Overview

When dividing snacks into Takahashi’s set and Aoki’s set, we want to find the minimum absolute difference between their “total deliciousness” values.
This is a problem of “creating a subset sum as close to half the total as possible” (a subset sum problem).

Analysis

First, let the total deliciousness be \(S=\sum A_i\).
If Takahashi receives a total of \(x\), then Aoki receives \(S-x\). The difference we want to minimize is:

\[ |x-(S-x)| = |S-2x| \]

In other words, we need to find the value of \(x\) (a subset sum) that minimizes \(|S-2x|\).

Why a naive approach doesn’t work

If we consider each snack as either “given to Takahashi / given to Aoki”, there are \(2^N\) possible divisions. With \(N\le 200\), exhaustive search is impossible (\(2^{200}\) is astronomically large).

How to solve it

We use dynamic programming (subset sum DP) to determine “which total values \(x\) are achievable”.
Furthermore, in Python, by representing a bitset as an integer, we can efficiently update it with operations like dp |= dp << a.

Also, since the condition requires “both must have at least one snack”: - Takahashi’s total \(x=0\) (receiving nothing) is forbidden - \(x=S\) (receiving everything) is also forbidden
Therefore, we only consider \(x\) in the range \(1 \le x \le S-1\).

Algorithm

1. Compute the total sum \(S\).
2. Perform bitset DP.
   
   • Maintain dp such that “if sum \(x\) is achievable, then the \(x\)-th bit of dp is 1”.
   • Initial state is dp = 1 (sum 0 is achievable).
   • For each snack’s deliciousness \(a\):
     dp |= dp << a
     This reflects that “for every sum already achievable, adding \(a\) to it also becomes achievable” in one operation.
3. Check all \(x\) from \(1\) to \(S-1\), and among achievable \(x\), output the minimum value of \(|S-2x|\).

(Example) When \(A=[3,5,8]\), \(S=16\). The idea is to find the achievable \(x\) where \(2x\) is closest to 16 (i.e., \(x\) is closest to 8).

Complexity

• Time complexity: \(O\!\left(N \cdot \frac{S}{w}\right)\) (bitset bit operations, where \(w\) is the machine word size equivalent)
  ※This is significantly faster in practice than the naive subset sum DP of \(O(NS)\).
• Space complexity: \(O(S)\) (the bit string representing reachable sums)

Implementation Notes

• By holding dp as a single Python integer, we can perform bulk updates using left shift and OR, which is fast.

• To satisfy “both must have at least one”, the final check restricts x to range(1, S) (i.e., \(1 \le x \le S-1\)).

• The difference is computed as abs(S - 2*x) (corresponding to \(|S-2x|\)).

  Source Code

import sys

def main():
    it = iter(sys.stdin.read().split())
    N = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    S = sum(A)

    dp = 1  # bitset: dp[x]=1 if sum x is achievable
    for a in A:
        dp |= dp << a

    ans = S
    for x in range(1, S):  # both must be non-empty => exclude 0 and S
        if (dp >> x) & 1:
            diff = abs(S - 2 * x)
            if diff < ans:
                ans = diff

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.