Editorial for An Animal Contest 4 P4 - Reindeer Racing

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ThingExplainer

Subtask 1

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 F to win, the solution exists with throwing either one banana or none at all.

The casework breaks down as such:

If S = F, 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 S \neq F, lets first consider the cases when a solution does not exist:

  • R = 0. In this case, we cannot cause any collisions, and therefore the reindeer in lane S will win.
  • There does not exist any i where k_i = F. No matter how many collisions we cause, the baton will never reach the reindeer in lane F.

Otherwise, it suffices to throw a single banana at the reindeer in lane S at metre i.

Time Complexity: \mathcal{O}(NM)

Subtask 2

While still considering cases present in the previous subtask, we should also consider cases where L \neq 0.

As observed in Subtask 1, we should try to minimize the number of bananas we throw. Thus, the number of bananas B thrown would then be L.

If B is greater than N \times M - M, we need the reindeer in lane F to collide B - (N \times M - M) times (we can make every other reindeer collide for every hurdle). Define k_{\max} as the rightmost k_i such that k_i = F.

The reindeer in lane F can collide as many times as they want before as well as during k_{\max}. Therefore, if k_{\max} is less than B - (N \times M - M), then no solution exists and we can output -1.

At this point, we can solve the problem with B bananas thrown. While we still have bananas to throw, we can use the following greedy strategy:

  • Make the reindeer in lane S collide at k_{\max}.
  • Make all other reindeer collide at k_{\max}.
  • Fill from left to right, (up/down filling order doesn't matter). Once we pass k_{\max}, do not make the reindeer in lane F collide with any hurdles.

Time Complexity: \mathcal{O}(NM)


There are no comments at the moment.