SUBPRNJL - EDITORIAL

binary-search
easy
march19
partial-sums
segment-tree
subprnjl
taran_1407

#41

No need according to my opinion…
This was little above easy…


#42

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?


#43

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.


#44

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 :frowning:


#45

I agree, this is definitely not an easy problem.


#46

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


#47

Why not? n is only 2000 and you are given 2 seconds. https://www.codechef.com/viewsolution/23329611


#48

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 imes 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.


#49

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


#50

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)


#51

NVM i think TreeSet in java also does smth similar


#52

That is so lol. CHONQ had very tight constraints and O(T∗n3) passes for this problem.


#53

No shit! Guy has been caught cheating twice in past contests… See the history!


#54

yes @udayan14 XD


#55

Yup I got. I used treap.
https://discuss.codechef.com/questions/146555/subprnjl-editorial/146653


#56

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…


#57

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.


#58

Can you explain it please?


#59

Thanks a lot!


#60

<3 for O(T*n^3)