10810 - Ultra-QuickSort

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

10810 - Ultra-QuickSort

Post by technobug » Tue Feb 08, 2005 12:05 am

Hey there,

I have implemented a binary tree (using a vector), and each time i get a new item to add to the tree, i count how many times its compared with someone bigger than itself (+1) and for each one it is NOT bigger than itself, it counts how many are at his right side.

Its kinda confusing

I belive the answer is to implement this kind of tree, I just cant get it right... any suggestions?

Code: Select all

HUMMM...
Last edited by technobug on Tue Feb 08, 2005 4:06 pm, edited 1 time in total.

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Tue Feb 08, 2005 12:44 am

I'm not sure if your algorithm is fast. In order to count the minimun number of swaps, you should use a 64-bit integer, because of in the worst case [ 500000, 499999, 499998, .... , 1 ] you need (500,000) * (499,999) / 2 swaps and that number doesn't fit into a 32-bit integer.

My implementation use a divide&conquer algorithm.

Hint. Is well known that making a sorted list from two sorted lists is O(n), and counting minimun necessary swaps for processing it is relatively easy.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Tue Feb 08, 2005 4:10 pm

In fact, it did work in 3.5 seconds, its an N*lg(N) algorithm. Got AC after changed it to long long.

During the contest, what was the time limit for it?

How fast is your D+C algorithm? What is its idea?

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue Feb 08, 2005 5:33 pm

Time limit during the contest was 5 sc.
My code works 1.4 sc(Pascal).I use mergsort to sort the input and during the sort calculate the answer.This algorithm is O(Nlog(N)).If you want I can tell more about the algo or you can read about it from many book for example from Cormen.
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Wed Feb 09, 2005 7:50 am

technobug wrote:How fast is your D+C algorithm? What is its idea?
My original program runs 8) in 1.150 seconds

Main idea was already posted by Eduard :D

I've managed for optimization, and now runs in 0.771. Showing that scanf is slow.
Last edited by filigabriel on Tue Mar 08, 2005 2:31 pm, edited 1 time in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

AC

Post by sohel » Wed Feb 09, 2005 10:04 am

I also used D&C and got AC in 2.14 seconds..

.. its funny that to solve a quicksort program, one has to implement merge sort.

- It also seems that some managed to solve it taking < 1sec time.
Is there any other method other then the classical merge sort?

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Wed Feb 09, 2005 1:20 pm

I implemented the same algorithm, but changed to bubblesort for small n. Merging is done with pointers, which speeds up the process a bit. And I must admit that I wrote a small function for parsing an integer from a string, which is a lot faster than scanf.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Re: AC

Post by gvcormac » Wed Feb 09, 2005 3:21 pm

sohel wrote:I also used D&C and got AC in 2.14 seconds..

.. its funny that to solve a quicksort program, one has to implement merge sort.

- It also seems that some managed to solve it taking < 1sec time.
Is there any other method other then the classical merge sort?
The sort in the problem is "quicksort" in name only.

There's a straightforward solution using quicksort. Just count the
number of inversions you have to do when you arrange the elements
about the pivot.

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

whats wrong?

Post by trulo17 » Fri Feb 11, 2005 9:18 am

whats wrong with this? please help me. thx.
Last edited by trulo17 on Sat Feb 12, 2005 1:50 am, edited 1 time in total.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Fri Feb 11, 2005 10:48 am

It seems you only add to the result if you arrived at the end of the right half during merging. Try the case

Code: Select all

4
1
2
3
1
The answer should be 2, but your program prints 1.

Hint: Each time a number from R is inserted, you need to count the numbers from L that are greater than this number.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Feb 11, 2005 2:49 pm

Hmm. That's bad input because all numbers should be distinct.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Fri Feb 11, 2005 4:52 pm

Sorry, I didn't read the problem description again. Here is a correct case where your program fails:

Code: Select all

4
1
3
4
2
Your output is 1, although 2 swaps are necessary (2<->4, then 3<->2)

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

thx

Post by trulo17 » Fri Feb 11, 2005 4:53 pm

thanks to christian and little joey for answering. Yes, input is not right, but the hint is totally correct. Got Ac now, thx again.

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

Post by sunhong » Thu Feb 17, 2005 11:50 am

I use Mergesort to solve this problem,but WA~
Can someone tell me where is wrong?thanks
Last edited by sunhong on Fri Feb 18, 2005 3:54 am, edited 1 time in total.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Thu Feb 17, 2005 6:57 pm

Your data type is not correct. You need long long int in this problem. See the past posts.

Regards
Sanny

Post Reply

Return to “Volume 108 (10800-10899)”