SUBPRNJL - EDITORIAL

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

#21

@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?


#22

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


#23

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:


#24

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


#25

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


#26

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


#27

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

#28

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


#29

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


#30

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


#31

It will be really helpful if anybody could assist me where I am going wrong?
I have used pbds approach.
link to solution:-https://www.codechef.com/viewsolution/23641513


#32

PBDS and fenwick tree also works


#33

can’t believe 4 star user caught in plagiarism


#34

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


#35

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


#36

Both your solutions are really nice, @taran_1407. I could only think of a solution using a Fenwick tree.


#37


https://goo.gl/WVDL6g


#38

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)


#39

seriously!


#40

Then that standard needs to be rectified.