I want help on the USACO Silver problem Sleepy Cow Herding.
For the maximum value, let’s say we move a[0] to a[1] + 1. Then we can move each of a[0], a[1], ..., a[n-2] right to the first unoccupied integer location. We can do this until all of a[0], a[1], ..., a[n-2] are lined up consecutively before a[n-1]. There are a total of a[n-1] - a[1] integer points we reach, minus the ones where cows a[1], ..., a[n-2] already stand. This gives a[n-1] - a[1] - (n-2) moves. By doing the same process in the reverse order, we can get a[n-2] - a[0] - (n-2), so the answer is the maximum of these two candidates.
I am stuck on how to approach finding the minimum number of moves required. Let M be the smallest gap between consecutive cows whose length is \ge 2. I thought of greedily moving an endpoint to the midpoint of M each iteration. However, this would not work in the case 1, 2, 3, 6, where the optimal strategy would be to move cow 6 to place 0 instead of cow 1 to place 4.
Please give me a hint as to how to approach finding the minimum value. Since I am weak at ad hoc problems, I want to be able to think of such ideas myself. Please do not reveal the approach to this problem, but please give me a nudge so I can make progress.
Thanks!