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)~