Angry Cows Silver problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=594

This is a binary search problem, using simulation to check if a value R works. In the simulation part, say we’re only allowed to detonate cows at the exact locations of haybales.

How do we check quickly if we can explode all N haybales using K cows?

I tried an O(NK) approach where I generate an R-length sliding window for each haybale. I detonate at the location with the largest window. Once some haybales explode, I discount the exploded haybales from each window and find the maximum window length once again. I use prefix sums to calculate how many bales have exploded in a particular range.

I don’t think my code has the right approach. The R-length sliding window might not always work, since it’s essentially a greedy strategy where I detonate the maximum number of haybales possible each time. Can you please explain if or why my code’s logic is correct?

```
int ok(int R){
bool invalid[N] = {0};
int prefix[N] = {0};
// compute R-length sliding windows
pair<int, int> bales[N];
// haybales before bale j
for (int j = N-1, k = N-1; j >= 0; j--){
while(k > 0 && Pos[k-1] >= Pos[j] - R) k--;
bales[j].f = k;
}
// haybales after bale j
for(int j = 0, k = 0; j < N; j++){
while(k < N-1 && Pos[k+1] <= Pos[j] + R) k++;
bales[j].s = k;
}
for(int i = 0; i < K; i++){
// take the window with the most bales
int l, r;
int maxBales = -1;
for (int j=0; j < N; j++) if (!invalid[j]) {
int a = bales[j].f, b = bales[j].s;
// interval from a to b inclusive
int numInvalid = prefix[b] - (a ? prefix[a-1] : 0);
int total = (b - a + 1) - numInvalid;
if (total > maxBales){
maxBales = total;
l = a, r = b;
}
}
// every haybale from l to r inclusive detonates
for (int j = 0; j < N; j++){
if (l <= j && j <= r) invalid[j] = 1;
prefix[j] = invalid[j];
if (j) prefix[j] += prefix[j-1];
}
}
return prefix[N-1];
}
```

There is certainly a more efficient approach that is easier to code. The modified problem seems simple enough: find the maximum haybales that can explode if we can only detonate cows at the exact locations of haybales. Can you please help me find the right idea and provide code so I can make progress?

Thank you.