Sleepy Cow Herding

#1

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!

#2

In this case,

4
1 2 3 6

the optimal strategy would not be to move cow 6 to place 0 because place 0 would still be an endpoint.

However, the approach is still incorrect.

6
1 3 6 7 8 11

In the above case, it would be optimal to move the cow at position 1 to position 9 and 3 to 10, so the smallest gap between consecutive cows isn’t always relevant.

Hint: moving the cows to be in consecutive locations in the least number of moves possible is the same thing as maximizing the number of cows that stay in their positions.

#3

That means, to minimize the number of moves in the problem, we need to minimize the number of cows that shift at all. I experimented with that and it seems correct, but logically, minimizing the number of cows that change and minimizing the number of moves we make are two different ideas. Why is your statement correct?

Assuming it is correct, however, I can’t think of how to leverage that fact. I am stuck without knowing the range of places where cows must be idle. I assume we must find such a range ourselves in O(N) time; i.e. there is no mathematical way to deduce that range. Please let me know if I am straying off track.

AIl that I have so far is to use two pointers with i being the left endpoint and j being the right endpoint of the set. I must move i and/or j to a different position as long as j-i+1 > n. This does not constitute any further progress. Can you please guide me more?

#4

In the end, the cows will end up in a range of length N with a left and right bound. If we want to minimize the number of moves, ideally, each move will put a cow outside that range to a position within the range so the two ideas are the same (and you can always do this with one exception that you will have to handle). The only time where we don’t have to spend a move is when a cow is already in that range and can stay put.

Let me know if you need help finding that range in O(N).

#5

Thank you. According to your post, I need a sliding window of length n coordinates that contains the most number of cows. I can do this by increasing the right pointer for a given left pointer so long as the right value is at most n-1 more than the left value. Thanks for the help!

1 Like
#6

I am having trouble understanding the intuition behind this problem’s solution.

How do we think of using an N-length subarray?

You mentioned that the cows will end up in a range of length N with a left and right bound. I hadn’t thought of pre-defining the left and right bound and seeing how many moves it would take to get in that range. To me, those final positions seemed arbitrary; I can extract those positions by simulating the process dictated by a greedy algorithm.

What made you think that once a left and right bound are given, the structure of the problem falls into place? How did you know that we can always move cows outside this range to inside the range with a definitive process?

Where does the idea behind the exception come from?

  • When is it true that “with care, we can ensure that we fill in the x empty spaces in the window in exactly x moves?” Why does it work in those cases?
  • Does it always work if there are cows on both sides of the subarray?
  • Why would you consider the possibility that the idea doesn’t hold with N-1 consecutive cows?

Thank you.

#7

Hi, can you please respond to the above? Much appreciated, thanks!

#8

Usually, the ideas for USACO problems come from “feeling it in your bones” after doing enough of them. But to be honest, given a left bound and a right bound for all the cows, there’s only so many moves FJ can make before all the cows fall into place.

Why wouldn’t it work?

Well, it should work if there are cows on both sides. I can’t see any reason why there wouldn’t be, as FJ can still herd cows at either endpoint.

It just comes from writing some of your own test cases and playing around with them (at least it came like that way for me).

#9

Sorry, I was busy recently. I could spend time coming up with more rigorous proofs for each of the ideas, but as SansPapyrus683 said, in real contest time, those ideas come from drawing out / playing around with cases and using your intuition and experience built up from lots and lots of problems beforehand. That’s essentially how you get better at ad hoc in general.