Overview

This problem asks for the minimum number of operations to make everyone have the same number of cakes, given that adjacent people can transfer one cake at a time (or output -1 if it’s impossible).

Analysis

First, for everyone to end up with the same number \(x\), the total \(S=\sum A_i\) must be divisible by \(N\), giving \(x=\frac{S}{N}\). If this doesn’t hold, it’s absolutely impossible, so we output -1.

Next, let’s think about the “minimum number of operations.” If we naively simulate something like “distribute from people with more to nearby people with fewer,” the state changes in complex ways depending on the order of moves, and since we move one cake at a time, the number of operations can become extremely large (e.g., \(10^{14}\)), making direct simulation impractical.

The key observation is:

• The number of cakes that need to cross the boundary between child \(i\) and \(i+1\) is uniquely determined once the final state is decided.
• The sum of the absolute values of these “required transfer amounts across boundaries” equals the minimum number of operations (since one operation corresponds to moving one cake across a boundary).

Here, we consider the “running surplus/deficit” from left to right. The cumulative sum of differences from the average \(A_i-\text{avg}\): $\( \text{running}_i = \sum_{k=1}^{i} (A_k-\text{avg}) \)\( represents "how many cakes the range of children \)1..i$ has in excess (positive) or deficit (negative) relative to the required final count.”

Then the number of cakes that must cross boundary \((i,i+1)\) is exactly \(\text{running}_i\), and the required number of operations is \(|\text{running}_i|\). Therefore, the answer is: $\( \sum_{i=1}^{N-1} |\text{running}_i| \)\( (Only \)N-1$ boundaries, since there is no boundary after the last child.)

Concrete Example

For example, with \(N=4,\ A=[1,6,2,3]\), the total is \(12\) and the average is \(\text{avg}=3\).

• \(i=1\): running \(=1-3=-2\) → 2 cakes need to move from right to left across boundary (1,2) → \(2\) operations
• \(i=2\): running \(=-2+(6-3)=1\) → 1 cake needs to move from left to right across boundary (2,3) → \(1\) operation
• \(i=3\): running \(=1+(2-3)=0\) → boundary (3,4) requires \(0\) operations

Total: \(2+1+0=3\) operations is the minimum.

Algorithm

1. Compute \(S=\sum A_i\). If \(S \bmod N \neq 0\), output -1 and terminate.
2. Compute \(\text{avg}=S/N\).
3. Initialize running = 0, ans = 0, and for \(i=1..N-1\) (or range(N-1) in 0-indexed):
   • running += A[i] - avg
   • ans += abs(running)
4. Output ans.

This running is exactly the required transfer amount across each boundary, and since each boundary independently requires “just the necessary amount” of transfers, the total gives the minimum number of operations.

Complexity

• Time complexity: \(O(N)\) (completed in a single pass)
• Space complexity: \(O(1)\) (only a constant number of variables besides the input array)

Implementation Notes

• The loop only needs to go up to \(i=1..N-1\) (there is no boundary to the right of the last child).

• ans can become very large (when \(N\) is large and differences are large), so while this is not an issue in Python, in other languages you should use 64-bit integers (long long, etc.).

• Since the input can be large, fast input methods like sys.stdin.buffer.read() are effective.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    A = data[1:1+N]

    total = sum(A)
    if total % N != 0:
        print(-1)
        return

    avg = total // N
    running = 0
    ans = 0
    for i in range(N - 1):
        running += A[i] - avg
        ans += abs(running)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.