Overview

This problem asks you to divide \(N\) players into 2 teams and maximize the total strength of the team with the smaller sum. This reduces to the classic Partition Problem.

Analysis

Rephrasing the Problem

Let \(S\) be the total sum of all players’ strengths. If team 1 has a total of \(S_1\), then team 2 has a total of \(S_2 = S - S_1\). To maximize \(\min(S_1, S_2)\), we should make \(S_1\) as close to \(S/2\) as possible.

In other words, the problem reduces to selecting a subset of players such that the sum of their strengths is maximized while not exceeding \(\lfloor S/2 \rfloor\).

Naive Approach

The subset sum problem is typically solved using a DP array dp[j] = “whether a sum of \(j\) can be achieved (true/false)”. The array size is \(S\), and we update it for each element, giving \(O(N \times S)\).

Since \(N \leq 2 \times 10^4\) and \(S \leq 2 \times 10^5\), the value of \(N \times S\) can be up to \(4 \times 10^9\), which risks TLE with a straightforward loop.

Speedup Using Bitsets

Since each element of the DP array is true/false (1 bit), it can be represented as individual bits of a large integer. Specifically, if the \(j\)-th bit of integer mask is 1, it means “a sum of \(j\) is achievable”.

• Initial state: mask = 1 (only bit 0 is 1 → a sum of 0 is achievable)
• When adding a player’s strength \(a\): mask |= (mask << a)

mask << a corresponds to “the set of all previously achievable sums with \(a\) added to each”. By taking the OR, we retain both the case of “not using \(a\)” and “using \(a\)”.

Example: \(A = [3, 5, 2]\), \(S = 10\), \(\lfloor S/2 \rfloor = 5\)

Step	mask (binary, bit 0 on the right)	Achievable sums
Initial	...0001	{0}
After processing \(a=3\)	...1001	{0, 3}
After processing \(a=5\)	...100101001	{0, 3, 5, 8}
After processing \(a=2\)	...10100110101	{0, 2, 3, 5, 7, 8, 10}

The maximum achievable value \(\leq 5\) is 5 → the answer is \(5\).

Algorithm

1. Compute the total sum of all players’ strengths \(S\), and set \(\text{target} = \lfloor S/2 \rfloor\).
2. Using a bitset (Python’s arbitrary-precision integer), determine all achievable subset sums.
3. Search in descending order from \(\text{target}\) down to \(0\), and output the maximum achievable value.

Complexity

• Time complexity: \(O(N \times S / w)\)
  • \(w\) is the word size (typically 64). Bit shift and OR operations allow each update to be performed in \(O(S/w)\).
  • Since \(N \leq 2 \times 10^4\) and \(S \leq 2 \times 10^5\), this is sufficiently fast in practice.
• Space complexity: \(O(S / w)\)
  • We store a single large integer’s bit sequence.

Implementation Notes

• The key point is leveraging Python’s arbitrary-precision integers as a bitset. Since Python has no limit on integer bit length, the DP array can be represented as a single integer, and bulk updates can be performed using bit shift and OR operations.

• In C++ and similar languages, the same speedup can be achieved using std::bitset.

• Finally, by checking mask & (1 << j), we can determine whether bit \(j\) is set, i.e., whether a sum of \(j\) is achievable.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = [int(input_data[i+1]) for i in range(N)]
    
    S = sum(A)
    target = S // 2
    
    # Bitset DP for subset sum
    mask = 1
    for a in A:
        mask |= (mask << a)
    
    # Find largest achievable sum <= target
    for j in range(target, -1, -1):
        if mask & (1 << j):
            print(j)
            return

main()

---

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