Hi. I tried solving “Yet again a subarray problem”, all testcases passed except one getting TLE. Here I am posting submission to the problem. Please suggest how can i optimize it more.
That’s not your submission, that’s the link to the submit page (your code may be cached locally, but only for you). You have to find your submission by clicking “My Submissions” from the problem page.
1 Like
Oh yes, i am sorry for that, My bad. i edited the link please headover
The array elements are capped at 2000, so that should get rid of one of the map operations.
Also, notice that when you add a new element, the position of the k-th smallest element won’t change by much. Think about how you can take advantage of that.
@galencolin Yes i tried taking advantage of finding kth smallest element quickly, but I am getting stuck in the case where elements may be repeated.
For e.g. Let 1, 2, 3, 2 and K = 3
for [1], 3rd smallest = 3
for [1, 2], 3rd smallest = 2
for [1,2,3], 3rd smallest = 3
for [1,2,3,2], 3rd smallest = 2
I can’t see pattern in this 
, how can i do it quickly.
I thought of using pbds with pair<int,int> but then i need to search smallest linearly in case of repeated elements.
I’d imagine the time limit only allows for 1 or 2 light log(n) operations (also, I remember having to squeeze my solution into TL for this a while ago too). PDBS works but has a very bad constant, so I’m not sure if it will pass.
And… looking back at my own solution that I hacked together a year ago, I realize I have no idea how I came up with this. But I have an explanation for it now.
(everything is 0-indexed) Fix a value of l, and consider the value of m you get for each subarray. This is \left \lceil \dfrac{K}{r - l + 1} \right \rceil. The only value that changes is r, which increases, so m will be nonincreasing as you sweep right. Then the position you want in the set is i = \left \lfloor \dfrac{K}{m} \right \rfloor. Because m is nonincreasing, i is nondecreasing.
Since i is nondecreasing, we can maintain an iterator to the i-th position in a multiset that stores all current array elements and only have to increment it at most n times for each l. Multiset iterators are quite simple. If an element is inserted with value strictly less than the value at the iterator, then the iterator’s position will increase by one, otherwise it won’t. So you can compute i, and the current iterator position j based on the last value of i and the insertion, then advance the iterator by i - j positions. The value at the iterator will be the K-th smallest.
There’s one special case, when (r - l + 1) \geq K, but in this case you only have to move the iterator backwards. The function advance handles both forward and backward cases quite nicely.
Ultimately O(n) iterator operations are done, so the only log(n) factor is a single multiset insertion for each element. Efficiently using PDBS probably renders this whole thing useless, but I really like this solution 
(Also, you don’t need to search linearly with PDBS, you can use it like a multiset by following this)
1 Like
Ok great. thanks 
I will work upon it.