You are not logged in. Please login at www.codechef.com to post your questions!

×

RRATING - Editorial

9
3

PROBLEM LINKS:

Practice
Contest

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/3th 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

This question is marked "community wiki".

asked 11 Jul '12, 16:09

yellow_agony's gravatar image

4★yellow_agony ♦♦
1243837
accept rate: 0%

edited 30 Dec '12, 07:20

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.6k62119138


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

link

answered 12 Jul '12, 12:32

swissknife007's gravatar image

3★swissknife007
6114
accept rate: 0%

What the hell man you dont even test your setter's and tester's solutions...

(12 Jul '12, 12:37) swissknife0073★

It's true, they give wrong answer. Maybe, because the test data was changed in the contest.

(12 Jul '12, 12:46) juancate4★

Hey, your right about the setter's solution getting a "wrong answer". However, I added a little code segment to it and resubmitted to check. I got a correct submission this time. http://www.codechef.com/viewsolution/1180239

(14 Jul '12, 17:01) irajvardhan3★

4 1 10 1 20 1 8 2

(30 Dec '12, 14:55) jayesh024★

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)

link

answered 11 Jul '12, 19:19

lazzrov's gravatar image

4★lazzrov
136118
accept rate: 0%

edited 11 Jul '12, 19:20

I had same problem with TreeSet :-/

(11 Jul '12, 19:25) betlista ♦♦3★

If no one knows why this happened, then perhaps the admin can check the test case/s where it fails (and I'm speaking only for insertion in a treeset)

(19 Jul '12, 19:34) lazzrov4★

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.

link

answered 11 Jul '12, 21:54

shashank_jain's gravatar image

2★shashank_jain
6192813
accept rate: 10%

If anyone want more info on procedure.. i can elaborate

(11 Jul '12, 21:56) shashank_jain2★
(11 Jul '12, 22:15) javadecoder4★

yep... same way :)

(11 Jul '12, 22:36) shashank_jain2★

i tried using multisets but i gives me tle...can u please check http://www.codechef.com/viewsolution/1654148

(29 Dec '12, 00:58) sikander_nsit5★

@sikander_nsit - check out your loops.. and check my solution.. there is still optimization required !!

(29 Dec '12, 15:49) shashank_jain2★

instead of maintaining two heaps it can also be done using Treaps ( http://en.wikipedia.org/wiki/Treap )

link

answered 12 Jul '12, 00:30

asif_iut's gravatar image

2★asif_iut
1
accept rate: 0%

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

link

answered 12 Jul '12, 09:21

red_coder's gravatar image

3★red_coder
303
accept rate: 0%

It's written in FAQ. Also there is practice problem for this... It can be worse - for example when you cannot use HashMap/HashSet or sorting in Java at CodeForces...

(12 Jul '12, 14:43) betlista ♦♦3★

I used Segment trees :)

link

answered 12 Jul '12, 23:37

shadow's gravatar image

5★shadow
1
accept rate: 0%

Can't the simple binary search work?

link

answered 19 Jul '12, 16:14

sahebrm's gravatar image

2★sahebrm
1111
accept rate: 0%

Problem with binary search is, that you have to have sorted array. Let's assume I'll add 100.000 elements to array and then I'll switching command 2 and command 1, so you need something like 125.000 sorts in array with size 100.000. Sort do not need to be quicksort (0(n*log(n)), probably insert sort is better (O(n)) (I do not know something better), but it is still too slow...

(19 Jul '12, 18:18) betlista ♦♦3★

getting wrong ans plz check my code... http://www.codechef.com/viewsolution/1956023

link

answered 22 Mar '13, 04:45

notaloser's gravatar image

2★notaloser
11
accept rate: 0%

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

link

answered 08 Dec '14, 05:52

vinitpayal's gravatar image

3★vinitpayal
153
accept rate: 0%

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 : https://www.codechef.com/viewsolution/15162429

link

answered 29 Aug, 21:39

rahul_iit's gravatar image

4★rahul_iit
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×2,686
×20
×13
×4

question asked: 11 Jul '12, 16:09

question was seen: 6,321 times

last updated: 29 Aug, 21:39