B - Two LIS Sum Editorial by evima
Hints → https://atcoder.jp/contests/arc149/editorial/4961
[1] Rephrasing the problem
Since one may swap adjacent \((A_i, B_i)\) and \((A_{i+1}, B_{i+1})\) any number of times, one may arrange the \(N\) tuples \((A_i, B_i)\) in any order. Thus, the problem can be rephrased into the following.
- We are to arrange \(N\) tuples \((A_i, B_i)\) freely and then mark some of the \(2N\) numbers \((A_1, \ldots, A_N)\), \((B_1, \ldots, B_N)\). Here, all marked \(A_i\) must be increasing, and the same goes for all marked \(B_i\). Find the maximum number of numbers that can be marked.
[2] Structure of an optimal solution
One can prove the following:
there is an optimal solution that marks all \(A_i\).
Let us do it. First, if there is \(i\) such that both \(A_i\) and \(B_i\) are unmarked, one can insert that \((A_i, B_i)\) in an appropriate position and then mark \(A_i\) to have more marks.
Thus, we can see that, in optimal solutions, \(A_i\) or \(B_i\) is marked for every \(i\).
Similarly, we can also prove that there is an optimal solution that marks all \(A_i\). If there is an optimal solution that does not mark \(A_i\), one can insert that tuple in an appropriate position and then unmark \(B_i\) and instead mark \(A_i\) to have more marks on \(A_i\) while keeping the total number of marks.
Therefore, one can take an optimal solution and repeat this operation as long as possible to get an optimal solution that marks all \(A_i\).
[3] How to solve the problem
In the end, one can compute the answer to the problem as follows.
- Sort the \(N\) tuples \((A_i, B_i)\) in ascending order of \(A_i\).
- The answer is then \(\mathrm{LIS}(A)+\mathrm{LIS}(B)=N+\mathrm{LIS}(B)\).
One can compute \(\mathrm{LIS}(B)\) in \(O(N\log N)\) time, and so the problem in \(O(N\log N)\) time.
Computing LIS
Here we list two methods.
Let \(\text{dp}[x]\) be the greatest length of an increasing subsequence ending with \(x\) when one considers up to some term in the sequence. Then, one can compute \(\text{dp}[x]\) fast using a segment tree. If the upper limit on \(x\) is large, one should compress the coordinates beforehand.
Let \(\text{dp}[k]\) be the smallest possible final term of an increasing subsequence of length \(k\) when one considers up to some term in the sequence. Then, one can compute \(\text{dp}[k]\) fast by binary search.
Sample submission
posted:
last update: