PBDS came quite handy for this problem. Solution
I was really amazed to see this question and the optimizations that were to be done to get an AC.
The hints of constraints were really tricky and PBDS could be the only method to solve them.
However, out of nowhere, I was checking some codes of Subprnjl after Contest ended and came to see this.
The editorial is pretty fine. There can be one more solution which is more or less similar to the editorialist’s solution that applies binary search over segment tree/bit and this was the intended solution when I created the problem. Later seeing so many other solutions was also amazing. The complexity for this approach will be O(n*logn)^2 which will pass in given time limit.
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.
Also my solution without using segment tree. My Solution
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++).
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
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 : https://www.codechef.com/viewsolution/23403845
Kudos to Problem Setter
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.
- 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.
O(N^2) per test case solution with frequency array in 0.04 sec.
What is wrong in my solution? Please help…
I think the test cases were weak. O(N^3) solutions also got accepted. Check this one.
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