Overview

This problem asks for the minimum number of operations to equalize the number of cakes held by \(N\) children, where the only allowed operation is passing cakes between adjacent children. If the total number of cakes is not divisible by \(N\), it is impossible to distribute them equally, so we output -1.

Analysis

1. Determining the Target Value

First, we calculate the number of cakes each child should ultimately have (the target value). If the total number of cakes is \(S\), then the number per person is \(target = S / N\). If \(S\) is not divisible by \(N\), no matter how we move the cakes, equal distribution is impossible, so we can immediately determine the answer is -1.

2. Focusing on Transfers Across Boundaries

The key insight of this problem is to focus on the “boundaries” between children lined up in a row. For example, consider the group from child \(1\) to child \(i\) (the left group). If the total number of cakes this group originally holds exceeds the target total (\(target \times i\)), the surplus must be sent across the “boundary between child \(i\) and child \(i+1\)” to the right side. Conversely, if there is a deficit, cakes must be sent from the right side across the boundary.

3. Deriving the Minimum Number of Operations

The operation of passing one cake between two adjacent children corresponds to one cake crossing a certain boundary. For each boundary \(i\) (between child \(i\) and child \(i+1\)), the number of cakes that must cross it equals the absolute value of the difference between “the total number of cakes currently held by children \(1\) through \(i\)” and “the total number of cakes children \(1\) through \(i\) should ultimately hold”.

The sum of these “absolute differences” across all boundaries (a total of \(N-1\) locations) gives the desired minimum number of operations.

Algorithm

1. Calculate the total number of cakes total_cakes.
2. If total_cakes % N != 0, output -1 and terminate.
3. Calculate the target value target = total_cakes // N.
4. Initialize the variable ans (total number of operations) and current_diff (cumulative surplus/deficit) to \(0\).
5. For child \(i = 1\) to \(N-1\), repeat the following:
   • Add A[i] - target to current_diff.
   • Add abs(current_diff) to ans.
6. Output the final ans.

Complexity

• Time Complexity: \(O(N)\)
  • Both the calculation of the total number of cakes and the single pass through the list are \(O(N)\), so the overall algorithm runs in linear time.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array storing the number of cakes in the input.

Implementation Notes

• Prefix Sum Approach: When calculating the surplus/deficit at each boundary, recomputing the sum from scratch each time would cost \(O(N^2)\). By updating current_diff incrementally from left to right, we can compute it in \(O(N)\).

• Handling Large Numbers: Since the values of \(A_i\) and \(N\) can be large, the total and the number of operations may not fit in a 32-bit integer. In Python, this is not an issue because integers are automatically handled as arbitrary-precision integers, but in other languages (such as C++), you need to use the long long type.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 子どもの数 N と各子どもが持つケーキの数 A を取得
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    # ケーキの総数を計算
    total_cakes = sum(a)
    
    # 総数が N で割り切れない場合は、均等に分配できないため -1 を出力
    if total_cakes % n != 0:
        print("-1")
        return
    
    # 最終的に全員が持つべきケーキの数
    target = total_cakes // n
    
    ans = 0
    current_diff = 0
    # 隣り合う子ども同士の境界を越えて移動させるケーキの数を計算
    # 累積和の絶対値の合計が最小操作回数となる
    for i in range(n - 1):
        # 現在の子どもまでの過不足分を累積
        current_diff += a[i] - target
        # その過不足分を解消するために境界を越えるケーキの移動回数を加算
        ans += abs(current_diff)
        
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.