Overview

Given \(N\) members, we split them into two teams (first half and second half) at a boundary between consecutive numbers, and minimize the absolute difference of the sums of ability values between the two teams.

Analysis

Problem Formulation

We try each split point \(k\) from \(1\) to \(N-1\), and for each one compute

\[|S_1 - S_2| = |(A_1 + \cdots + A_k) - (A_{k+1} + \cdots + A_N)|\]

then find the minimum value.

Issues with the Naive Approach

If we recompute \(S_1\) and \(S_2\) from scratch for each \(k\), a single computation takes \(O(N)\), and repeating this \(N-1\) times results in \(O(N^2)\) overall. When \(N\) is up to \(2 \times 10^5\), this amounts to approximately \(4 \times 10^{10}\) operations, which will result in TLE (Time Limit Exceeded).

Key Insight

Let the total sum be \(T = A_1 + A_2 + \cdots + A_N\). Then,

\[S_2 = T - S_1\]

so we can rewrite:

\[|S_1 - S_2| = |S_1 - (T - S_1)| = |2 \cdot S_1 - T|\]

This means we can compute the difference as long as we know the prefix sum \(S_1\).

Furthermore, when \(k\) increases by \(1\), \(S_1\) increases by \(A_k\), so by incrementally updating the prefix sum, we can compute the result in \(O(1)\) for each \(k\).

Concrete Example

For \(N = 4\), \(A = [1, 3, 2, 4]\), we have \(T = 10\).

\(k\)	\(S_1\)	\(S_2\)	\(\|2 \cdot S_1 - T\|\)
1	1	9	\(\|2 - 10\| = 8\)
2	4	6	\(\|8 - 10\| = 2\)
3	6	4	\(\|12 - 10\| = 2\)

The minimum value is \(2\).

Algorithm

1. Compute the total sum \(T\).
2. Initialize a variable prefix (prefix sum of the first half) to \(0\).
3. Loop through \(k = 1, 2, \ldots, N-1\), and at each step:
   • Add \(A_{k}\) (or \(A[k-1]\) in 0-indexed) to prefix.
   • Compute \(|2 \cdot \text{prefix} - T|\) and update the running minimum.
4. Output the minimum value.

Complexity

• Time complexity: \(O(N)\) — \(O(N)\) for computing the total sum, and \(O(N)\) for the loop
• Space complexity: \(O(N)\) — for storing the input array (since we don’t create a separate prefix sum array, the additional space is \(O(1)\))

Implementation Notes

• By incrementally adding to prefix, we can track the first half’s sum without explicitly constructing a prefix sum array.

• The absolute difference is computed using the expression abs(2 * prefix - total). By leveraging the relation \(S_2 = T - S_1\), we reduce it to a single subtraction, resulting in cleaner code.

• The initial value of the minimum is set to float('inf') so that it compares correctly against any large value.

• Note that \(k\) ranges over \(1 \le k < N\). The cases \(k = 0\) (Team A is empty) and \(k = N\) (Team B is empty) are not allowed.

  Source Code

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
prefix = 0
ans = float('inf')
for k in range(1, N):
    prefix += A[k-1]
    diff = abs(2 * prefix - total)
    if diff < ans:
        ans = diff
print(ans)

---

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