Problem Info
Angry Cows - USACO
My Work
#include <bits/stdc++.h>
using namespace::std;
#define ll long long
int main () {
cout << fixed << showpoint;
cout << setprecision(1);
int n; cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr+n);
int left[n], right[n];
for (int i = 0; i < n; i++) left[i]=0, right[i]=0;
int y = 0;
for (int x = 0; x < n; x++) {
while (y+1<x && arr[x]-arr[y]>left[y]+1) y++;
left[x]=max(arr[x]-arr[y], left[y]+1);
}
y=n-1;
for (int x = n-1; x >= 0; x--) {
while (y-1>x && arr[y]-arr[x]>right[y]+1) y--;
right[x]=max(arr[y]-arr[x], right[y]+1);
}
double minrad = 1e9;
for (int x = 0; x < n; x++) {
minrad=min(minrad, (double) max(left[x], right[x]));
}
for (int x = 0; x < n-1; x++) {
int a = left[x], d = right[x+1];
minrad = min(minrad, (double) max((double)(arr[x+1]-((arr[x+1]+arr[x])/2.0)), (double) max(a+1, d+1)));
// cout << (double)(arr[x+1]-((arr[x+1]+arr[x])/2.0)) << " " << a+1 << " " << d+1 << "\n";
}
cout << minrad << "\n";
}
Basically this runs a dp on the minimum radius needed to reach the left from a haybale and right from a point. Then just take the max of both values, and min is answer. I also checked if the shot lands in between 2 bales, and used some algebra to calculate the minimum values.
Question
For some reason, the right dp isn’t working, and I am not able to figure out why