I have submitted it using map and after storing iterating from end still getting tle … ?
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
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
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.
JAVA people, whoever is struggling to get rid of TLE for this problem, use BufferedWriter and BufferedReader that will reduce time a lot
The official editorial is not helpful!
Had much trouble in understanding!
Nice solution at : CodeChef/RP.cpp at master · executable16/CodeChef · GitHub
1 Like
I had same problem with TreeSet :-/
If anyone want more info on procedure… i can elaborate
yep… same way 
What the hell man you dont even test your setter’s and tester’s solutions…
It’s true, they give wrong answer. Maybe, because the test data was changed in the contest.
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…
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
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…
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)
i tried using multisets but i gives me tle…can u please check
http://www.codechef.com/viewsolution/1654148
@sikander_nsit - check out your loops… and check my solution… there is still optimization required !!
4
1 10
1 20
1 8
2
Excellent and Simplest Approach to Understand! Thanks!