I agree, this is definitely not an easy problem.
The reason why this is classified as easy is because its classical. We can reduce the problem to "Finding k'th largest element in an unsorted array, which is one of the classical (and well known/basic) problem of order statistical tree. If you know the data structure, then its just tree.insert(k); tree.find_k'th_largest(); . If you dont know the data structureā¦life becomes messier :3
2 Likes
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
For n = 2000, n^2\log^2n is approximately 4.8 \times 10^8. Also there are five test cases, which makes it 2.4 \times 10^9. But I guess the actual number of operations done is much less than this value, which is why \mathcal {O}(n^2\log^2n) passes.
I see people discussing about O(T*n^2*log^2(n))
How about O(T*n^3) ??
Have a lookā¦
https://www.codechef.com/viewsolution/23473452
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++).
I tried using a Merge Sort Tree (Java) with time complexity O(nlogn)^2, though it timed out. I used fast io and precomputation for getting count in O(1). PBDS in C++ ofc provides O(logn) operations which gave final TC of O(n^2logn)
NVM i think TreeSet in java also does smth similar
That is so lol. CHONQ had very tight constraints and O(Tān3) passes for this problem.
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 
1 Like
No shit! Guy has been caught cheating twice in past contestsā¦ See the history!
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