Editorial for Mock CCC '22 Contest 2 J3 - Figure Skating Fun

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.

Authors: ayay9, Tommy_Shan

Note that if the spot exists, it will be unique. The proof is left as an exercise to the reader.

Subtask 1

We attempt to find the splitting spot by looping through all possible spots, going from left to right. We can then find the sum on either side of the spot by looping through the left and the right separately and comparing their sums.

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

Full Solution

Notice that every time we move one spot, the left sum increases by the score of the i^\text{th} competitor, while the right sum decreases by this score. From this observation, we can simply use two variables to keep track of the left and right sums, and compare them during each iteration.

Time Complexity: \mathcal{O}(N)

An alternative solution involves a prefix sum array. We first construct the prefix sum array, then loop through each possible splitting index. During each iteration, we use the prefix sum array to compare the left and right sum in constant time.

Time Complexity: \mathcal{O}(N)


There are no comments at the moment.