10107 - What is the Median?

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10107 - What is the Median?

Post by brianfry713 » Thu May 30, 2013 12:03 am

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!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10107 - What is the Median?

Post by brianfry713 » Fri Jul 12, 2013 12:51 am

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

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

Re: 10107 - What is the Median?

Post by kaushik_acharya » Thu Oct 03, 2013 4:22 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10107 - What is the Median?

Post by brianfry713 » Thu Oct 03, 2013 10:34 pm

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!

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 10107 - What is the Median?

Post by vsha041 » Sun Feb 23, 2014 9:41 pm

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.

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 10107 - What is the Median?

Post by vsha041 » Sun Feb 23, 2014 11:15 pm

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
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

Re: 10107 - What is the Median?

Post by mratan16 » Tue Jul 29, 2014 8:51 am

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

Please help

Code: Select all

Removed after AC
Last edited by mratan16 on Tue Jul 29, 2014 2:08 pm, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10107 - What is the Median?

Post by lbv » Tue Jul 29, 2014 11:12 am

mratan16 wrote: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
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

Re: 10107 - What is the Median?

Post by mratan16 » Tue Jul 29, 2014 11:32 am

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
Last edited by mratan16 on Tue Jul 29, 2014 2:08 pm, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10107 - What is the Median?

Post by lbv » Tue Jul 29, 2014 12:23 pm

mratan16 wrote: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
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

Re: 10107 - What is the Median?

Post by mratan16 » Tue Jul 29, 2014 2:06 pm

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
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

Re: 10107 - What is the Median?

Post by mratan16 » Tue Jul 29, 2014 2:09 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10107 - What is the Median?

Post by brianfry713 » Tue Jul 29, 2014 7:29 pm

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
Check input and AC output for thousands of problems on uDebug!

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

Re: 10107 - What is the Median?

Post by ehsanulbigboss » Thu Oct 16, 2014 8:57 am

Thanks to brianfry713
Last edited by ehsanulbigboss on Thu Feb 05, 2015 10:01 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10107 - What is the Median?

Post by brianfry713 » Thu Oct 16, 2014 8:52 pm

Your algorithm is too inefficient.
Try using two priority queues.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest