Subtask 1 [2/15]

This subtask rewarded solutions that used brute force to directly calculate the number of bounces required for each side and taking the minimum.

Since \(a_i\) goes up to \(10^9\), caution must be taken against overflow errors.

Time Complexity: \(O(N^2)\).

Subtask 2 [5/15]

Building off the previous subtask, precomputing the number of bounces required on the left and the number of bounces required on the right, then looping from left to right while updating the two counters is enough for an additional \(5\) points.

Precomputing can be done with Prefix Sum Arrays or two variables.

Time Complexity: \(O(N)\)

Subtask 3 [8/15]

The first observation needed is that it is always optimal to use all of our \(K\) orbital strikes on the same side. Furthermore, it is always best to use the strikes on all odd walls first.

We can then build off our subtask \(2\) solution except now we must precompute a more cleverly. We must seperate precomputing odd and even height walls of both the left and right sums. We are now able to correctly calculate the number of bounces for each strike, assuming we use our orbital strikes optimally.

Our answer is simply the minimum of our calculations for both sides.

Time Complexity: \(O(N)\)