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.
java and python are slow languages that’s why codechef and all OJs provide time multipliers for them. for java its x2, and for python its x5
I know they are slower but its not mentioned anywhere in the problem. Isn’t it?
That's kind of excuse. Sorry.
Dont be, lul. Neither I owe you any explanation nor do you. Its anyways my own opinion and not the setter/admins.
Ordered statistics tree is not something beginner wants to know at first.
Thats a very subjective thing. I can argue the same for other data structures like heap, segment tree, set etc. and say they should not be given as “Beginners will want a easy problem which they can solve.”
looks easier for experienced participants.
Which is alright lol.
Lastly, if everyone solves easy problem means they are learning nothing. Personally against that.
Hmm that all mean we shouldn’t have any category in Practice section like Easy, Medium, etc! Something related to segment tree or BIT shouldn’t be in easy in that case.
Hello @prmondal the test cases were weak and you can even solve this question with any tree and hence it’s an easy question… Okay fine ?
And btw I hope u know that all problems gets 100 points regardless of difficulty and it’s only setter who gets different amount of payment on basis of difficulty… I don’t see any point that u should have any problem… And the O(n^3) soln passes which shows it’s an easy problem
It can be solved by simple sum query Segment tree also and if you don’t even know segment tree then I don’t think you are a competitive programmer yet… It’s very popular tree… You should learn it by now then… And even if u don’t know it… It’s still solvable without it…