PSHTRG - Editorial

Solutions are not visible :frowning:

Wouldn’t a much simpler solution be to just make a segtree which returns the index of the max element in a range? After extracting the max index, we can save it and then point update it to 0 and then do the max query again to get the second largest. This is O(KlogN) query and O(logN) update but is much simpler.

12 Likes

I have used square root decomposition for the problem.
https://www.codechef.com/viewsolution/17760397

3 Likes

@kayak 2^31 is less than 3*10^9.

Can I get a link to nice tutorial on Segment tree ?
Btw I passes this question using sqrt decomposition. CodeChef: Practical coding for everyone
With little optimisation.

1 Like

No need to store 50 points… while merging two arrays from child nodes… we can break adding points when we get a triangle and by fibonacci it is clear that no. of points would be less than 50 always… so it would be more optimized…
sample code for merging could be…


s1=size of v1 , s2 = size of v2....
 while(i<s1 && j<s2)
  {
        if( v[k-1] + v[k-2] > v[k-3]) /// breaking condition
            return ;
        if(v1[i] > v2[j])
        v.push_back(v1[i++]);
        else
        v.push_back(v2[j++]);
        k++;
  }

I am not getting how this O(Q*N) submission of mine is getting 100 points.
My approach :
First I created a vector of pair in which i stored every element’s value and index. Then I sorted this vector.
For first query I used an algorithm similar to one used in insertion sort. And for query 2 I just traversed
the array from backward and checked the conditions for an element, whether its index is between l and r .

1 Like

I got AC with full 100 points using Square root decomposition, should have got WA, but test cases were weak. Slution

neither tester nor setter’s solution are opening… showing the error “This XML file does not appear to have any style information associated with it. The document tree is shown below.” fix it @admin

Anybody tell me why its showing WA for this solution:solution

Is there any reason to choose k=50? If Yes can some one explain?

Please can someone explain to me the math involved behind the limiting the value of K to 50 ?

harrypotter0 For mathematical calculations ,refer to this

Can anyone help me. Why this code is giving TLE?

can anyone just tell me how setter is doing without sorting nodes.

Please can someone help me in improving my solution. I have understood the concept and written a code but it is giving TLE.The complexity is Q.K.log n where k = 45. here is my code Thanks

@ista2000 can you please explain your approach. I am new to segment trees.
Thanks in Advance:)

You can also simply use Max Segment Tree: Query for the largest element, remove it (by setting the value to -infinity), and repeat it K times. Afterwards you just restore the values. This is also O(K \log n) per query.

4 Likes

very nice editorial @adkroxx

3 Likes

Wow such a different idea . Never thought of this.

1 Like