10810 - Ultra-QuickSort

[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?

Code: Select all

HUMMM...

[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.

[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?

[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.

[filigabriel]

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

My original program runs 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.

[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?

[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.

[gvcormac]

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]

Code: Select all

whats wrong with this? please help me. thx.

[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

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.

[little joey]

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

[Christian Schuster]

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]

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]

I use Mergesort to solve this problem,but WA~
Can someone tell me where is wrong?thanks

[Sanny]

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

Regards
Sanny