Skip to Content
CTRL K

Taming the Herd

Análisis oficial (C++) 

Esta solución es O(N2)\mathcal{O}(N^2), más rápida que la del editorial oficial, pero no es necesaria ya que N≤100N \leq 100.

Explicación

Sea dp[i][j]\texttt{dp}[i][j] el número mínimo de cambios que se deben hacer en las primeras jj entradas para que haya ii fugas entre las primeras jj entradas.

Hay tres casos cuando calculamos el valor actual de dp[i][j]\texttt{dp}[i][j]:

  • Si el registro fue alterado y las vacas NO se fugarían:

    • Comparado con el día anterior, el número de fugas no cambia. Sin embargo, necesitamos un cambio más del registro, así que transferimos desde dp[i][j−1]\texttt{dp}[i][j-1]. dp[i][j]=dp[i][j−1]+1 \texttt{dp}[i][j]=\texttt{dp}[i][j-1]+1

  • Si el registro fue alterado y las vacas se fugarían (nótese que a[j]≠0a[j] \neq 0):

    • Comparado con el día anterior, el número de fugas aumenta en 1. También necesitamos un cambio más del registro, así que transferimos desde dp[i−1][j−1]\texttt{dp}[i-1][j-1]. dp[i][j]=dp[i−1][j−1]+1 \texttt{dp}[i][j]=\texttt{dp}[i-1][j-1]+1

  • Si el registro NO fue alterado:

    • Entonces la ii-ésima fuga sería en el (j−a[j])(j-a[j])-ésimo día, así que transferimos desde dp[i−1][j−a[j]−1]\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] representa el costo mínimo de reemplazar el rango a[l]...a[r]a[l]...a[r] por 0...(r−l)0...(r-l).

Así, nuestra relación de DP final es

\texttt{dp}[i][j] = \min\begin{cases} \texttt{dp}[i][j-1]+1\\ \texttt{dp}[i-1][j-1]+1\\ \texttt{dp}[i-1][j-a[j]-1] + \texttt{range\\_ans}[j-a[j]][j]) \end{cases}

Nótese que si los índices están fuera de rango, el valor no se considera.

Implementación

Complejidad temporal: O(N2)\mathcal{O}(N^2)

#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);
	for (int i = 0; i < n; i++) { cin >> entry[i]; }
 
	vector<vector<int>> range_ans(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			if (j) {
				range_ans[i][j] = range_ans[i][j - 1] + (entry[j] == j - i ? 0 : 1);
			} else {
				range_ans[i][j] = (entry[j] == j - i ? 0 : 1);
			}
		}
	}
 
	vector<vector<int>> dp(n + 1, vector<int>(n, INT32_MAX));
	for (int i = 1; i <= n; i++) {
		for (int j = i - 1; j < n; j++) {
			if (!j) {
				if (entry[j] == 0) {
					dp[i][j] = 0;
				} else {
					dp[i][j] = 1;
				}
				continue;
			}
 
			// Case 1
			if (dp[i][j - 1] != INT32_MAX) { dp[i][j] = dp[i][j - 1] + 1; }
 
			// Case 2
			if (entry[j] && dp[i - 1][j - 1] != INT32_MAX) {
				dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
			}
 
			// Case 3
			if (j - entry[j] - 1 >= 0 && dp[i - 1][j - entry[j] - 1] != INT32_MAX) {
				dp[i][j] = min(dp[i][j], dp[i - 1][j - entry[j] - 1] +
				                             range_ans[j - entry[j]][j]);
			}
			if (j - entry[j] == 0 && i == 1) {
				dp[i][j] = min(dp[i][j], range_ans[j - entry[j]][j]);
			}
		}
	}
 
	for (int i = 1; i <= n; i++) { cout << dp[i][n - 1] << endl; }
}
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:
			range_ans[i][j] = 0 if entry[j] == j - i else 1
 
dp = [[float("inf")] * n for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(i - 1, n):
		if j == 0:
			dp[i][j] = 0 if entry[j] == 0 else 1
			continue
 
		# Case 1
		if dp[i][j - 1] != float("inf"):
			dp[i][j] = dp[i][j - 1] + 1
 
		# Case 2
		if entry[j] and dp[i - 1][j - 1] != float("inf"):
			dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
 
		# Case 3
		if j - entry[j] - 1 >= 0 and dp[i - 1][j - entry[j] - 1] != float("inf"):
			dp[i][j] = min(
				dp[i][j], dp[i - 1][j - entry[j] - 1] + range_ans[j - entry[j]][j]
			)
 
		if j - entry[j] == 0 and i == 1:
			dp[i][j] = min(dp[i][j], range_ans[j - entry[j]][j])
 
with open("taming.out", "w") as out:
	for i in range(1, n + 1):
		out.write(f"{dp[i][n - 1]}\n")
Fundamentos