I wrote a recursive solution with O(n^3) time complexity imo.

But I am getting TLE Verdict on submission .

Problem Link

Problem Link

Editorial Link

Samples —

3 1 4 2

4 2 1 3

According to the editorial we are taking pairs of indices which form a valid pair (Qj,Pi). All pairs are = (0,3)(1,0),(1,1)(1,2)(1,3)(2,0)(3,0)(3,1). [zero based indexing] Now we are sorting according to (i,-j).

New order of pairs is = (0,-3)(1,-3),(1,-2)(1,-1)(1,0)(2,0)(3,-1)(3,0). Now taking LIS considering only j's, we have ans as 4 but answer should be 2.

There is no clear explanation in the editorial, no C++ sample solution in the editorial and No english youtube video explaining this approach. I also tried to understand solutions of top rated coders but I think they have used fenwick tree.

Can anyone explain please I am stuck in this question since a day trying to understand this editorial.

Can anyone tell me the dp transitions for this problem ? Even after seeing the editorial I am not able to code.

Problem link

I am getting runtime error on n=1000, m=1000 test cases. Unable to figure out why.

Sorry for messed up code.

Code link: https://cses.fi/paste/ca53210d467e6f2f2d250f/