10810 - Ultra-QuickSort

Moderator: Board moderators

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

10810 - Ultra-QuickSort

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.

filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:
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:
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
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

filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:
technobug wrote: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.
Last edited by filigabriel on Tue Mar 08, 2005 2:31 pm, edited 1 time in total.

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

AC

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
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
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

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

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

whats wrong?

Last edited by trulo17 on Sat Feb 12, 2005 1:50 am, edited 1 time in total.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 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``````

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. That's bad input because all numbers should be distinct.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
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

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
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:
Your data type is not correct. You need long long int in this problem. See the past posts.

Regards
Sanny