Official

D - Inc, Dec - Decomposition Editorial by evima

We will explain two approaches.

  1. \(\Theta(N\log N)\) solution by accelerating DP: https://atcoder.jp/contests/arc123/editorial/2318
  2. \(\Theta(N)\) solution by examining the structure of the optimal solution: this article

In this article, we multiply every term of the sequence \(C\) by \(-1\) and call the resulting sequence \(C\). That is, we assume that the problem is about non-decreasing sequences \(B\) and \(C\) such that \(A_i = B_i - C_i\).

◆ The structure of the optimal solution

We can show the following.

【Lemma】 There exists an optimal solution \((B, C)\) such that \(B_i =B_{i+1}\) or \(C_i = C_{i+1}\) holds for every \(1\leqq i \leqq N - 1\).

Let us prove this. Among the optimal solutions \((B, C)\), we take the one with the minimum \(B_N - B_1\). Assume that \(B_n < B_{n+1}\) and \(C_n < C_{n+1}\) holds for every \(1\leqq n \leqq N-1\), and let us derive a contradiction.

Consider the following two kinds of operations.

  • Operation \(\operatorname{prefix}_+\): add \(1\) to each of \(B_1, \ldots, B_n\) and \(C_1, \ldots, C_{n}\).
  • Operation \(\operatorname{suffix}_-\): add \(-1\) to each of \(B_{n+1}, \ldots, B_N\) and \(C_{n+1}, \ldots, C_N\).

These operations decrease \(B_N - B_1\) by \(1\) while maintaining the non-decreasingness of \(B\) and \(C\) and the condition \(A_i = B_i - C_i\). Thus, if we can show that one of the two operations maintains the optimality (the minimumness of \(\sum (|B_i| + |C_i|)\)), we are done.

We can see the following:

  • if \(B_n < 0\): \(\operatorname{prefix}_+\) maintains the optimality;
  • if \(0< B_{n+1}\): \(\operatorname{suffix}_-\) maintains the optimality.

Actually, if \(B_n < 0\), we have \(B_i < 0\) for \(1\leqq i\leqq n\). \(\operatorname{prefix}_+\) on such \(i\) will decrease \(|B_i|\) by \(1\) and increase \(|C_i\) by at most \(1\), so we are done. The same goes for the case \(0 < B_{n+1}\).

Since we have assumed that \(B_n < B_{n+1}\), these cases are exhaustive. Thus, we have proved the Lemma.

◆ Computing the answer.

From the Lemma, we only need to consider \((B, C)\) such that \(B_i =B_{i+1}\) or \(C_i = C_{i+1}\) holds, where we have the following:

  • \(B_{i+1} = B_i + \max(0, A_{i+1} - A_i)\);
  • \(C_{i+1} = C_i + \max(0, A_i - A_{i+1})\).

From these properties and \(A_1 = B_1 - C_1\), all \(B_i\) and \(C_i\) will be uniquely determined when \(B_1\) is determined. By letting \(x = B_1\), we end up with a problem in the following form.

Given are \(2N\) integers \(p_1, \ldots, p_{2N}\). Find the minimum value of \(\sum_{i=1}^{2N}|x - p_i|\) for an integer \(x\).

We can solve this problem in \(\Theta(N)\) time by computing the median.

◆ Sample Implementation

posted:
last update: