Overview

Given children standing in a line, we need to find the minimum number of operations to equalize everyone’s cake count, where each operation passes one cake between adjacent children. This can be efficiently solved using the well-known technique of “sum of absolute values of prefix sums.”

Analysis

Key Insight: Focus on the “flow” between adjacent children

First, the number of cakes each child should ultimately have is \(\text{target} = \frac{\sum A_i}{N}\). If this is not an integer, it’s impossible, so we output -1.

Next, let \(f_i\) denote the amount of cake flowing between child \(i\) and child \(i+1\) (the flow). If \(f_i > 0\), cakes flow from left to right; if \(f_i < 0\), cakes flow from right to left.

Considering child \(1\): for child \(1\) to end up with target cakes, they need to send \(A_1 - \text{target}\) cakes to the right. That is:

\[f_1 = A_1 - \text{target}\]

Similarly, child \(2\) receives \(f_1\) cakes from the left and sends \(f_2\) cakes to the right. From the balance of child \(2\):

\[A_2 + f_1 - f_2 = \text{target} \implies f_2 = (A_1 - \text{target}) + (A_2 - \text{target})\]

Generalizing, the flow between positions \(i\) and \(i+1\) is:

\[f_i = \sum_{j=1}^{i} (A_j - \text{target})\]

In other words, \(f_i\) is the prefix sum of the differences \(A_j - \text{target}\).

Why is the number of operations the sum of \(|f_i|\)?

Since one operation moves one cake between two adjacent children, the number of cakes passing through the boundary between positions \(i\) and \(i+1\) is \(|f_i|\). The total of these passage amounts across all boundaries gives the minimum total number of operations.

Concrete Example

For \(N = 4\), \(A = [7, 3, 1, 5]\), we have \(\text{target} = 16 / 4 = 4\).

| Position \(i\) | \(A_i - \text{target}\) | Prefix sum \(f_i\) | \(|f_i|\) |

1	\(+3\)	\(3\)	\(3\)
2	\(-1\)	\(2\)	\(2\)
3	\(-3\)	\(-1\)	\(1\)
4	\(+1\)	\(0\)	\(0\)

The answer is \(3 + 2 + 1 + 0 = 6\) operations. (The last prefix sum is always \(0\).)

Algorithm

1. If the total number of cakes \(\sum A_i\) is not divisible by \(N\), output -1.
2. Compute \(\text{target} = \frac{\sum A_i}{N}\).
3. Let \(B_i = A_i - \text{target}\), and compute the prefix sums \(S_i = \sum_{j=1}^{i} B_j\).
4. The answer is \(\sum_{i=1}^{N} |S_i|\).

Complexity

• Time complexity: \(O(N)\) (just a single pass through the array)
• Space complexity: \(O(N)\) (for storing the input array. The prefix sum can be maintained with a single variable, so the additional space is \(O(1)\))

Implementation Notes

• There is no need to store the prefix sums in an array; you can update a variable prefix and accumulate abs(prefix) as you go.

• Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the prefix sums and operation count can reach approximately \(2 \times 10^{14}\). In Python, there is no overflow concern due to arbitrary-precision integers, but in C++ and similar languages, you need to use long long.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    total = sum(A)
    if total % N != 0:
        print(-1)
        return
    
    target = total // N
    
    # The minimum number of operations is the sum of absolute values of prefix sums of (A_i - target).
    # This is because the flow between position i and i+1 equals the prefix sum up to i.
    ops = 0
    prefix = 0
    for i in range(N):
        prefix += A[i] - target
        ops += abs(prefix)
    
    print(ops)

main()

---

This editorial was generated by claude4.6opus-thinking.