Editorial for An Animal Contest 4 P4 - Reindeer Racing
Submitting an official solution before solving the problem yourself is a bannable offence.
Observe that we should try to minimize the number of bananas that we need to throw. If it is possible for the reindeer in lane to win, the solution exists with throwing either one banana or none at all.
The casework breaks down as such:
If , there is no need to cause any collisions; therefore, we don't need to throw any bananas. The solution always exists in this case.
If , lets first consider the cases when a solution does not exist:
- . In this case, we cannot cause any collisions, and therefore the reindeer in lane will win.
- There does not exist any where . No matter how many collisions we cause, the baton will never reach the reindeer in lane .
Otherwise, it suffices to throw a single banana at the reindeer in lane at metre .
While still considering cases present in the previous subtask, we should also consider cases where .
As observed in Subtask 1, we should try to minimize the number of bananas we throw. Thus, the number of bananas thrown would then be .
If is greater than , we need the reindeer in lane to collide times (we can make every other reindeer collide for every hurdle). Define as the rightmost such that .
The reindeer in lane can collide as many times as they want before as well as during . Therefore, if is less than , then no solution exists and we can output
At this point, we can solve the problem with bananas thrown. While we still have bananas to throw, we can use the following greedy strategy:
- Make the reindeer in lane collide at .
- Make all other reindeer collide at .
- Fill from left to right, (up/down filling order doesn't matter). Once we pass , do not make the reindeer in lane collide with any hurdles.