Explanation required for Atcoder ARC133B Problem

Revision en1, by asawa_harsh, 2022-03-14 11:29:21

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.

Tags atcoder, dp, lis

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English asawa_harsh 2022-03-14 11:30:12 26
en1 English asawa_harsh 2022-03-14 11:29:21 949 Initial revision (published)