Subtask 1

The only possible splitting point is between the two students, so all we have to do is output ~|s_1 - s_2|~ twice.

Time Complexity: ~\mathcal{O}(1)~

Subtask 2

Consider an imaginary splitting point, starting between the first two students. As we move this splitting point to the right, the sum of strengths of the left side will increase and the sum of strengths of the right side will decrease. All we have to do is find their "intersection point" (since I've been cramming too much economics recently, think ~\text{MR} = \text{MC}~), and that will give us the optimal answer. We can do this in ~\mathcal{O}(N)~ for each value of ~l~, for ~\mathcal{O}(N^2)~ total.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 3

For full marks, we can extend the idea above to work in ~\mathcal{O}(N)~ total. Let's first calculate the optimal splitting point for ~l=1~ with the method above. Then, we notice that as ~l~ increases, the sum of strengths on the left side of the splitting point decreases whereas the sum of strengths on the right side of the splitting point increases. This can only move the optimal splitting point to the right. Furthermore, once we have made a full cycle, the optimal splitting point will end up back where it was originally, ~N~ units away. Since the optimal splitting point only moves ~N~ times at maximum in our algorithm, the time complexity is ~\mathcal{O}(N)~.

It is worth noting that binary searching for the optimal splitting point with a prefix sum data structure is also sufficient to pass in ~\mathcal{O}(N \log N)~, and requires less insight.

Time Complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N \log N)~