Overview

This problem asks us to distribute \(N\) snacks between two people, where each person must receive at least one snack, minimizing the absolute difference of the total deliciousness. We solve it using dynamic programming (DP) on subset sums.

Analysis

Reformulating the Problem

Let the total deliciousness of all snacks be \(S\). If Takahashi receives snacks with total deliciousness \(T\), then Aoki’s total is \(S - T\). The absolute difference is \(|T - (S - T)| = |2T - S|\).

In other words, the problem reduces to choosing a subset of 1 to \(N-1\) snacks from the \(N\) snacks, and minimizing \(|2T - S|\) where \(T\) is the subset sum.

Naive Approach

Enumerating all possible distributions gives \(2^N - 2\) cases, which is far too many for \(N \leq 200\).

Solution with DP

We treat this as a subset sum problem and use DP to track “which total values are achievable.” However, since we have the constraint of “choosing at least 1 and at most \(N-1\) items,” we record the minimum and maximum number of items selected for each total value. For a given total value \(s\), if the minimum count is at most \(N-1\) and the maximum count is at least \(1\), then a valid distribution exists.

Algorithm

1. Compute the total sum \(S = \sum A_i\).
2. Prepare a DP table as a dictionary dp, where dp[s] = (min_count, max_count) manages “the minimum and maximum number of items needed to achieve total \(s\).” The initial state is dp[0] = (0, 0).
3. For each snack \(a\), perform transitions for “take” and “don’t take,” updating the DP:
   • Don’t take: the total and count remain unchanged
   • Take: the total becomes \(s + a\), and the count increases by \(1\)
   • When multiple counts correspond to the same total value, only the minimum and maximum are retained
4. After processing all snacks, for each achievable total value \(s\), check whether there exists a count in the range \([1, N-1]\), and find the minimum value of \(|2s - S|\).

Concrete Example

For \(N = 3\), \(A = [1, 2, 3]\), we have \(S = 6\).

• Subset sum \(1\) (1 item) → \(|2 \cdot 1 - 6| = 4\)
• Subset sum \(2\) (1 item) → \(|2 \cdot 2 - 6| = 2\)
• Subset sum \(3\) (1 item or 2 items) → \(|2 \cdot 3 - 6| = 0\) ← minimum!
• Subset sum \(4\) (2 items) → \(|2 \cdot 4 - 6| = 2\)
• Subset sum \(5\) (2 items) → \(|2 \cdot 5 - 6| = 4\)

The answer is \(0\) (for example, Takahashi gets \(\{3\}\), Aoki gets \(\{1, 2\}\)).

Complexity

• Time complexity: \(O(N \cdot S)\) (\(S = \sum A_i \leq 200000\))
  • For each snack, we scan and update all entries in the DP table
• Space complexity: \(O(S)\)
  • The number of entries in the DP table is at most \(S+1\)

Implementation Notes

• By only retaining the minimum and maximum number of items selected for each total value, we keep memory and computation costs low. Even if not all intermediate counts are achievable, it suffices to check whether the min/max range overlaps with \([1, N-1]\).

• By writing both “take” and “don’t take” transitions into a new dictionary during DP updates, we prevent using the same snack more than once.

• Since \(N \geq 2\), we need to exclude the case where one person takes all snacks (count \(0\) or \(N\)), but this is naturally handled by the min/max check.

  Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    S = sum(A)
    
    # DP: dp[s] = True if subset sum s is achievable
    # We need subsets of size 1 to N-1
    # dp[j] = set of possible subset sizes that achieve sum j, but simpler:
    # Track (sum, count) pairs
    # Since N<=100 and S<=100000, use dp[s] as a set of possible counts, or
    # just track dp[s] = bitmask of possible counts... N<=100 so bitmask too large
    
    # Alternative: dp[s] = (min_count, max_count) of items that can form sum s
    # We need count >= 1 and count <= N-1
    # If any achievable count for sum s is in [1, N-1], it's valid
    
    # Better: dp[s] stores min and max number of items to achieve sum s
    # If min_count <= N-1 and max_count >= 1, then valid
    
    # dp as dict: sum -> (min_items, max_items)
    # Initialize: dp[0] = (0, 0)
    
    dp = {0: (0, 0)}
    
    for a in A:
        new_dp = {}
        for s, (mn, mx) in dp.items():
            # Don't take this item
            if s not in new_dp:
                new_dp[s] = (mn, mx)
            else:
                old_mn, old_mx = new_dp[s]
                new_dp[s] = (min(old_mn, mn), max(old_mx, mx))
            # Take this item
            ns = s + a
            nmn, nmx = mn + 1, mx + 1
            if ns not in new_dp:
                new_dp[ns] = (nmn, nmx)
            else:
                old_mn, old_mx = new_dp[ns]
                new_dp[ns] = (min(old_mn, nmn), max(old_mx, nmx))
        dp = new_dp
    
    ans = float('inf')
    for s, (mn, mx) in dp.items():
        # Check if there's a valid count (between 1 and N-1)
        if mx >= 1 and mn <= N - 1:
            diff = abs(S - 2 * s)
            ans = min(ans, diff)
    
    print(ans)

solve()

---

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