Overview

This is a problem where you try all possible boundaries \(k\) that split an array into a “first half (Team A)” and a “second half (Team B)”, and find the minimum value of the difference of sums \(|S_1-S_2|\). By incrementally updating the left sum as you go, the entire problem can be solved in a single pass.

Analysis

The key observation is that the change when shifting the boundary \(k\) one position to the right is small.

• \(S_1\) (left sum) simply has one element added
• \(S_2\) (right sum) can be immediately obtained by subtracting \(S_1\) from the total sum

In other words, there is no need to compute the interval sums from scratch each time.

Naive Approach

For each \(k\), computing - \(A_1+\cdots+A_k\) - \(A_{k+1}+\cdots+A_N\)

from scratch each time costs \(O(N)\) per boundary, and doing this \(N\) times gives a total of \(O(N^2)\). This is too slow for \(N \le 2\times10^5\) (TLE).

Improvement

First compute the total sum \(total=\sum A_i\), then incrementally increase the left sum left starting from 0. When placing the boundary at index \(i\) (0-indexed):

• \(S_1\) is obtained by left += A[i]
• \(S_2 = total - left\)
• The difference is abs(left - (total - left))

By checking this for \(i=0\) through \(N-2\), we cover all valid splits (\(1 \le k < N\)).

Algorithm

1. Read \(N\) and array \(A\)
2. Compute total = sum(A)
3. Initialize left = 0, ans = sufficiently large value
4. For i = 0 .. N-2, repeat:
   • left += A[i]
   • right = total - left
   • diff = abs(left - right)
   • ans = min(ans, diff)
5. Output ans

For example, when \(A=[1,2,3,4]\): - \(k=1\): \((1)\) vs \((2,3,4)\) → difference \(8\) - \(k=2\): \((1,2)\) vs \((3,4)\) → difference \(4\) - \(k=3\): \((1,2,3)\) vs \((4)\) → difference \(2\)

The minimum is \(2\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (only auxiliary variables, excluding the input array)

Implementation Notes

• The loop range should be range(N - 1) (to prevent the right team from being empty).

• In Python, there is almost no concern about integer overflow, but in other languages it is safe to use the equivalent of long long (since \(A_i\) can be large and the total sum can also be large).

• By setting the initial value to something sufficiently large like ans = 10**30, you can easily update the minimum.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))

    total = sum(A)
    left = 0
    ans = 10**30

    for i in range(N - 1):
        left += A[i]
        right = total - left
        diff = abs(left - right)
        if diff < ans:
            ans = diff

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.