公式

G - Suitable Edit for LIS 解説 by en_translator

Prerequisite: how to find LIS (Longest Increasing Sequence) fast? (From the editorial of ABC354-F)

Given a sequence $A$, its LIS (Longest Increasing Sequence) can be found as follows.

Apply coordinate compression to assume $1 \leq A_i \leq N$. We adopt Dynamic Programming (DP). Let $\mathrm{dp}[i][j]$ be the length of a LIS, chosen from the first $i$ elements, and whose last element is $j$. The initial states are $\mathrm{dp}[0][0] = 0$ and $\mathrm{dp}[0][1] = \mathrm{dp}[0][2] = \dots = \mathrm{dp}[0][N] = \mathrm{-inf} $, and the transitions for $i = 1, 2, \dots ,N$ are as follows:

  • $\displaystyle \mathrm{dp}[i][j] = \max_{0 \leq k < j} \mathrm{dp}[i - 1][k] + 1$ for $j = A_i$.
  • $\displaystyle \mathrm{dp}[i][j] = \mathrm{dp}[i - 1][j]$ for $j \neq A_i$.
The sought length of a LIS is $\displaystyle \max_{0 \leq k \leq N} \mathrm{dp}[N][k]$. One can also reconstruct a LIS itself.

The complexity of a naive implementation would cost $O(N^2)$, but it can be reduced to $O(N \log N)$. There are mainly two approaches. We introduce a way that uses a segment tree.

The DP above can be simply represented as pseudocode as follows: 

dp = [N + 1] * [N + 1]
dp.fill(-inf)
dp[0][0] = 0
for (int i : (1, N))
    max_value = 0
    for (int j : (0, A[i] - 1))
        max_value = max(max_value, dp[i - 1][j])
    dp[i][j] = max_value + 1

With a segment tree with segment-max retrieval, the DP above can be turned into in-place style: 

RangeMaxSegmentTree dp(N + 1, -inf)
dp[0] = 0
for (int i : (1, N))
    dp[a[i]] = dp.calc_max(0, A[i] - 1) + 1

The segment-max retrieval of a segment tree costs $O(\log N)$ time, so the length of a LIS can be obtained in $O(N \log N)$ time. An auxiliary array enables us to reconstruct a LIS too.

Let \(A\) be the length of a LIS of \(L\). First, we assert that the answer is either \(L\) or \(L + 1\). For example, if we operate with \(x=1, y=A_1\), the resulting length of a LIS achieves \(L\). Also, editing only one element does not increase the length of a LIS by \(2\). Thus, the answer is either \(L\) or \(L + 1\).

Solution 1

We can assume without changing the answer that the operation sets \(A_i\) to \(0\) if \(i=1\) and to \(A_{i - 1} + 1\) if \(i \neq 1\).

Outline of proof

Assume that the answer is $L + 1$. After editing, a length-$(L + 1)$ strictly monotonically increasing subsequence of $A$ should consist of a LIS of $A$ before editing and the edited element. It is sufficient to prove that, conversely, for all LIS of $A$, whether one can obtain a length-$(L + 1)$ strictly monotonically increasing subsequence consisting of the LIS and the edited element regardless of the constraint above.

Consider constructing a length-$(L + 1)$ LIS by appropriately adjusting the "gaps" of a length-$L$ LIS. Here, it immediately turns out that the constraint above on the operation does not matter (although proving it formally is lengthy).

By the fact above, we use the so-called “ear DP”: a type of DP that maintains a constant number of states as one of the keys. For example, one can define DP as:

\(\mathrm{dp}[0][i][j] := \) the maximum length of a strictly monotonically increasing subsequence of the first \(i\) elements, where the \(j\)-th element are the last element picked and the operation is not yet performed;
\(\mathrm{dp}[0][i][j] := \) the maximum length of a strictly monotonically increasing subsequence of the first \(i\) elements, where the \(j\)-th element are the last element picked and the operation is already done.

By implementing this DP in-place (just as the DP to find the length of a LIS), this problem can be solved in a total of \(\mathcal{O}(N \log N)\) time.

Solution 2

For each \(i\), determine if one can make a length-\((L + 1)\) strictly monotonically increasing subsequence.

A natural way to determine it would be like this:

  • For all integers \( x \ (0 \leq x \leq L)\), find the minimum possible value \(a\) that can be the last element of a length-\(x\) strictly monotonically increasing subsequence of \(A[1 : i - 1]\) and the maximum possible value \(b\) that can be the first element of a length-\(x\) strictly monotonically increasing subsequence of \(A[i + 1 : N]\). Determine if \(a + 1 < b\).

Naively implementing it costs \(\Theta(N^2)\) time.

Observe the (in-place) DP to find the length of a LIS. In the transition from \(i\) to \((i + 1)\), only one element of the DP array is modified.

For each \(i\), memorized which element in the DP array was updated by the transition from \(i\) to \(i + 1\). Do the same DP from the back likewise. Based on the memorized information, it can be solved in a total of \(\mathcal{O}(N \log N)\) time.

投稿日時:
最終更新: