Official Analysis (C++)

This solution is $\mathcal{O}(N^2)$ which is faster than the official editorial's but not required since $N \leq 100$.

Explanation

Let $\texttt{dp}[i][j]$ be the the minimum number of changes that must be made to the first $j$ entries so that there are $i$ breakouts among the first $j$ entries.

There are three cases when we calculate the current value of $\texttt{dp}[i][j]$:

• If the log was tampered with and the cows would NOT breakout:

  • Compared to the previous day, the breakout number won't change. However, we need one more change of the log, so we transfer from $\texttt{dp}[i][j-1]$.

    $$\texttt{dp}[i][j]=\texttt{dp}[i][j-1]+1$$

• If the log was tampered with and the cows would breakout (Notice that $a[j] \neq 0$):

  • Compared to the previous day the breakout number increases by 1. We also need one more change of the log, so we transfer from $\texttt{dp}[i-1][j-1]$.

    $$\texttt{dp}[i][j]=\texttt{dp}[i-1][j-1]+1$$

• If the log was NOT tampered with:

  • Then the $i$-th breakout would be on the $(j-a[j])$-th day, so we transfer from $\texttt{dp}[i-1][j-a[j]-1]$.

    $$\texttt{dp}[i][j] = \texttt{dp}[i-1][j-a[j]-1]+\texttt{range\_ans}[j-a[j]][j]);$$

$\texttt{range\_ans}[l][r]$ represents the minimum cost to replace the range $a[l]...a[r]$ with $0...(r-l)$.

Thus, our final DP relation is

Note that if the indices are out of bounds, the value is not considered.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>

using namespace std;

int main() {
	freopen("taming.in", "r", stdin);
	freopen("taming.out", "w", stdout);
	int n;
	cin >> n;
	vector<int> entry(n);

Copy
with open("taming.in", "r") as read:
	n = int(read.readline().strip())
	entry = list(map(int, read.readline().strip().split()))

range_ans = [[0] * n for _ in range(n)]
for i in range(n):
	for j in range(i, n):
		if j > 0:
			range_ans[i][j] = range_ans[i][j - 1] + (0 if entry[j] == j - i else 1)
		else: