Page 1 of 3
10810 - Ultra-QuickSort
Posted: Tue Feb 08, 2005 12:05 am
by technobug
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?
Posted: Tue Feb 08, 2005 12:44 am
by filigabriel
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.
Posted: Tue Feb 08, 2005 4:10 pm
by technobug
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?
Posted: Tue Feb 08, 2005 5:33 pm
by Eduard
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.
Posted: Wed Feb 09, 2005 7:50 am
by filigabriel
technobug wrote:How fast is your D+C algorithm? What is its idea?
My original program runs
![8)](./images/smilies/icon_cool.gif)
in
1.150 seconds
Main idea was already posted by Eduard
I've managed for optimization, and now runs in 0.771. Showing that scanf is
slow.
AC
Posted: Wed Feb 09, 2005 10:04 am
by sohel
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?
Posted: Wed Feb 09, 2005 1:20 pm
by Christian Schuster
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.
Re: AC
Posted: Wed Feb 09, 2005 3:21 pm
by gvcormac
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.
whats wrong?
Posted: Fri Feb 11, 2005 9:18 am
by trulo17
whats wrong with this? please help me. thx.
Posted: Fri Feb 11, 2005 10:48 am
by Christian Schuster
It seems you only add to the result if you arrived at the end of the right half during merging. Try the case
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.
Posted: Fri Feb 11, 2005 2:49 pm
by little joey
Hmm. That's bad input because all numbers should be distinct.
Posted: Fri Feb 11, 2005 4:52 pm
by Christian Schuster
Sorry, I didn't read the problem description again. Here is a correct case where your program fails:
Your output is 1, although 2 swaps are necessary (2<->4, then 3<->2)
thx
Posted: Fri Feb 11, 2005 4:53 pm
by trulo17
thanks to christian and little joey for answering. Yes, input is not right, but the hint is totally correct. Got Ac now, thx again.
Posted: Thu Feb 17, 2005 11:50 am
by sunhong
I use Mergesort to solve this problem,but WA~
Can someone tell me where is wrong?thanks
Posted: Thu Feb 17, 2005 6:57 pm
by Sanny
Your data type is not correct. You need long long int in this problem. See the past posts.
Regards
Sanny