Overview

This problem asks you to divide \(N\) players into 2 teams and maximize the smaller of the two teams’ total strengths \(S_1, S_2\). This can be reduced to a “subset sum problem”: given the total strength of all players as \(T\), find the maximum \(S_1\) satisfying \(S_1 \leq \lfloor T/2 \rfloor\).

Analysis

1. Reduction to the Subset Sum Problem

If we let the total strength of Team 1 be \(S_1\), then the total strength of Team 2 is \(S_2 = T - S_1\). To maximize \(\min(S_1, S_2)\), we should make \(S_1\) as close to \(T/2\) as possible. Therefore, the problem becomes: among all possible sums formed by selecting some of the given \(A_i\), find the maximum value that does not exceed \(T/2\).

2. Naive Dynamic Programming (DP) and Its Limitations

Normally, the subset sum problem is solved with the following DP: - dp[j] : whether it is possible to make a sum of \(j\) (boolean value)

The recurrence is dp[j] = dp[j] | dp[j - A_i]. However, under the given constraints, \(N \leq 2 \times 10^4\) and \(\sum A_i \leq 2 \times 10^5\). A straightforward DP would have a time complexity of \(O(N \times \sum A_i) \approx 4 \times 10^9\), which will not fit within the time limit.

3. Optimization Techniques

To solve this problem, we combine two important optimizations.

• Bitset Optimization We treat the DP table as a bit sequence of a “very large integer.” In Python, integers have no size limit, so we can use huge integers as bitsets. With the single statement dp |= (dp << A_i), all states can be updated at once, dramatically improving the computation time (since it is internally processed in parallel at the word-size level, a speedup of roughly 64x can be expected).

• Binary Decomposition for Bounded Knapsack DP When the same value of \(A_i\) appears multiple times, processing them one by one is inefficient. If a value \(v\) appears \(c\) times, we split them into groups with weights \(1, 2, 4, \dots, 2^k, \text{remainder}\). This way, only \(\log c\) updates are needed for a count of \(c\), significantly reducing the computation.

Algorithm

1. Compute the total strength \(T\) of all players and set the target value target = \(T // 2\).
2. Count the occurrences of each strength value \(A_i\).
3. Initialize the DP variable dp to \(1\) (only the 0th bit is set).
4. For each strength value \(v\) and its count \(c\), perform binary decomposition.
   • Increase \(k = 1, 2, 4, \dots\), performing dp |= (dp << (v * k)) and subtracting \(k\) from the count \(c\).
   • Process the remaining count in the same manner.
   • Always apply dp &= mask to trim unnecessary bits exceeding target.
5. The index of the highest set bit in the final dp (dp.bit_length() - 1) is the answer.

Complexity

• Time Complexity: \(O\left(\frac{T \cdot \sum \log(\text{counts})}{w}\right)\) \(T = \sum A_i\), and \(w\) is the machine’s word size (depends on Python’s internal implementation). By grouping players with the same value, the effective \(N\) becomes very small, and combined with the speedup from bitwise operations, this comfortably fits within the time limit.
• Space Complexity: \(O(T)\) This is the memory required to hold the large integer (bitset). \(T = 2 \times 10^5\) bits is approximately 25 KB, which is very lightweight.

Implementation Notes

• Python’s large integers: dp |= (dp << shift) is a standard technique in Python that achieves speedups similar to std::bitset in other languages.

• Masking: By applying dp &= mask, we exclude bits exceeding target from the computation. This prevents the integer from growing excessively in size and maintains computation speed.

• bit_length(): This method returns the length of the integer in binary representation, which can be used to efficiently obtain the “highest index where a 1 bit is set.”

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、空白で分割します。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # Nは選手の人数です。
    N = int(data[0])
    # Aは各選手の力のリストです。
    # 最初の要素Nを除いた、N個の整数を読み込みます。
    A = map(int, data[1:N+1])
    
    # 各力の値の出現回数をカウントし、全選手の力の総和を計算します。
    counts = {}
    total_sum = 0
    for x in A:
        counts[x] = counts.get(x, 0) + 1
        total_sum += x
        
    # 目標値は力の総和の半分（切り捨て）です。
    # min(S1, S2) を最大化することは、S1 <= total_sum // 2 を満たす最大の S1 を見つけることと同じです。
    target = total_sum // 2
    
    # dpはビットセットとして機能する大きな整数です。
    # i番目のビットが1であることは、力の和としてiが作れることを意味します。
    # 初期状態では和0が可能なので、0番目のビットを1（dp = 1）にします。
    dp = 1
    
    # targetまでのビットを保持するためのマスクを作成します。
    # これにより、targetを超える無駄な計算を省き、ビットセットのサイズを抑えます。
    mask = (1 << (target + 1)) - 1
    
    # 同じ力の値が複数ある場合、個数制限付き部分和問題を効率的に解くために
    # バイナリ分割（2進数分割）のテクニックを使用します。
    # これにより、計算量を O(target * N) から O(target * Σ log(counts)) に削減できます。
    for v, c in counts.items():
        # 力の値自体が目標値を超えている場合、その選手をチームに入れると target を超えるため無視します。
        if v > target:
            continue
        
        # 個数 c を 1, 2, 4, ..., 2^k, 残り という形式で分割します。
        k = 1
        while k <= c:
            # v * k の分だけビットを左シフトしてOR演算を行うことで、
            # 新たに作れるようになった和のビットを立てます。
            dp |= (dp << (v * k))
            # targetを超えるビットをマスクで落とします。
            dp &= mask
            c -= k
            k *= 2
        
        # 残りの個数がある場合、それについても同様に処理します。
        if c > 0:
            dp |= (dp << (v * c))
            dp &= mask
            
    # dp.bit_length() - 1 は、dpの中で最も高い位置にある1のビットのインデックスを返します。
    # これが target 以下の範囲で作れる最大の和（S1）になります。
    print(dp.bit_length() - 1)

if __name__ == "__main__":
    solve()

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