Overview

This problem asks us to divide \(N\) given snacks into two groups (Takahashi and Aoki) and minimize the difference between the total deliciousness of each group. This is a classic “subset sum problem” that can be solved efficiently using dynamic programming (DP).

Analysis

Brute Force Approach and Its Limitations

For each snack, there are 2 choices: “give to Takahashi” or “give to Aoki”. Since there are \(N\) snacks, the total number of ways to divide them is \(2^N\). Looking at the constraints, \(N \leq 200\). Since \(2^{200}\) is an extremely large value (approximately \(1.6 \times 10^{60}\)), naively trying all possible divisions would result in a Time Limit Exceeded (TLE) verdict.

Dynamic Programming (DP) Approach

When deciding how to divide the snacks, what matters is “the total deliciousness of the snacks Takahashi receives.” Let \(S\) be the total sum of all snack deliciousness values. If the total deliciousness of snacks Takahashi receives is \(T\), then Aoki’s total is automatically determined as \(S - T\). The absolute difference between the two totals can be expressed as: $\(|T - (S - T)| = |2T - S|\)$

Therefore, if we know “whether we can select a subset of snacks with total deliciousness equal to \(T\)”, we can compute \(|2T - S|\) for all achievable values of \(T\) and find the minimum. Here, we need to be careful about the condition “each person must receive at least one snack.” Takahashi’s total \(T\) must not be \(0\) (Takahashi gets 0 snacks) or \(S\) (Aoki gets 0 snacks). Thus, the range of \(T\) to search is \(1 \leq T \leq S - 1\).

Speeding Up the Subset Sum Problem

Since \(N \leq 200\) and \(A_i \leq 1000\), the total sum \(S\) is at most \(200 \times 1000 = 200,000\). We consider maintaining and updating an array dp[T] (boolean) that determines “whether a total of \(T\) can be achieved.” A standard DP approach requires \(O(N \times S)\) computation. With the given constraints, this amounts to \(200 \times 200,000 = 4 \times 10^7\) operations, which is fast enough with regular loops. However, by using C++’s std::bitset, we can achieve ultra-fast transitions through bitwise operations.

Algorithm

1. Compute the total sum \(S\) of all snack deliciousness values.
2. Prepare a dp array (std::bitset). dp[x] represents whether a total deliciousness of \(x\) is achievable (1 means possible, 0 means impossible). The initial state is dp[0] = 1, with all other bits set to 0.
3. For each snack \(A_i\), update dp in order.
   • When using std::bitset, the operation dp |= (dp << A_i) performs all transitions simultaneously with a single bitwise operation. This corresponds to taking the logical OR of “not selecting \(A_i\) (the original dp)” and “selecting \(A_i\) (dp << A_i)”.
4. For all \(T\) in the range \(1 \leq T < S\) where dp[T] is 1, compute \(|2T - S|\) and output the minimum value.

Concrete Example

For \(N=3\), \(A = [2, 3, 5]\): - Total sum \(S = 10\). - Initial state: bit 0 of dp is set (...0000000001) - Processing \(A_1 = 2\): bits 0, 2 of dp are set (...0000000101) - Processing \(A_2 = 3\): bits 0, 2, 3, 5 of dp are set (...0000101101) - Processing \(A_3 = 5\): bits 0, 2, 3, 5, 7, 8, 10 of dp are set (...10110101101) - The values of \(T\) in the range \(1 \leq T \leq 9\) where dp[T] is 1 are \(2, 3, 5, 7, 8\). - When \(T=5\), the absolute difference is \(|2 \times 5 - 10| = 0\), which is the minimum value.

Complexity

• Time Complexity: \(O\left(\frac{N \times S}{w}\right)\) Here, \(w\) is the word size (typically 64). With \(N \leq 200\) and \(S \leq 200,000\), the worst case involves approximately \(\frac{4 \times 10^7}{64} \approx 6.25 \times 10^5\) simple bit operations, running in just a few milliseconds.
• Space Complexity: \(O(S)\) Since we maintain a bitset of size \(S\), the required memory is approximately \(\frac{200,000}{8} \approx 25 \text{ KB}\), which is extremely memory-efficient.

Implementation Notes

• Utilizing std::bitset: By using C++’s std::bitset, the DP transition dp[j] = dp[j] | dp[j - A[i]] using arrays can be concisely and efficiently implemented as the single line dp |= (dp << A[i]) using bit shift and logical OR.

• Boundary Condition (at least one snack each): Since both Takahashi and Aoki must receive at least one snack, we need to exclude cases where either person gets 0 snacks (\(T = 0\) or \(T = S\)) and iterate the loop over \(1 \leq T < S\). Since the constraint guarantees \(N \ge 2\), there always exists a way to give at least one snack to each person.

  Source Code

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <bitset>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> A(N);
    int S = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        S += A[i];
    }

    const int MAX_S = 200005;
    bitset<MAX_S> dp;
    dp[0] = 1;

    for (int a : A) {
        dp |= (dp << a);
    }

    int min_diff = 1e9;
    for (int T = 1; T < S; ++T) {
        if (dp[T]) {
            int diff = abs(2 * T - S);
            if (diff < min_diff) {
                min_diff = diff;
            }
        }
    }

    cout << min_diff << "\n";

    return 0;
}

---

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