Angry Cows

Pista 1

Supongamos que ya sabemos que cierto valor de $R$ no puede detonar todos los fardos; ¿qué dice esto sobre todos los valores de $R$ menores que el valor actual de $R$ ? Del mismo modo, si sabemos que cierto valor de $R$ sí puede detonar todo, ¿qué dice esto sobre todos los valores de $R$ mayores que el valor actual?

Pista 2

Si un cierto valor de $R$ no funciona, todos los valores menores que ese tampoco funcionarán. De forma similar, si un valor de $R$ funciona, todos los valores mayores que ese también funcionarán. ¿Qué algoritmo aprovecha esta propiedad?

Solución

Explicación

Notemos que para cualquier radio de explosión $x$ , si $x$ no puede detonar todos los fardos cuando se dispara de forma eficiente, entonces ningún radio de explosión menor que $x$ podrá tampoco. Así, podemos hacer búsqueda binaria del radio de explosión mínimo que puede detonar todos los fardos.

Solo necesitamos probar si un radio de explosión dado detonará todos los fardos, lo que se puede hacer calculando el número mínimo de vacas necesarias para hacerlo con un radio de explosión dado, y comparándolo con el número total de vacas que tenemos ( $k$ ).

Ordenamos la lista de fardos de heno por posición creciente para determinar fácilmente si un fardo explotó o no. Consideremos el primer fardo (el más a la izquierda). Necesitamos una vaca para detonar este fardo, y siempre es más eficiente colocar la explosión de esta vaca lo más a la derecha posible, para detonar la máxima cantidad de otros fardos. Así, la posición de la explosión sería cow position + radius.

Esto se puede aplicar a cada fardo de heno. Recorremos la lista ordenada de fardos y detonamos cada uno, guardando el número de vacas necesarias y la posición de la última explosión. Si el fardo actual está en el radio de la última explosión, el fardo ya está detonado. Si no, necesitamos una vaca más para detonar el fardo actual, y reubicamos de forma óptima la última explosión.

Implementación

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

C++JavaPython


#include <algorithm>
#include <climits>
#include <fstream>
#include <iostream>
#include <vector>
 
/**
 * Prueba si todos los fardos pueden volar con el radio de explosión indicado.
 * Calcula el número total de vacas necesarias para volar todos los fardos con
 * el radio de explosión indicado. Si el número es menor o igual que el
 * número real de vacas que tenemos, entonces es posible. En caso contrario, no.
 * @param blast_radius: El radio de explosión propuesto a probar.
 * @return true si es posible volar todos los fardos, false en caso contrario
 */
bool valid_blast_radius(int blast_radius, int k, std::vector<int> &bales) {
	int last_blast_location = INT_MIN;
	int needed_cows = 0;
	for (int bale_position : bales) {
		/*
		 * Si el fardo actual está fuera del radio de explosión de la última vaca,
		 * necesitamos usar una vaca nueva.
		 */
		if (std::abs(bale_position - last_blast_location) > blast_radius) {
			needed_cows += 1;
 
			/*
			 * Siempre es más eficiente colocar la explosión de la vaca actual
			 * donde el nuevo fardo que se vuela queda exactamente en el borde izquierdo
			 */
			last_blast_location = bale_position + blast_radius;
 
			if (needed_cows > k) { return false; }
		}
	}
	return true;
}
 
int main() {
	std::ifstream cin("angry.in");
	int n, k;
	cin >> n >> k;
 
	std::vector<int> bales(n);
	for (int i = 0; i < n; i++) { cin >> bales[i]; }
 
	std::sort(begin(bales), end(bales));
 
	int left = 0;
	int right = bales[n - 1] - bales[0];
	while (left < right) {
		int mid = (left + right) / 2;
		if (valid_blast_radius(mid, k, bales)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
 
	std::ofstream("angry.out") << left << std::endl;
}


import java.io.*;
import java.util.*;
 
public class AngryCows {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("angry");
		int n = io.nextInt();
		int k = io.nextInt();
 
		int[] bales = new int[n];
		for (int i = 0; i < n; i++) { bales[i] = io.nextInt(); }
 
		Arrays.sort(bales);
		int left = 0;
		int right = bales[n - 1] - bales[0];
 
		while (left < right) {
			int mid = (left + right) / 2;
			if (validBlastRadius(mid, k, bales)) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
 
		io.println(left);
		io.close();
	}
 
	/**
	 * Prueba si todos los fardos pueden volar con el radio de explosión indicado.
	 * Calcula el número total de vacas necesarias para volar todos los fardos con
	 * el radio de explosión indicado. Si el número es menor o igual que el
	 * número real de vacas que tenemos, entonces es posible. En caso contrario, no.
	 * @param blast_radius: El radio de explosión propuesto a probar.
	 * @return true si es posible volar todos los fardos, false en caso contrario
	 */
	private static boolean validBlastRadius(int blastRadius, int k, int bales[]) {
		int lastBlastLocation = Integer.MIN_VALUE;
		int neededCows = 0;
 
		for (int balePosition : bales) {
 
			/**
			 *Si el fardo actual está fuera del radio de explosión de la última vaca,
			 *necesitamos usar una vaca nueva.
			 */
 
			if (Math.abs(balePosition - lastBlastLocation) > blastRadius) {
				neededCows += 1;
 
				/**
				 *Siempre es más eficiente colocar la explosión de la vaca actual
				 *donde el nuevo fardo que se vuela queda exactamente en el borde izquierdo
				 */
				lastBlastLocation = balePosition + blastRadius;
 
				if (neededCows > k) { return false; }
			}
		}
 
		return true;
	}
 
	// CodeSnip{Kattio}
}


with open("angry.in", "r") as infile:
	n, k = map(int, infile.readline().split())
	bales = [int(infile.readline()) for _ in range(n)]
	bales.sort()
 
 
def valid_blast_radius(blast_radius: int) -> bool:
	"""
	Prueba si todos los fardos pueden volar con el radio de explosión indicado.
 
	Calcula el número total de vacas necesarias para volar todos los fardos con
	el radio de explosión indicado. Si el número es menor o igual que el
	número real de vacas que tenemos, entonces es posible. En caso contrario, no.
 
	:param blast_radius: El radio de explosión propuesto a probar.
	:return: True si es posible volar todos los fardos, False en caso contrario
	"""
 
	last_blast_location = -float("inf")
	needed_cows = 0
	for bale_position in bales:
 
		# Si el fardo actual está fuera del radio de explosión de la última vaca,
		# necesitamos usar una vaca nueva.
		if abs(bale_position - last_blast_location) > blast_radius:
			needed_cows += 1
 
			# Siempre es más eficiente colocar la explosión de la vaca actual
			# donde el nuevo fardo que se vuela queda exactamente en el borde izquierdo.
			last_blast_location = bale_position + blast_radius
 
			if needed_cows > k:
				return False
 
	return True
 
 
left, right = 0, bales[-1] - bales[0]
 
while left < right:
	mid = (left + right) // 2
	if valid_blast_radius(mid):
		right = mid
	else:
		left = mid + 1
 
print(left, file=open("angry.out", "w"))