Taming the Herd

Pista

Si algún registro del log de Farmer John está fijado, ¿qué otros registros deben quedar fijados?

Solución

Explicación

Primero observamos que si el contador marcó un número positivo $X$ en algún día, entonces el contador debió haber sido $X - 1$ el día anterior.

Por lo tanto, podemos iterar hacia atrás desde el último día y aplicar esta regla para completar las entradas faltantes. Si intentamos completar una entrada que no faltaba, entonces o no pasa nada (completamos la entrada con $Y$ , pero la entrada ya decía $Y$ ), o llegamos a una contradicción.

La primera entrada del log es un caso especial, ya que Farmer John ya sabe que las vacas se escaparon ese día. Así, si la entrada falta, podemos poner automáticamente el número en $0$ . Si obtenemos que el número es positivo, llegamos a una contradicción.

Si alguna vez llegamos a una contradicción, entonces el log es necesariamente inconsistente, y simplemente podemos imprimir $-1$ como respuesta.

En caso contrario, el log debe contener varias rachas $0, 1, \dots, k$ de distintas longitudes, posiblemente con algunos $-1$ s entre rachas. Sabemos que la primera racha empieza el primer día.

Supongamos que hay $S$ rachas y $M$ entradas que todavía faltan. Para minimizar la cantidad de fugas, podemos completar cada secuencia de entradas faltantes consecutivas de modo que continúe la racha que la precede. Así, esto hace que el mínimo de fugas sea $S$ .

Para maximizar la cantidad de fugas, podemos tener una fuga en cada uno de los $M$ días cuya entrada falta, haciendo que el máximo de fugas sea $S + M$ .

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++JavaPython


#include <bits/stdc++.h>
 
 
using namespace std;
 
int main() {
	freopen("taming.in", "r", stdin);
	freopen("taming.out", "w", stdout);
	int n;
	cin >> n;
 
	/*
	 * Un estado de 2 significa que hubo una fuga el día n.
	 * Un estado de 1 significa que no hubo una fuga el día n.
	 * Un estado de 0 significa que no estamos seguros de qué pasó el día n.
	 */
	vector<int> status(n, 0);
	vector<int> log(n);  // log de cada día
	for (int i = 0; i < n; i++) { cin >> log[i]; }
	bool valid = true;
	if (log[0] == 1) {
		valid = false;  // encontramos una discrepancia
	} else {
		status[0] = 2;  // el problema dice que el primer día hubo una fuga
	}
 
	for (int i = 1; i < n; i++) {
		if (!valid) { break; }
		if (log[i] == -1) {
			continue;  // no tenemos log para este día, así que pasamos al
			           // siguiente día
		} else if (log[i] == 0) {
			status[i] = 2;  // esto significa que hay una fuga este día
		} else {
			// ahora procesamos los log[i] días, buscando discrepancias en
			// el camino
			status[i] = 1;  // el día actual no tiene fuga
			int curr_index = i - 1;
			log[i]--;
			while (log[i] > 0 && curr_index > -1) {
				if (status[curr_index] == 0 || status[curr_index] == 1) {
					status[curr_index] = 1;
				} else {
					// encontramos una discrepancia
					valid = false;
					break;
				}
				log[i]--;
				curr_index--;
			}
 
			// comprobamos el día en que el log actual dice que hubo una fuga
			if (curr_index > -1 &&
			    (status[curr_index] == 0 || status[curr_index] == 2)) {
				status[curr_index] = 2;
			} else {
				valid = false;  // encontramos una discrepancia
			}
		}
	}
 
	int min_ans = 0;
	int max_ans = 0;
	if (valid) {
		for (int i : status) {
			if (i == 2) {
				// los días con estado 2 son fugas, así que cuentan en
				// ambas respuestas
				min_ans++;
				max_ans++;
			} else if (i == 0) {
				max_ans++;
			}
		}
		cout << min_ans << " " << max_ans << "\n";
	} else {
		cout << -1 << "\n";  // no hay una secuencia válida
	}
}


import java.io.*;
import java.util.*;
 
public class Taming {
	public static void main(String[] args) {
		Kattio io = new Kattio("taming");
		int n = io.nextInt();
		int[] log = new int[n];
		for (int i = 0; i < n; i++) { log[i] = io.nextInt(); }
		/*
		 * La primera entrada del log es un caso especial,
		 * ya que Farmer John ya sabe que las vacas se escaparon ese día.
		 */
		if (log[0] > 0) {
			io.println(-1);
			io.close();
			System.exit(0);
		}
		// Si es una entrada faltante, podemos ponerla en 0.
		log[0] = 0;
		int t = -1;
		int req = 0;
		int pos = 0;
		/*
		 * Si alguna vez encontramos una contradicción, entonces el
		 * log es necesariamente inconsistente, así que podemos imprimir −1.
		 * En caso contrario, el log debe consistir en varias rachas 0,1,2,…,k
		 * de distintas longitudes, posiblemente con algunos −1s entre
		 * rachas: entradas que no pudimos deducir de forma única.
		 * Sabemos que la primera racha empieza el primer día.
		 */
		for (int i = n - 1; i >= 0; i--) {
			if (t != -1 && log[i] != -1 && log[i] != t) {
				io.println(-1);
				io.close();
				System.exit(0);
			}
			if (t == -1) { t = log[i]; }
			if (log[i] == -1) { log[i] = t; }
			if (log[i] == 0) { req++; }
			if (log[i] == -1) { pos++; }
			if (t > -1) { t--; }
		}
		int sum = req + pos;
		io.println(req + " " + sum);
		io.close();
	}
	// CodeSnip{Kattio}
}


fin = open("taming.in", "r")
fout = open("taming.out", "w")
 
inputs = [str(i) for i in fin.read().splitlines()]
days = int(inputs[0])
entry = [int(i) for i in inputs[1].split(" ")]
 
time = -1  # Lleva los días restantes en los que está garantizado que hay 0 fugas
outbreaks = 0  # Cuenta la cantidad de fugas que deben ocurrir
potential = 0  # Cuenta la cantidad de fugas que pueden ocurrir potencialmente
valid = True  # Comprueba si la entrada es válida
 
# Si la primera entrada es mayor que 0, entonces hay una contradicción
if entry[0] > 0:
	valid = False
else:
	entry[0] = 0
 
"""
Si alguna vez encontramos una contradicción, entonces el
log es necesariamente inconsistente, así que podemos imprimir −1.
En caso contrario, el log debe consistir en varias rachas 0,1,2,…,k
de distintas longitudes, posiblemente con algunos −1s entre
rachas: entradas que no pudimos deducir de forma única.
Sabemos que la primera racha empieza el primer día.
"""
for day in range(days - 1, -1, -1):
	if time != -1 and entry[day] != -1 and entry[day] != time:
		valid = False
		break
	if time == -1:
		time = entry[day]
	if entry[day] == -1:
		entry[day] = time
	if entry[day] == 0:
		outbreaks += 1
	if entry[day] == -1:
		potential += 1
	if time > -1:
		time -= 1
 
if valid:
	print(outbreaks, outbreaks + potential, file=fout)
else:
	print(-1, file=fout)

Solución en video

Por Jay Fu

Video de YouTube (f_Otluj98kM)

Código de la solución en video

C++Java


#include <algorithm>
#include <cstdio>
#include <iostream>
 
 
using namespace std;
 
const int MAXN = 100000;
 
int N;
int A[MAXN];
 
int main() {
	freopen("taming.in", "r", stdin);
	freopen("taming.out", "w", stdout);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	if (A[0] > 0) {
		cout << -1 << '\n';
		return 0;
	}
	A[0] = 0;
	int t = -1;
	int req = 0;
	int pos = 0;
	for (int i = N - 1; i >= 0; i--) {
		if (t != -1 && A[i] != -1 && A[i] != t) {
			cout << -1 << '\n';
			return 0;
		}
		if (t == -1) t = A[i];
		if (A[i] == -1) A[i] = t;
		if (A[i] == 0) req++;
		if (A[i] == -1) pos++;
		if (t > -1) t--;
	}
	cout << req << ' ' << req + pos << '\n';
}


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
 
public class taming {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("taming.in"));
		PrintWriter out = new PrintWriter("taming.out");
		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];
		StringTokenizer s = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) { A[i] = Integer.parseInt(s.nextToken()); }
		if (A[0] > 0) {
			out.println(-1);
			return;
		}
		A[0] = 0;
		int t = -1;
		int req = 0;
		int pos = 0;
		for (int i = N - 1; i >= 0; i--) {
			if (t != -1 && A[i] != -1 && A[i] != t) {
				out.println(-1);
				out.close();
				return;
			}
			if (t == -1) t = A[i];
			if (A[i] == -1) A[i] = t;
			if (A[i] == 0) req++;
			if (A[i] == -1) pos++;
			if (t > -1) t--;
		}
		out.println(req + " " + (req + pos));
		out.close();
	}
}