Angry Cows

Solución en video

Por David Zhou

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

Solución en video

Video de YouTube (Xdj-OybMSYM)

Pista 1

En problemas donde se nos pide minimizar/maximizar algún valor, podemos hacernos estas preguntas:

¿Cómo cambia la “validez” de la respuesta a medida que la aumentamos/disminuimos?
¿Qué condiciones deben cumplirse en una solución óptima?

Respuesta a la pista 1

Notemos que la potencia mínima con la que lanzamos una vaca es monótona, ya que hay un punto fijo a partir del cual valores más chicos de $R$ dejan de funcionar.

Esto implica una búsqueda binaria sobre la potencia $R$ .

Solución

Análisis oficial (C++ y Java)

Explicación

A partir de las pistas, empezamos a hacer búsqueda binaria sobre la potencia inicial $R$ . Ahora, redujimos el problema a comprobar si una potencia fija $R$ funciona para nuestro conjunto de fardos de heno.

Hay muchas formas de encararlo (ver el Análisis oficial para más información), pero quizás la más directa es hacer una segunda búsqueda binaria sobre el punto máximo en el que podemos colocar nuestra vaca.

Esto funciona porque, al igual que con la potencia, existe un punto fijo a partir del cual una vaca lanzada en una coordenada no derribará todos los fardos a la izquierda/derecha. Como $N \leq 5 \cdot 10^4$ , podemos simular estas explosiones de forma naive.

Implementación

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

C++JavaPython


#include <algorithm>
#include <climits>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
 
int n;
vector<int> haybales;
 
bool valid(int pos, int idx, int power, int dir) {
	// explotó el fardo más a la izquierda
	if (idx <= 0 && dir == 0) { return (idx < 0 || pos - power <= haybales[idx]); }
 
	// explotó el fardo más a la derecha
	if (idx >= n - 1 && dir == 1) { return idx >= n || pos + power >= haybales[idx]; }
 
	if (dir == 0) {  // izquierda
		if (pos - power <= haybales[0]) { return true; }
 
		// ir tan a la izquierda como sea posible
		int next_idx = idx;
		while (next_idx >= 0 && pos - power <= haybales[next_idx]) { next_idx--; }
 
		// no es posible más movimiento
		if (next_idx == idx) { return false; }
 
		return valid(haybales[next_idx + 1], next_idx, power - 2, dir);
	} else {  // derecha
		if (pos + power >= haybales[n - 1]) { return true; }
 
		// ir tan a la derecha como sea posible
		int next_idx = idx;
		while (next_idx < n && haybales[next_idx] <= pos + power) { next_idx++; }
 
		// no es posible más movimiento
		if (next_idx == idx) { return false; }
 
		return valid(haybales[next_idx - 1], next_idx, power - 2, dir);
	}
 
	return false;
}
 
int main() {
	freopen("angry.in", "r", stdin);
	freopen("angry.out", "w", stdout);
 
	cin >> n;
	haybales.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> haybales[i];
		haybales[i] *= 2;  // duplicar cada posición para eliminar decimales
	}
	sort(haybales.begin(), haybales.end());
 
	int l = 0, r = INT_MAX;
	while (l <= r) {
		int power = (r - l) / 2 + l;
 
		// encontrar el fardo más a la derecha que todavía puede alcanzar la izquierda
		int pos_l = 0, pos_r = INT_MAX;
		while (pos_l <= pos_r) {
			int pos = (pos_r - pos_l) / 2 + pos_l;
 
			// índice del fardo candidato
			int idx =
			    lower_bound(haybales.begin(), haybales.end(), pos) - haybales.begin();
 
			// ¿podemos explotar todos los fardos a la izquierda?
			if (idx < n && valid(pos, idx, power, 0)) {
				pos_l = pos + 1;
			} else {
				pos_r = pos - 1;
			}
		}
 
		int idx =
		    upper_bound(haybales.begin(), haybales.end(), pos_l) - haybales.begin();
 
		// ¿podemos explotar todos los fardos a la derecha?
		if (valid(pos_l, idx, power, 1)) {
			r = power - 1;
		} else {
			l = power + 1;
		}
	}
	cout << fixed << setprecision(1) << (double)l / 2.0 << endl;
}


import java.io.*;
import java.util.*;
 
public class Main {
	static int n;
	static int[] haybales;
 
	static boolean valid(int pos, int idx, int power, int dir) {
		// explotó el fardo más a la izquierda
		if (idx <= 0 && dir == 0) { return (idx < 0 || pos - power <= haybales[idx]); }
 
		// explotó el fardo más a la derecha
		if (idx >= n - 1 && dir == 1) {
			return idx >= n || pos + power >= haybales[idx];
		}
 
		if (dir == 0) {  // izquierda
			if (pos - power <= haybales[0]) { return true; }
 
			// ir tan a la izquierda como sea posible
			int next_idx = idx;
			while (next_idx >= 0 && pos - power <= haybales[next_idx]) { next_idx--; }
 
			// no es posible más movimiento
			if (next_idx == idx) { return false; }
 
			return valid(haybales[next_idx + 1], next_idx, power - 2, dir);
		} else {  // derecha
			if (pos + power >= haybales[n - 1]) { return true; }
 
			// ir tan a la derecha como sea posible
			int next_idx = idx;
			while (next_idx < n && haybales[next_idx] <= pos + power) { next_idx++; }
 
			// no es posible más movimiento
			if (next_idx == idx) { return false; }
 
			return valid(haybales[next_idx - 1], next_idx, power - 2, dir);
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("angry.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("angry.out"));
 
		n = Integer.parseInt(br.readLine());
		haybales = new int[n];
		for (int i = 0; i < n; i++) {
			// duplicar cada posición para eliminar decimales
			haybales[i] = Integer.parseInt(br.readLine()) * 2;
		}
		Arrays.sort(haybales);
		int l = 0, r = Integer.MAX_VALUE;
		while (l <= r) {
			int power = (r - l) / 2 + l;
 
			// encontrar el fardo más a la derecha que todavía puede alcanzar la izquierda
			int pos_l = 0, pos_r = Integer.MAX_VALUE;
			while (pos_l <= pos_r) {
				int pos = (pos_r - pos_l) / 2 + pos_l;
 
				// índice del fardo candidato
				int idx = Arrays.binarySearch(haybales, pos);
				if (idx < 0) { idx = -idx - 1; }
 
				// ¿podemos explotar todos los fardos a la izquierda?
				if (idx < n && valid(pos, idx, power, 0)) {
					pos_l = pos + 1;
				} else {
					pos_r = pos - 1;
				}
			}
 
			int idx = Arrays.binarySearch(haybales, pos_l);
			if (idx < 0) {
				idx = -idx - 1;
			} else {
				while (idx < n && haybales[idx] == pos_l) { idx++; }
			}
 
			// ¿podemos explotar todos los fardos a la derecha?
			if (valid(pos_l, idx, power, 1)) {
				r = power - 1;
			} else {
				l = power + 1;
			}
		}
		pw.printf("%.1f\n", (double)l / 2.0);
		pw.close();
		br.close();
	}
}


import sys
 
 
def valid(mid: int) -> bool:
	# de L a R
	# i marca el fardo actual que estamos explotando
	# j marca el fardo más lejano que podemos alcanzar
	i, j = 0, 0
 
	# maxpos encuentra el índice más a la derecha que puede alcanzar la izquierda
	maxpos = hay[0] + mid
	r = mid % 2
	while j < n and r <= mid:
		if hay[i] + r >= hay[j]:
			j += 1
		else:
			if j - i == 1:
				# los fardos consecutivos son un caso especial
				# el ancla es el fardo justo anterior, así que no podemos empezar una nueva cadena
				r = (hay[j] - hay[i]) + (hay[j] - hay[i]) % 2
				if r >= mid:
					# actualizar la posición máxima posible si el radio es insuficiente
					maxpos = min(maxpos, hay[i] + mid)
					break
			else:
				# de lo contrario, podemos explotar el fardo j-1 y empezar de nuevo con menor potencia
				r += 2
				i = j - 1
		if r <= mid:
			maxpos = max(maxpos, hay[i] + mid)
 
	# de R a L
	i, j = n - 1, n - 1
 
	# minpos encuentra el índice más a la izquierda que puede alcanzar la derecha
	minpos = hay[-1] - mid
	r = mid % 2
	while j >= 0 and r <= mid:
		if hay[i] - r <= hay[j]:
			j -= 1
		else:
			if i - j == 1:
				r = (hay[i] - hay[j]) + (hay[i] - hay[j]) % 2
				if r >= mid:
					minpos = min(minpos, hay[i] - mid)
					break
			else:
				r += 2
				i = j + 1
		if r <= mid:
			minpos = min(minpos, hay[i] - mid)
 
	# la explosión es posible si los rangos se solapan
	return minpos <= maxpos
 
 
with open("angry.in", "r") as f:
	n = int(f.readline().strip())
	hay = [
		int(f.readline().strip()) * 2 for _ in range(n)
	]  # duplicar posiciones para evitar decimales
hay.sort()
 
# búsqueda binaria para la menor potencia inicial
l, r = 0, hay[-1]
while l < r:
	mid = (l + r) // 2
	if valid(mid):
		r = mid
	else:
		l = mid + 1
 
print(f"{l / 2:.1f}", file=open("angry.out", "w"))