Overview

This is a problem where you need to find the number of ways to select from \(N\) candies such that the total price is exactly \(S\) yen. We solve it efficiently using Meet in the Middle.

Analysis

Problems with the Naive Approach

Since each candy has \(2\) choices (“select” or “don’t select”), there are \(2^N\) total ways to choose.

• If \(N \leq 20\) or so, \(2^{20} \approx 10^6\), so full enumeration is feasible
• However, if \(N \leq 40\), then \(2^{40} \approx 10^{12}\), making full enumeration impossible

Key Insight

If we split the \(N\) elements in half and consider: - Subset sums of the first \(N/2\) elements: \(2^{20} \approx 10^6\) possibilities - Subset sums of the second \(N/2\) elements: \(2^{20} \approx 10^6\) possibilities

When selecting sum \(s_1\) from the first half and sum \(s_2\) from the second half, we need \(s_1 + s_2 = S\). In other words, for each sum \(s_1\) from the first half, if we can quickly count the number of sums equal to \(S - s_1\) in the second half, we can solve the problem.

Algorithm

We use Meet in the Middle.

Procedure

1. Enumerate the first half: Split the candies into the first \(N/2\) and the remaining \(N - N/2\)
2. Calculate subset sums:
   • For all \(2^{N/2}\) subsets of the first half, calculate the total price and store in list first_sums
   • Do the same for the second half and store in second_sums
3. Sort and binary search:
   • Sort second_sums
   • For each element \(s\) in first_sums, use binary search to count the number of elements in second_sums equal to \(S - s\)

Concrete Example

For \(N = 4\), \(S = 5\), \(A = [1, 2, 3, 4]\):

• Subset sums of first half \([1, 2]\): \(\{0, 1, 2, 3\}\)
• Subset sums of second half \([3, 4]\): \(\{0, 3, 4, 7\}\)

When first half sum \(s = 1\), search for \(5 - 1 = 4\) in second half → Found \(1\) (selecting only candy \(4\)) When first half sum \(s = 2\), search for \(5 - 2 = 3\) in second half → Found \(1\) (selecting only candy \(3\))

In this way, we efficiently count combinations where \(s_1 + s_2 = S\).

Complexity

• Time complexity: \(O(2^{N/2} \cdot N/2 + 2^{N/2} \log 2^{N/2}) = O(N \cdot 2^{N/2})\)
  • Enumerating subsets and calculating sums: \(O(N \cdot 2^{N/2})\)
  • Sorting: \(O(2^{N/2} \cdot N/2)\)
  • Binary search \(2^{N/2}\) times: \(O(2^{N/2} \cdot N/2)\)
• Space complexity: \(O(2^{N/2})\)
  • Storing subset sums for both first and second halves

When \(N = 40\), \(2^{20} \approx 10^6\), which is sufficiently fast.

Implementation Notes

• Enumerate subsets using bitmask: If the \(i\)-th bit of mask is \(1\), select the \(i\)-th element
• Count using binary search: The difference between bisect_left and bisect_right gives the count of elements equal to a given value
• Watch for overflow: Although \(S\) and \(A_i\) can be as large as \(10^{12}\), Python uses arbitrary-precision integers, so there’s no problem
• Consider the empty set: When the mask is \(0\), the sum is \(0\), which is also treated as a valid selection (selecting nothing)

Source Code

import sys
from collections import defaultdict
from bisect import bisect_left, bisect_right

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    S = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # Meet in the Middle
    # Split N elements in half and enumerate all subset sums for each half
    
    half = N // 2
    first_half = A[:half]
    second_half = A[half:]
    
    # Enumerate all subset sums of the first half
    first_sums = []
    for mask in range(1 << len(first_half)):
        total = 0
        for i in range(len(first_half)):
            if mask & (1 << i):
                total += first_half[i]
        first_sums.append(total)
    
    # Enumerate all subset sums of the second half
    second_sums = []
    for mask in range(1 << len(second_half)):
        total = 0
        for i in range(len(second_half)):
            if mask & (1 << i):
                total += second_half[i]
        second_sums.append(total)
    
    # Sort the second half list
    second_sums.sort()
    
    # For each sum in the first half, count elements equal to S - sum in the second half using binary search
    ans = 0
    for s in first_sums:
        target = S - s
        if target < 0:
            continue
        # Count the number of elements in second_sums equal to target
        left = bisect_left(second_sums, target)
        right = bisect_right(second_sums, target)
        ans += right - left
    
    print(ans)

solve()

---

This editorial was generated by claude4.5opus.