Here is the problem.
USACO 2018 US Open Contest, Bronze
Problem 2. Milking Order
I have no clue what the solution is saying. Here is my solution.
I only got 3 test cases right so don’t count on my solution. I know I’m being pretty vague, but can anyone explain to me the general idea and implementation of the solution that usaco has?
The analysis is a bit confusing, to be fair. Their idea is to try every possible location of cow 1. Since the bounds are pretty low (N<100), you have time to do this loop.
Now that cow 1’s position is fixed, the only thing left to do is put down the cows in the “given order” array. Notice that for each cow in this array (whose position is not already fixed), it’s optimal to put it down as far to the left as possible. This is a greedy algorithm. The rest of the problem is book-keeping to track available cows and available spots.
Greedy algorithms are very common, particularly when you are constructing some kind of ordering like in this problem.