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\ne 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\ne 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)$