SUBPRNJL - EDITORIAL

@admin: How a solution gets complete AC when it takes 3.74 sec for some test cases and written in Java? What is the time limit for this problem for JAVA?

Solution of Another Solution mentioned in Editorial.

Just Instead of Two heaps I maintained one Max Heap and one Array. I got AC in 0.58 seconds.

https://www.codechef.com/viewsolution/23590325

1 Like

I passed the testcases using a persistent segment tree to know the value of the kth element in a range [l,r]. Each query takes log2(N), so passes all the testcases in N * N * log2(N). Nice question if you want to learn different methods to find the kth element in range [l,r] in different complexities. I referred Merge Sort Tree, Order Statistics Tree, and an old Codeforces blog. Beautiful problem :smiley:

I used the Persistence segment tree for finding kth smallest element. Is this is what the editorial is talking about?

I am getting tle for my solution.
https://www.codechef.com/viewsolution/23590284

what is the use of TREEOFFSET there in the tester solution? will anyone, please explain to me. thanks in advance

someone, please give the links of the resources of

  1. finding kth smallest element in an array for a range
  2. frequency find in a range

I applied the last approach of Heap using priority queue. Can anyone tell me where I was going wrong?
https://www.codechef.com/viewsolution/23482405

I maintained an array throughout the problem and used insertion sort and tweaked a bit of binary search to find the position to insert an element. once array is sorted, everything will be easy.
Got an AC :wink: hahah

Have a look here solution

1 Like

Why am I unable to add a comment to other users’ answers?

It will be really helpful if anybody could assist me where I am going wrong?
I have used pbds approach.
link to solution:-CodeChef: Practical coding for everyone

PBDS and fenwick tree also works

can’t believe 4 star user caught in plagiarism

as it was an easy problem… its neither cake walk nor medium according to codechef standards or admin’s/editorialist’s standards…

exactly… I did binary search over BIT… :smiley:

https://goo.gl/WVDL6g

1 Like

it’s a kind of balanced binary search tree afaik…
you can consider it as a black box which does these operations in O(logn)

2 Likes

seriously!

Then that standard needs to be rectified.

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