USACO Bronze 2016 January - Angry Cows

Video Solution

By Qi Wang

Explanation

Official Analysis (Java)

Since there's at most 100 haybales, we can try launching a cow at every single one and simulate the aftermath.

Implementing the explosions can get a little nasty, though, so to make things easier we can notice that the explosions on the left and right side are completely independent from each other.

Consider a situation where the haybales are $[3, 4, 5]$. We'll refer to them by their positions for convenience.

If we launch a cow at the haybale $4$, although $5$ is able to blow up $3$ with an explosion of radius $2$, $3$ was already going to explode anyway from $4$'s explosion of radius $1$.

This observation allows us to check the farthest the explosion can reach on both sides and then add up the results for our final answer.

3
3
5
6

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
#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) {

Copy
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");

Copy
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