Structure of the Optimal Solution

We may assume that the second operation is only performed after performing all of the first operations.

Let us say you perform the first operation \(L\) times, and in the \(i\)-th usage of the first operation, you swap the \(p_i\)-th and \((p_i+1)\)-th elements of \(A\). There exists an optimal solution such that for every \(1 \leq i < j \leq L\), we have \(|p_i - p_j| \geq 2\). In other words, there is an optimal solution where each element of \(A\) is swapped at most once. Also, in this case, the final sequence obtained does not depend on the order in which you perform the first operations.

Hence, we can devise the following dynamic programming:

• Let \(dp(0,i)\) be the minimum total number of operations needed to make \((A_1,\dots,A_i)\) empty, under the condition that you do not swap \(A_{i-1}\) and \(A_i\) in the first operation.
• Let \(dp(1,i)\) be the minimum total number of operations needed to make \((A_1,\dots,A_i)\) empty, under the condition that you do swap \(A_{i-1}\) and \(A_i\) in the first operation.

The overall complexity is \(\mathrm{O}(N)\).

Proof

We prove that there exists an optimal solution in which each element of \(A\) is swapped at most once.

Let \(p = (p_1,\dots,p_L)\) be the sequence of positions where you apply the first operation, so that in the \(i\)-th operation you swap \(A_{p_i}\) and \(A_{p_i+1}\). Denote by \(A(p)\) the sequence obtained after these swaps. For a sequence \(B = (B_1,\dots,B_N)\), let \(f(B)\) be the minimum number of second operations required to make \(B\) empty (using only the second operation). We have \(f(B) - 1\) equals the number of indices \(i\) such that \(B_i \neq B_{i+1}\). Then, the answer to the problem is the minimum of \(|p| + f(A(p))\) over all sequences \(p\), where \(|p|\) is the length of \(p\).

We shall show that among the \(p\) minimizing \(|p| + f(A(p))\), there is one satisfying \(|p_i - p_j| \geq 2\) for all \(1 \leq i < j \leq |p|\). To do so, we prove the following lemma:

If \(p\) contains indices \(p_i,p_j\) with \(1 \leq i < j \leq |p|\) such that \(|p_i - p_j| \leq 1\), then there exists another sequence \(q\) such that \(|q| < |p|\) and \(|q| + f(A(q)) \leq |p| + f(A(p))\).

Once this lemma is established, if we take a \(p\) that minimizes \(|p| + f(A(p))\) with minimal \(|p|\), it follows that \(|p_i - p_j| \geq 2\) for all \(1 \leq i < j \leq |p|\).

Proof of the Lemma

Take any \(p\) that satisfies the lemma’s condition. Construct an undirected graph \(G(p)\) with \(N\) vertices labeled \(1, \dots, N\) and an edge between vertices \(p_i\) and \(p_i+1\) for each \(1\leq i\leq |p|\). Note that \(G(p)\) may have multi-edges. By the lemma’s assumption, \(G(p)\) has a connected component with at least three vertices. Because each connected component’s vertex labels form a consecutive interval, let that component’s vertices be \(x, x+1, \dots, x+K-1\), with \(K \geq 3\). Also, swaps involving different connected components can be done in any order without affecting the final sequence, so we may assume that all \(p_i\) with \(x \leq p_i \leq x+K-2\) are placed at the end of \(p\). That is, we may assume there is an \(X\) such that

• For each \(i\) \((1\leq i \leq |p|-X)\), \(p_i \leq x-2\) or \(p_i \geq x+K\),
• For each \(i\) \((|p|-X+1 \leq i \leq |p|)\), \(x \leq p_i \leq x+K-2\).

Let \(p' = (p_1,\dots,p_{|p|-X})\). Then, from the connectivity of \(x,\dots,x+K-1\) in \(G(p)\), we get

\[ |p'|-|p| = -X \leq -K+1. \]

If \(A_x = A_{x+1} = \dots = A_{x+K-1}\) in the original array, then \(A(p) = A(p')\), so the lemma follows by letting \(q = p'\). Otherwise, consider the case where there are at least two distinct elements among \(A_x,A_{x+1},\dots,A_{x+K-1}\).

Consider the case where \(2 \leq x\) and \(x+K-1 \leq N-1\). Let \(B = A(p)\) and \(B' = A(p')\). Then, \(B\) and \(B'\) differ only in the segment from the \(x\)-th to the \((x+K-1)\)-th elements. Thus,

\[ \begin{aligned} f(A(p')) - f(A(p)) &= f(B') - f(B)\\ &= \sum_{i=x-1}^{x+K-1}1_{B'_i\neq B'_{i+1}} - \sum_{i=x-1}^{x+K-1}1_{B_i\neq B_{i+1}}\\ &\leq (K+1) - 1\\ &= K, \end{aligned} \]

where \(1_{B_i \neq B_{i+1}}\) is \(1\) if \(B_i \neq B_{i+1}\) and \(0\) otherwise (and similarly for \(1_{B'_i\neq B'_{i+1}}\)). If \(f(A(p')) - f(A(p)) \leq K-1\), then \(|p'| + f(A(p')) \leq |p| + f(A(p))\), so the lemma follows by letting \(q = p'\). If \(f(A(p')) - f(A(p)) = K\), then both of the following hold:

\[ \sum_{i=x-1}^{x+K-1}1_{B'_i\neq B'_{i+1}} = K+1,~\sum_{i=x-1}^{x+K-1}1_{B_i\neq B_{i+1}} = 1. \]

Hence, there exist distinct integers \(\alpha\) and \(\beta\) such that

\[ \begin{aligned} (B'_{x-1},B'_x,\dots,B'_{x+K}) &= (\alpha,\beta,\alpha,\beta,\dots,\alpha,\beta),\\ (B_{x-1},B_x,\dots,B_{x+K}) &= (\alpha,\alpha,\dots,\alpha,\beta,\beta,\dots,\beta). \end{aligned} \]

If we form \(q\) by appending \(x\) to the end of \(p'\), then

\[ |q| - |p'| = 1,~ f(A(q))-f(A(p')) = -2, \]

so

\[ \begin{aligned} |q| + f(A(q)) - (|p| + f(A(p))) &= |q| + f(A(q)) - (|p'| + f(A(p'))) + |p'| + f(A(p')) - (|p| + f(A(p)))\\ &\leq -1 + (-K+1) + K\\ &= 0. \end{aligned} \]

Also, \(K \geq 3\) implies \(|q| - |p| = |p'| - |p| + 1\leq -K+2\leq -1\), so \(q\) satisfies the lemma.

If \(x=1\) or \(x+K-1 = N\), we have \(f(A(p')) - f(A(p)) \leq K-1\), so \(q = p'\) satisfies the lemma.

Thus, the lemma is proved.