Analysis and Solution for Jan. 2016 USACO Bronze Problem 2
Angry Cows
Analysis
Because the input size is quite small, we can just simulate the explosions starting from each point.
For each explosion, we can split the explosions into left and right components. If the explosion going to the left explodes any haybales, then we only have to simulate the explosions going left because while the explosion radius increases by 1, the haybale has to be 1 space to the left of the original haybale. Therefore, the explosion going to the left cannot explode any haybales to the right. This means that we can fix the direction of the explosion. Thus, we can find the farthest haybale that explodes in an explosion, and simulate the explosion going from that haybale, meaning that we can find the total range that the explosion(s) cover, and also the number of haybales within that range.
Implementations
C++17
/* USACO January 2016 Bronze 2
* C++17 code
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int expIndex(int hay[], int start, bool left, int N);
int main(){
int N = 0;
int ans = 0;
ifstream input("angry.in");
ofstream output("angry.out");
input >> N;
int hay[N];
for(int i = 0; i < N; i++)
input >> hay[i];
input.close();
sort(hay, hay + N);
ans = 1;
for (int i = 0; i < N; i++){
int left = expIndex(hay, i, true, N);
int right = expIndex(hay, i, false, N);
int explode = right - left + 1;
if (explode > ans)
ans = explode;
}
output << ans << "\n";
return 0;
}
int expIndex(int hay[], int start, bool left, int N){
int last = start;
int r = 1;
int size = N;
int dir;
if (left)
dir = -1;
else
dir = 1;
if (left){
while (last > 0 && last - 1 < size - 1){
int next = last;
while ((next + dir >= 0 && next + dir < size) && abs(hay[next + dir] - hay[last]) <= r){
next += dir;
}
if (next == last)
break;
last = next;
r++;
}
}
else {
while (last + 1 > 0 && last < size - 1){
int next = last;
while ((next + dir >= 0 && next + dir < size) && abs(hay[next + dir] - hay[last]) <= r){
next += dir;
}
if (next == last)
break;
last = next;
r++;
}
}
return last;
}
Java 8
/* USACO January 2016 Bronze 2
* Java 8 code
*/
import java.io.*;
import java.util.*;
public class Jan2016Bronze2{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new FileReader("angry.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("angry.out")));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int[] hay = new int[N];
for (int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
hay[i] = Integer.parseInt(st.nextToken());
}
br.close();
Arrays.sort(hay);
int ans = 1;
for (int i = 0; i < N; i++){
int left = expIndex(hay, i, true, N);
int right = expIndex(hay, i, false, N);
int explode = right - left + 1;
if (explode > ans)
ans = explode;
}
pw.println(ans);
pw.close();
}
public static int expIndex(int[] hay, int start, boolean left, int N){
int last = start;
int r = 1;
int size = N;
int dir;
if (left)
dir = -1;
else
dir = 1;
if (left){
while (last > 0 && last - 1 < size - 1){
int next = last;
while ((next + dir >= 0 && next + dir < size) && Math.abs(hay[next + dir] - hay[last]) <= r){
next += dir;
}
if (next == last)
break;
last = next;
r++;
}
}
else {
while (last + 1 > 0 && last < size - 1){
int next = last;
while ((next + dir >= 0 && next + dir < size) && Math.abs(hay[next + dir] - hay[last]) <= r){
next += dir;
}
if (next == last)
break;
last = next;
r++;
}
}
return last;
}
}