Skip to Content
CTRL K

Sleepy Cow Herding

Análisis oficial (C++) 

Solución en video 1

Por Hannah Ying

Nota: La solución en video podría no ser la misma que las otras soluciones. Código en Java.

Video de YouTube (BttHK6QQQTk)

Solución en video 2

Por Melody Yu

Nota: La solución en video podría no ser la misma que las otras soluciones. Código en C++.

Video de YouTube (BvgV7f3pwcI)

Código de la solución en video

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O} (N \log N)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	ifstream cin("herding.in");
	ofstream cout("herding.out");
 
	int n;
	cin >> n;
 
	vector<int> cows(n);
	for (int i = 0; i < n; i++) { cin >> cows[i]; }
 
	sort(cows.begin(), cows.end());
 
	int min_ans = 0;
 
	// dos casos especiales
	if (cows[n - 2] - cows[0] == n - 2 && cows[n - 1] - cows[n - 2] > 2) {
		min_ans = 2;
	} else if (cows[n - 1] - cows[1] == n - 2 && cows[1] - cows[0] > 2) {
		min_ans = 2;
	} else {
		int p1 = 0;
		int p2 = 0;
		int max_range = 0;
		for (p1 = 0; p1 < n; p1++) {
			while (p2 < n - 1 && cows[p2 + 1] - cows[p1] <= n - 1) {
				// seguimos hasta hallar un rango de tamaño n (no índices, sino
				// ubicaciones de vacas)
				p2++;
			}
			int range_size = p2 - p1 + 1;
			max_range = max(max_range, range_size);
		}
		min_ans = n - max_range;
	}
 
	cout << min_ans << endl
	     << max(cows[n - 2] - cows[0], cows[n - 1] - cows[1]) - (n - 2);
}
import java.io.*;
import java.util.*;
 
public class Herding {
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("herding");
 
		int n = io.nextInt();
		int[] cows = new int[n];
		for (int i = 0; i < n; i++) { cows[i] = Integer.parseInt(io.next()); }
 
		Arrays.sort(cows);
 
		int minAns = 0;
		// dos casos especiales
		if (cows[n - 2] - cows[0] == n - 2 && cows[n - 1] - cows[n - 2] > 2) {
			minAns = 2;
		} else if (cows[n - 1] - cows[1] == n - 2 && cows[1] - cows[0] > 2) {
			minAns = 2;
		} else {
			int p1 = 0;
			int p2 = 0;
			int maxRange = 0;
			for (p1 = 0; p1 < n; p1++) {
				while (p2 < n - 1 && cows[p2 + 1] - cows[p1] <= n - 1) {
					// seguimos hasta hallar un rango de tamaño n (no índices, sino
					// ubicaciones de vacas)
					p2++;
				}
				int rangeSize = p2 - p1 + 1;
				maxRange = Math.max(maxRange, rangeSize);
			}
			minAns = n - maxRange;
		}
 
		io.println(minAns);
		io.println(Math.max(cows[n - 2] - cows[0], cows[n - 1] - cows[1]) - (n - 2));
		io.close();
	}
 
	// CodeSnip{Kattio}
}
with open("herding.in") as read:
	n = int(read.readline())
	cows = sorted(int(read.readline()) for _ in range(n))
 
 
min_ans = 0
 
# dos casos especiales
if cows[n - 2] - cows[0] == n - 2 and cows[n - 1] - cows[n - 2] > 2:
	min_ans = 2
elif cows[n - 1] - cows[1] == n - 2 and cows[1] - cows[0] > 2:
	min_ans = 2
else:
	p1 = 0
	p2 = 0
	max_range = 0
	for p1 in range(n):
		while p2 < n - 1 and cows[p2 + 1] - cows[p1] <= n - 1:
			# seguimos hasta hallar un rango de tamaño n (no índices, sino ubicaciones de vacas)
			p2 += 1
		range_size = p2 - p1 + 1
		max_range = max(max_range, range_size)
	min_ans = n - max_range
 
with open("herding.out", "w") as f:
	f.write(
		f"{min_ans}\n{max(cows[n - 2] - cows[0], cows[n - 1] - cows[1]) - (n - 2)}\n"
	)

Solución

Explicación

Mínimo

En general usaremos una técnica de ventana deslizante con dos punteros sobre el arreglo de vacas ordenado para hallar la ventana de longitud−Nlongitud-N que contiene más vacas (es decir, menos espacios vacíos). El valor mínimo es el número de espacios vacíos en esa ventana. Sin embargo, hay un caso borde: si N−1N-1 vacas ya están consecutivas pero la última vaca está lejos, necesitamos 22 movimientos en vez de 11 porque primero hay que cerrar el hueco.

Máximo

Es similar a la versión bronce de este problema. Consideraremos el número total de celdas vacías entre todas las vacas, y luego restaremos el hueco que queremos sacrificar. Aquí, los huecos son (herd[1]−herd[0])(herd[1] - herd[0])y (herd[N−1]−herd[N−2])(herd[N-1] - herd[N-2]). Para obtener el valor máximo, sacrificamos el menor de los dos huecos.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("herding.in", "r", stdin);
 
	int n;
	cin >> n;
	vector<int> herd(n);
	for (int i = 0; i < n; ++i) { cin >> herd[i]; }
	sort(herd.begin(), herd.end());
 
	int min_moves = INT32_MAX;
	if (herd[n - 2] - herd[0] == n - 2 && herd[n - 1] - herd[n - 2] > 2) {
		min_moves = 2;
	} else if (herd[n - 1] - herd[1] == n - 2 && herd[1] - herd[0] > 2) {
		min_moves = 2;
	} else {
		// el mínimo es el parche de longitud n que tiene la menor cantidad de huecos
		int farthest_cow = 0;
		for (int curr_cow = 0; curr_cow < n; ++curr_cow) {
			while (farthest_cow + 1 < n &&
			       herd[farthest_cow + 1] - herd[curr_cow] < n) {
				farthest_cow++;
			}
			min_moves = min(min_moves, n - (farthest_cow - curr_cow + 1));
		}
	}
 
	// calculamos el número de celdas vacías
	int gap_num = 0;
	for (int i = 1; i < n; i++) { gap_num += herd[i] - herd[i - 1] - 1; }
	// el máximo es el máximo del hueco total menos el primer o el último hueco
	int max_moves = max(gap_num - (herd[1] - herd[0] - 1),
	                    gap_num - (herd[n - 1] - herd[n - 2] - 1));
 
	freopen("herding.out", "w", stdout);
	cout << min_moves << '\n' << max_moves << endl;
}
import java.io.*;
import java.util.*;
 
public class Herding {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("herding.in"));
 
		int n = Integer.parseInt(br.readLine());
		int[] herd = new int[n];
		for (int i = 0; i < n; i++) { herd[i] = Integer.parseInt(br.readLine()); }
		Arrays.sort(herd);
		br.close();
 
		int minMoves = Integer.MAX_VALUE;
		if (herd[n - 2] - herd[0] == n - 2 && herd[n - 1] - herd[n - 2] > 2) {
			minMoves = 2;
		} else if (herd[n - 1] - herd[1] == n - 2 && herd[1] - herd[0] > 2) {
			minMoves = 2;
		} else {
			// el mínimo es el parche de longitud n que tiene la menor cantidad de huecos
			int farthestCow = 0;
			for (int currCow = 0; currCow < n; currCow++) {
				while (farthestCow + 1 < n &&
				       herd[farthestCow + 1] - herd[currCow] < n) {
					farthestCow++;
				}
				minMoves = Math.min(minMoves, n - (farthestCow - currCow + 1));
			}
		}
 
		// calculamos el número de celdas vacías
		int gapNum = 0;
		for (int i = 1; i < n; i++) { gapNum += herd[i] - herd[i - 1] - 1; }
		// el máximo es el máximo del hueco total menos el primer o el último
		// hueco
		int maxMoves = Math.max(gapNum - (herd[1] - herd[0] - 1),
		                        gapNum - (herd[n - 1] - herd[n - 2] - 1));
 
		PrintWriter pw = new PrintWriter("herding.out");
		pw.println(minMoves);
		pw.println(maxMoves);
		pw.close();
	}
}
with open("herding.in") as read:
	n = int(read.readline())
	herd = sorted(int(read.readline()) for _ in range(n))
 
min_moves = float("inf")
if herd[n - 2] - herd[0] == n - 2 and herd[n - 1] - herd[n - 2] > 2:
	min_moves = 2
elif herd[n - 1] - herd[1] == n - 2 and herd[1] - herd[0] > 2:
	min_moves = 2
else:
	# el mínimo es el parche de longitud n que tiene la menor cantidad de huecos
	farthest_cow = 0
	for curr_cow in range(n):
		while farthest_cow + 1 < n and herd[farthest_cow + 1] - herd[curr_cow] < n:
			farthest_cow += 1
		min_moves = min(min_moves, n - (farthest_cow - curr_cow + 1))
 
# calculamos el número de celdas vacías
gap_num = 0
for curr_cow in range(1, n):
	gap_num += herd[curr_cow] - herd[curr_cow - 1] - 1
# el máximo es el máximo del hueco total menos el primer o el último hueco
max_moves = max(
	gap_num - (herd[1] - herd[0] - 1), gap_num - (herd[n - 1] - herd[n - 2] - 1)
)
 
print(min_moves, max_moves, sep="\n", file=open("herding.out", "w"))
Fundamentos