10107 - What is the Median?

[brianfry713]

Try using an array instead of a vector, and inserting each X into the array in linear time instead of sorting. Also why would you sort the same vector multiple times?

[brianfry713]

I solved this in a few different ways to compare the run time.
Using two priority queues, each one with half of the numbers seen so far. Keep all of the numbers in one priority queue less than or equal to all of the numbers in the other priority queue. AC in 0.019 sec.
Using an array and doing a linear search to insert each number into it, AC in 0.042 sec. I sped it up by doing a binary search for the insertion position and AC in 0.025 sec.
Using a linked list and first inserting the new number and then finding the median, AC in 0.175 sec. I sped it up by finding the median on the same pass as inserting the new number and AC in 0.138 sec.

[kaushik_acharya]

http://discuss.codechef.com/questions/1 ... sorting-it
This is a helpful discussion in another website where selection algorithm is suggested.

[brianfry713]

I got TLE using the selection algorithm on this problem. The selection algorithm would work if we only had to print the median of the entire array. Since we have to print the median for each input, the fastest way I've found to solve this problem is using two priority queues.

[vsha041]

Hi I am getting Wrong Answer. However it does pass this forum's and my own test cases. Can anyone give me a hint as to what is wrong here? Thanks.

Code: Select all

Code removed after ACCEPTED

[vsha041]

Well I found out the problem. The key is that nth_element function only brings 1 element in its correct location and this element is the one where the algorithm is applied. For example if your vector contains 4 numbers - 23, 34, 1, 4

then nth_element(begin(v), begin(v) + 2, end(v)) will only bring the third element of the vector in the correct location. One possible ordering of the vector after applying this function could be 4, 34, 23, 1 i.e. 23 is at its correct final place. This is where it would have been if the entire list was sorted. Now that's not enough to get the median if the vector size is even. You will need to apply the function again for nth_element(begin(v), begin(v) + 1, end(v)).

[mratan16]

I cannot seem to figure out why my code is wrong.

Please help

Code: Select all

Removed after AC

[lbv]

I cannot seem to figure out why my code is wrong. Please help

The program you posted doesn't pass the sample cases given in the problem statement. Check that you're printing the newline characters properly.

Also try:

Input

Code: Select all

1
1
2
2
8
8
9
9
5
6

Output

Code: Select all

1
1
1
1
2
2
2
5
5
5

[mratan16]

It does work along those test cases. I edited it a bit since i noticed that I forgot to print a newline. It still however still get WC.

Please help. Thanks in advance

Code: Select all

Removed after AC

[lbv]

It does work along those test cases.

It doesn't. If you can get past your natural skepticism, my friend, you can see here the output from your program (see at the bottom). Compare it with the expected output.

Using nth_element seems like an interesting idea, but if you call it two consecutive times, the partial ordering performed during the first call will not necessarily be preserved after the second call. I hope I'm making myself clear

[mratan16]

I do apologize. While the correct output appears on my laptop apparently it does not work in online compilers. Would you have any idea why?

As for why I chose nth_element above sort is because
1. I want to learn it
2. It was recommended in a book for this problem

[mratan16]

I tweaked the solution and you are indeed right. The nth element is not saved. Thank you very much for the help . I got AC now.

On a side note, how come it works on my Mac, same thing occurs on some "compile errors" that occur in UVA but not in my mac

[brianfry713]

Each system or compiler can implement the undefined behavior of a function in different ways.
http://www.cplusplus.com/reference/algo ... h_element/
The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less.

You can see the reason for your compile errors by clicking My Submissions.

Also notice on the submit page which compiler and options that this online judge uses.
ANSI C 4.8.2 - GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE
JAVA 1.7.0 - Java Sun JDK
C++ 4.8.2 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
PASCAL 2.6.2 - Free Pascal Compiler
C++11 4.8.2 - GNU C++ Compiler with options: -lm -lcrypt -O2 -std=c++11 -pipe -DONLINE_JUDGE

[ehsanulbigboss]

Thanks to brianfry713

[brianfry713]

Your algorithm is too inefficient.
Try using two priority queues.