Editorial for DMOPC '20 Contest 6 P1 - Tug of War


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

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)


Comments


  • 1
    luismo  commented on June 8, 2021, 8:38 p.m.

    ...As we move this splitting point to the right, the sum of strengths of the left side will decrease ... isn't it like the sums of strengths of the left will INCREASE and the sums of the right will DECREASE, please explain


    • 1
      4fecta  commented on June 8, 2021, 10:17 p.m.

      Yeah you're right, fixed.