Overview

We need to find the minimum number of operations to make all children have the same number of cakes by exchanging cakes between adjacent children. If the total number of cakes is not divisible by the number of people, output -1.

Analysis

First, if the total number of cakes \(S = \sum_{i=1}^{N} A_i\) is not divisible by \(N\), it is impossible to distribute the same number to everyone. In that case, we output -1.

If it is divisible, the target number of cakes per person is \(\text{target} = S / N\).

A naive approach of “moving cakes one by one from those who have too many toward those who have too few” would be too computationally expensive and would not finish in time. Optimizing the movement paths is also difficult.

Here is a key observation: Since operations can only be performed between two adjacent people, when thinking about the overall “flow,” what matters is the cumulative surplus or deficit up to each position.

In other words, if we calculate how much the total number of cakes in the range from the 1st to the \(i\)-th person exceeds or falls short of the target \(\text{target} \times (i+1)\), we can determine “how many cakes need to flow to the right (or should flow in from the left)” up to that range.

For example, if the cumulative surplus at a certain position is \(+3\) when viewed from the left, then a total of 3 cakes need to be transported to the right from that position. Summing up these values (in absolute value) across all positions gives the minimum number of required operations.

In this way, we can efficiently compute the answer by taking the sum of absolute values of cumulative differences.

Algorithm

1. Compute the total sum of cakes \(S\) and check if it is divisible by \(N\). If not, output -1 and terminate.
2. Compute the target value \(\text{target} = S / N\).
3. Compute the cumulative difference from the left: \(B[i] = \sum_{j=0}^{i} A[j] - \text{target} \times (i+1)\).
4. The answer is the sum of \(|B[i]|\) for each \(i\).
5. The last element is automatically determined, so computing from \(i = 0\) to \(N-2\) is sufficient.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (only using a cumulative variable)

Implementation Notes

• By managing the cumulative difference with a variable called cum_diff and adding abs(cum_diff) to the result each time, we can compute efficiently.

• Since the last element is automatically determined once all other elements are fixed, the loop only needs to run \(N-1\) times.

• sys.stdin.read is used for fast input reading.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    total = sum(A)
    
    if total % N != 0:
        print(-1)
        return
    
    target = total // N
    
    # 累積の不足/余剰を計算
    # B[i] = A[0] + ... + A[i] - target*(i+1)
    # この値は、左からi番目までの範囲で、targetよりどれだけ多く持っているか（正）または足りないか（負）を示す
    cum_diff = 0
    res = 0
    for i in range(N - 1):  # 最後の人は自動的に決まるのでN-1まで
        cum_diff += A[i] - target
        res += abs(cum_diff)
    
    print(res)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.