As per the editorial this problem is solved using segment tree or prefix array with binary search. Do you still think it should be categorized as easy problem?
Given the constraints, \mathcal{O}(n^2\log^2n) shouldnāt pass. Though, with a Fenwick tree, it can be done in \mathcal{O}(n^2\log n) too.
1 Like
People say I write long and scary editorials. I believe they are worth it! What do you say?
And @taran_1407 seems to be missing someone who used to encourage him on his editorials almost every time 
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
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 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.
No shit! Guy has been caught cheating twice in past contestsā¦ See the history!
https://discuss.codechef.com/questions/97820/i-want-to-ask-a-question-ask-them-all-here
post it hereā¦ donāt ask for free karma pointsā¦
Thatās kind of excuse. Sorry. Ordered statistics tree is not something beginner wants to know at first. I hope easy problems are actually easy to solve for beginners. Otherwise it seems that the platform discriminates the participants since this problem looks easier for experienced participants.
Can you explain it please?
Thanks a lot!
<3 for O(T*n^3)
1 Like
Look what I found while checking some solutions.