Angry Cows Silver Question

I’m still not sure if your algorithm is correct for this version of the problem. We can only drop cows where haybales are, and what your algorithm does is drop a cow so that it just reaches the leftmost unexploded bale.

I did not see such requirement, and it passed the USACO online judge.

we’re talking about a modified version of the problem here…

I have a O(n\lg^2 n) solution with your adjusted problem.

First do binary search, then do dynamic programming.

let \text{dp}[i] be the minimal amount of cows needed to make 1-i covered.

then we binary search l and r, which is the first element of x[] out of the [x[i]-mid,x[i]+mid].

Then \text{dp}[k] = min(\text{dp}[k],\text{dp}[l]+1) \text{ where [l<k<r]}

This can be optimized into O(n \lg n) using segment tree. Considering the binary search that we did initially, the time complexity is O(n\lg^2 n)

The dp is a range minimum where the left endpoint moves monotonically right, which can be done in O(N) time with a deque.

But you can notice that you don’t even need a range minimum, since the dp table is monotonically increasing (if you define it to be dp[i] = covering at least cows 1 through i). So it can be done with two pointers in O(n), more or less equivalent to the greedy solution.