RRATING - Editorial

yellow_agony · July 11, 2012, 4:09pm

PROBLEM LINKS:

DIFFICULTY:

Easy

PREREQUISITES:

Heaps

PROBLEM:

You’re given an online stream of numbers. At any point of time if K numbers have already appeared, you need to find out floor(K/3)^th largest number.

QUICK EXPLANATION:

Maintain two heaps - one min heap for top floor(K/3) numbers and other max heap for all remaining numbers.

DETAILED EXPLANATION:

We can maintain two different heaps - one min heap for top 1/3^th of votes and
one max heap for all other votes. Once we have this, we can simulate actual
voting itself. The reason is after every vote, at maximum 1 vote moves between
the heaps.

To understand this, let’s say that at some point of time we’ve x votes in top heap
and N - x votes in other heap. If a new vote comes push it in one of the two halves
by comparing its value to the lowest value in top heap. Now assume it went in top
heap. Number of votes in top heap might be more than floor( (N+1) / 3) now in which case we’d need to transfer some numbers to the other heap. But difference
is only of 1 vote as number of votes in top heap <= 1 + floor(N/3) and hence only 1 vote needs
to goto bottom heap. That one vote has to be the minimum value of this heap.
By similar argument, had the vote gone to bottom heap, again only its topmost value
need to be transfered to top heap, if at all.

At any query, all we have to do is find out the smallest value from top heap and print it.

Complexity of our solution is O(N log N) as we take O(log N) time per query.

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

RELATED PROBLEMS:

Spoj Weird Function

lazzrov · July 11, 2012, 7:19pm

I tried the same solution with TreeSet and myInteger class to take care of the duplicates. Because it gave me TLE, I tested only insertion in one treeset, and it gave me TLE again. Why did this happen? They’re suppose to be equivalent in their complexities for insertion with the priority queue and to be balanced to get the logn… (I used fast io)

shashank_jain · July 11, 2012, 9:54pm

This can also be done with MULTISET STL in C++… but just you have to careful with iterator… since iterator is only bidirectional here not random.

asif_iut · July 12, 2012, 12:30am

instead of maintaining two heaps it can also be done using Treaps ( Treap - Wikipedia )

red_coder · July 12, 2012, 9:21am

i am not happy with codechef. When i tried with cin and cout i got TLE and when i tried with printf() and scanf() i got AC. I think Codechef should know that its a algorithmic contest not a Humpty-Dumpty Language contest…

swissknife007 · July 12, 2012, 12:32pm

Pathetic the setters solution shows wrong answer on submissio? Just how bad things can get for Codechef

shadow · July 12, 2012, 11:37pm

I used Segment trees

sahebrm · July 19, 2012, 4:14pm

Can’t the simple binary search work?

notaloser · March 22, 2013, 4:45am

getting wrong ans plz check my code… CodeChef: Practical coding for everyone

vinitpayal · December 8, 2014, 5:52am

I have submitted it using map and after storing iterating from end still getting tle … ?

rahul_iit · August 29, 2017, 9:39pm

An easy way to solve the problem is to store the first position of box(n/3), say var and see the shifts of this element. Only two cases are held. One case is if n divisible by 3 and var greater than new value inserted, we shift one behind. Its symmetric case is if n not divisible by 3 and var less than or equal to new value inserted, we shift one ahead.
Link to Solution : CodeChef: Practical coding for everyone

ayushtewary07 · January 21, 2018, 1:59am

I trid it this like this but it gave TLE in my submission
Check my solution CodeChef: Practical coding for everyone
Help me to rectify my mistake

samarth1402 · December 24, 2018, 2:24pm

Alternate approach

There is a simpler solution. We use 2 multi-sets. One stores the top 1/3 elements, other stores the bottom 2/3 elements.

Here is a link to a well commented solution of this problem.

https://www.codechef.com/viewsolution/22073441

sgrpwr · February 13, 2019, 9:09pm

JAVA people, whoever is struggling to get rid of TLE for this problem, use BufferedWriter and BufferedReader that will reduce time a lot

executable · February 17, 2019, 2:31pm

The official editorial is not helpful!
Had much trouble in understanding!

Nice solution at : CodeChef/RP.cpp at master · executable16/CodeChef · GitHub

betlista · July 11, 2012, 7:25pm

I had same problem with TreeSet :-/

shashank_jain · July 11, 2012, 9:56pm

If anyone want more info on procedure… i can elaborate

javadecoder · July 11, 2012, 10:15pm

I did the same , CodeChef: Practical coding for everyone

shashank_jain · July 11, 2012, 10:36pm

yep… same way

swissknife007 · July 12, 2012, 12:37pm

What the hell man you dont even test your setter’s and tester’s solutions…