Editorial for DMOPC '20 Contest 6 P1 - Tug of War
Submitting an official solution before solving the problem yourself is a bannable offence.
The only possible splitting point is between the two students, so all we have to do is output twice.
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 ), and that will give us the optimal answer. We can do this in for each value of , for total.
For full marks, we can extend the idea above to work in total. Let's first calculate the optimal splitting point for with the method above. Then, we notice that as 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, units away. Since the optimal splitting point only moves times at maximum in our algorithm, the time complexity is .
It is worth noting that binary searching for the optimal splitting point with a prefix sum data structure is also sufficient to pass in , and requires less insight.
Time Complexity: or