Overview

Given a sequence of \(N\) elements, the problem asks to split it into two teams at some point \(k\), dividing it into a front and back portion, and minimize the difference \(|S_1 - S_2|\) of the total values of each team.

Analysis

1. Simplifying the difference formula

Let the sum of Team A be \(S_1\), the sum of Team B be \(S_2\), and the total sum of all members’ skill values be \(Total\). Since \(S_2 = Total - S_1\), the desired difference can be transformed as follows: $\(|S_1 - S_2| = |S_1 - (Total - S_1)| = |2 \times S_1 - Total|\)\( By precomputing \)Total\(, we can calculate the difference at each boundary \)k\( as long as we know the value of \)S_1$.

2. Efficient computation method

Consider trying each boundary \(k\) from \(1\) to \(N-1\) in order. - Naive method: For each \(k\), computing \(S_1\) as \(A_1 + \dots + A_k\) takes up to \(O(N)\) per step, resulting in \(O(N^2)\) total time. Since \(N = 2 \times 10^5\), this will not fit within the time limit. - Efficient method: When shifting the boundary \(k\) one position to the right, only the new member’s skill value \(A_k\) is added to \(S_1\). In other words, we simply add \(A_k\) to the previous step’s \(S_1\) to obtain the next step’s \(S_1\). This allows \(O(1)\) computation per step, resulting in \(O(N)\) overall, which is sufficiently fast.

Algorithm

1. Compute the total sum \(Total\) of the entire sequence.
2. Initialize Team A’s current sum \(S_1\) to \(0\) and the minimum difference \(min\_diff\) to infinity (a sufficiently large value).
3. For \(k = 1\) to \(N-1\), perform the following operations in order:
   • Add \(A_k\) to \(S_1\).
   • Compute the current difference \(|2 \times S_1 - Total|\).
   • If the computed difference is smaller than \(min\_diff\), update the value.
   • If the difference becomes \(0\), it cannot get any smaller, so we can terminate the search early.
4. Output the final \(min\_diff\).

Complexity

• Time complexity: \(O(N)\)
  • Computing the total sum takes \(O(N)\), and the loop over boundaries takes \(O(N)\), so the overall runtime is linear.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the \(N\) input skill values in a list.

Implementation Notes

• Fast I/O: Since \(N\) can be large, in Python using sys.stdin.read().split() or similar methods to read all input at once can reduce execution time.

• Boundary range: The problem specifies \(1 \le k < N\), so the loop must stop before the last element (at \(k=N-1\)) to ensure Team B is not empty.

• Using absolute values: Since either team may have the larger sum, always use the abs() function to take the absolute value when computing the difference.

  Source Code

import sys

def solve():
    # 標準入力から全データを読み込み、空白で分割してリスト化
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # メンバーの人数 N
    n = int(input_data[0])
    # 各メンバーの実力値 A
    a = list(map(int, input_data[1:]))
    
    # 全体の実力値の総和を計算
    total_sum = sum(a)
    
    # チームAの現在の実力値の総和
    current_s1 = 0
    # 最小の差を保持する変数（初期値は無限大）
    min_diff = float('inf')
    
    # 境界 k を 1 から N-1 まで動かす
    # a[i] は 0-indexed なので、i=0 から i=n-2 までループ
    for i in range(n - 1):
        current_s1 += a[i]
        # |S1 - S2| = |S1 - (Total - S1)| = |2 * S1 - Total|
        diff = abs(2 * current_s1 - total_sum)
        
        if diff < min_diff:
            min_diff = diff
        
        # 差が0になった場合はそれ以上小さくならないため終了
        if min_diff == 0:
            break
            
    # 結果を出力
    print(min_diff)

if __name__ == '__main__':
    solve()

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