What is PBDS and can you please share a good link to read and study them?
Just to share another approach.I solved it without using tree, through count sort.As sorting of subarrays ws required afew times as count was maintained.
Here is my solution.
Hey guys, found this solution from @shubhammitt in java. Seems like the fastest one. : )
Solution
Also my solution without using segment tree. My Solution
1 Like
I tried implementing a Merge Sort Tree in JAVA to solve this, but the time complexity of that was O((nlogn)^2). PBDS was super easier in C++. Thanks to author for this problem. Learnt quite a lot (and shifted to C++).
1 Like
Two submissions of mine, one with prefix sum ( same as in the editorial ) took 0.47 sec and another one with treap took 1.49 sec, LOL!
Solution 1 : https://www.codechef.com/viewsolution/23362784
Solution 2 : https://www.codechef.com/viewsolution/23582294
1 Like
I used Wavelet Tree for solving the problem.Great to see such different approaches being used for solving the question.
Here’s the link to my solution : CodeChef: Practical coding for everyone
Kudos to Problem Setter 
3 Likes
I’m amazed by all the different approaches out here, I believe this will help me learn a lot once I implement them myself. As for my solution, I maintained a count array for each subarray I generated, and then traversed the count array. I subtracted count for every element until the value reaches zero or below.
I believe this is an O(N^3) solution in the worst case, but with a couple of observations, it passed within 0.4 seconds.
Observations:
- If all the elements in the subarray are distinct, no matter what the kth element is, it’s count will always be 1, so we just have to check for the count of 1.
- If k \geq s^2 , then the kth element will always be the last element in the subarray, so all we need to maintain is the largest element found so far.
s is the size of the subarray, i.e s = (r-l+1)
I hope the code will be self explanatory.
Did anyone get complete AC using balanced trees?
this question can be solve using Binary Index Tree.
As there were required to find Kth smallest element in unsorted array, so by using of Binary Index Tree we can do it.
SUBPRNJL
O(N^2) per test case solution with frequency array in 0.04 sec.
https://www.codechef.com/viewsolution/23583890
1 Like
nice editorial!
Worth mentioning that the BS solution can be sped up substantially by initializing M to the previously found B_x. Amazingly, I still could not get this to pass TL in python 
@admin: How a solution gets complete AC when it takes 3.74 sec for some test cases and written in Java? What is the time limit for this problem for JAVA?
Solution of Another Solution mentioned in Editorial.
Just Instead of Two heaps I maintained one Max Heap and one Array. I got AC in 0.58 seconds.
1 Like
I passed the testcases using a persistent segment tree to know the value of the kth element in a range [l,r]. Each query takes log2(N), so passes all the testcases in N * N * log2(N). Nice question if you want to learn different methods to find the kth element in range [l,r] in different complexities. I referred Merge Sort Tree, Order Statistics Tree, and an old Codeforces blog. Beautiful problem 
I used the Persistence segment tree for finding kth smallest element. Is this is what the editorial is talking about?
what is the use of TREEOFFSET there in the tester solution? will anyone, please explain to me. thanks in advance