Angry Cows

Solución en video

Por Qi Wang

Explicación

Como hay a lo sumo 100 fardos de heno, podemos probar lanzar una vaca contra cada uno y simular las consecuencias.

Implementar las explosiones puede volverse un poco incómodo; para facilitarlo, notamos que las explosiones del lado izquierdo y del derecho son completamente independientes entre sí.

Consideremos una situación en la que los fardos están en $[3, 4, 5]$ . Los identificaremos por sus posiciones por comodidad.

Si lanzamos una vaca contra el fardo $4$ , aunque $5$ sea capaz de hacer explotar $3$ con una explosión de radio $2$ , $3$ ya iba a explotar de todos modos por la explosión de radio $1$ de $4$ .

Esta observación nos permite revisar hasta dónde puede llegar la explosión en ambos lados y luego sumar los resultados para obtener la respuesta final.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int N;
vector<int> bales;
 
int exploded_num(int start, int direction) {
	int radius = 1;
	int prev = start;
	while (true) {
		int next = prev;
		// Get the furthest explosion index without exceeding the current radius
		while (next + direction >= 0 && next + direction < N &&
		       abs(bales[next + direction] - bales[prev]) <= radius) {
			next += direction;
		}
 
		// We didn't find a new haybale, so the chain explosion is over
		if (next == prev) { break; }
 
		// Update our previous explosion and increment radius
		prev = next;
		radius++;
	}
 
	return abs(prev - start);
}
 
int main() {
	freopen("angry.in", "r", stdin);
	freopen("angry.out", "w", stdout);
 
	cin >> N;
	bales.resize(N);
	for (int i = 0; i < N; i++) { cin >> bales[i]; }
 
	sort(bales.begin(), bales.end());
	int max_exploded = 0;
	for (int i = 0; i < N; i++) {
		// Get the number of exploded bales for the left & right side
		max_exploded = max(max_exploded, exploded_num(i, -1) + exploded_num(i, 1) + 1);
	}
 
	cout << max_exploded << endl;
}


import java.io.*;
import java.util.*;
 
public class Angry {
	private static int N;
	private static int[] bales;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("angry");
 
		N = io.nextInt();
		bales = new int[N];
		for (int i = 0; i < N; i++) { bales[i] = io.nextInt(); }
 
		Arrays.sort(bales);
		int maxExploded = 0;
		for (int i = 0; i < N; i++) {
			// Get the number of exploded bales for the left & right side
			maxExploded =
			    Math.max(maxExploded, explodedNum(i, -1) + explodedNum(i, 1) + 1);
		}
		io.println(maxExploded);
		io.close();
	}
 
	public static int explodedNum(int start, int direction) {
		int radius = 1;
		int prev = start;
		while (true) {
			int next = prev;
			// Get the furthest explosion index without exceeding radius
			while (next + direction >= 0 && next + direction < N &&
			       Math.abs(bales[next + direction] - bales[prev]) <= radius) {
				next += direction;
			}
			// We didn't find a new haybale, so the chain explosion is over
			if (next == prev) { break; }
			// Update our previous explosion and increment radius
			prev = next;
			radius++;
		}
		return Math.abs(prev - start);
	}
 
	// CodeSnip{Kattio}
}


with open("angry.in") as read:
	bales = sorted([int(read.readline()) for _ in range(int(read.readline()))])
 
 
def exploded_num(start: int, direction: int) -> int:
	radius = 1
	prev = start
	while True:
		next_ = prev
		# Get the furthest explosion index without exceeding the current radius
		while (
			0 <= next_ + direction < len(bales)
			and abs(bales[next_ + direction] - bales[prev]) <= radius
		):
			next_ += direction
 
		# We didn't find a new haybale, so the chain explosion is over
		if next_ == prev:
			break
 
		# Update our previous explosion and increment radius
		prev = next_
		radius += 1
	return abs(prev - start)
 
 
max_exploded = 0
for i in range(len(bales)):
	# Get the number of exploded bales for the left & right side
	max_exploded = max(max_exploded, exploded_num(i, -1) + exploded_num(i, 1) + 1)
print(max_exploded, file=open("angry.out", "w"))