10107  What is the Median?
Moderator: Board moderators

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10107  What is the Median?
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?
Check input and AC output for thousands of problems on uDebug!

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10107  What is the Median?
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.
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.
Last edited by brianfry713 on Thu Oct 03, 2013 10:34 pm, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 17
 Joined: Thu Jul 28, 2005 3:05 pm
 Location: Bangalore, India
Re: 10107  What is the Median?
http://discuss.codechef.com/questions/1 ... sortingit
This is a helpful discussion in another website where selection algorithm is suggested.
This is a helpful discussion in another website where selection algorithm is suggested.
My experience with Fraudster khari

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10107  What is the Median?
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.
Check input and AC output for thousands of problems on uDebug!
Re: 10107  What is the Median?
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
Last edited by vsha041 on Sun Feb 23, 2014 11:15 pm, edited 1 time in total.
Re: 10107  What is the Median?
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)).
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)).
Re: 10107  What is the Median?
Last edited by mratan16 on Tue Jul 29, 2014 2:08 pm, edited 1 time in total.
Re: 10107  What is the Median?
The program you posted doesn't pass the sample cases given in the problem statement. Check that you're printing the newline characters properly.mratan16 wrote:I cannot seem to figure out why my code is wrong. Please help
Also try:
Input
Code: Select all
1
1
2
2
8
8
9
9
5
6
Code: Select all
1
1
1
1
2
2
2
5
5
5
Re: 10107  What is the Median?
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
Please help. Thanks in advance
Code: Select all
Removed after AC
Last edited by mratan16 on Tue Jul 29, 2014 2:08 pm, edited 1 time in total.
Re: 10107  What is the Median?
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.mratan16 wrote:It does work along those test cases.
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
Re: 10107  What is the Median?
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
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
Re: 10107  What is the Median?
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
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

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10107  What is the Median?
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
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
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 32
 Joined: Tue Jul 22, 2014 1:17 am
Re: 10107  What is the Median?
Thanks to brianfry713
Last edited by ehsanulbigboss on Thu Feb 05, 2015 10:01 pm, edited 1 time in total.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10107  What is the Median?
Your algorithm is too inefficient.
Try using two priority queues.
Try using two priority queues.
Check input and AC output for thousands of problems on uDebug!