Overview

This problem asks us to find the total number of ways to choose \(K\) items out of \(N\) sweets such that the sum of their satisfaction values is at least \(X\). Given the constraint \(N \leq 36\), we use the Meet-in-the-Middle technique.

Analysis

First, let us consider a naive approach: enumerating all combinations of choosing \(K\) items from \(N\) items and checking if their sum is at least \(X\). However, the number of combinations can be as large as \(\binom{36}{18} \approx 9 \times 10^9\), making full enumeration impossible within a realistic time limit.

On the other hand, enumerating “all subsets” results in \(2^{36} \approx 6.8 \times 10^{10}\) possibilities, which is also too slow as is.

The key observation here is that if we split \(N\) in half, the number of subsets for each half is at most \(2^{18} \approx 2.6 \times 10^5\). By using “Meet in the Middle”, we can enumerate subsets for each half first and then combine them efficiently, drastically reducing the computational complexity.

Specifically, we divide the sweets into the first half of \(n_1\) items and the second half of \(n_2\) items, and consider combinations of: - the number of items chosen from the first half and their sum \(s_1\) - the number of items chosen from the second half and their sum \(s_2\)

We just need to count the pairs such that the total number of chosen items is \(K\) and \(s_1 + s_2 \geq X\).

Algorithm

We use Meet in the Middle.

Step 1: Enumerate for the first and second halves

Divide the sweets into the first half of \(n_1 = \lfloor N/2 \rfloor\) items and the second half of \(n_2 = N - n_1\) items.

For the first half, enumerate all \(2^{n_1}\) subsets and store their sum values into a list left[c1] according to the “number of chosen items \(c_1\)”. Similarly, construct right[c2] for the second half.

Step 2: Sort the second half

Sort each list right[c2] of the second half in ascending order. This is to perform binary search later.

Step 3: Count combinations

Iterate over the number of chosen items in the first half \(c_1\) from \(0\) to \(n_1\), and set the number of items to choose from the second half as \(c_2 = K - c_1\) (skip if out of range).

For each sum \(s_1\) from the first half, count the number of sums \(s_2\) from the second half that satisfy the condition \(s_1 + s_2 \geq X\), which is equivalent to \(s_2 \geq X - s_1\).

Since right[c2] is sorted, using lower_bound to find the first position that is at least \(X - s_1\) gives the number of valid elements as the number of elements from that position onwards. Summing this up for all \(s_1\) yields the answer.

Concrete Example: Suppose \(N=4, K=2, X=10\), and \(A = [3, 6, 4, 8]\). Divide into the first half \(\{3, 6\}\) and the second half \(\{4, 8\}\). - \(c_1=0, c_2=2\): Sum of the first half is \(0\), and the sum of choosing 2 items from the second half is \(\{12\}\). Since \(12 \geq 10\), there is 1 way. - \(c_1=1, c_2=1\): Sums of the first half are \(\{3, 6\}\), and sums of choosing 1 item from the second half are \(\{4, 8\}\). Since \(3+8=11\geq10\), \(6+4=10\geq10\), and \(6+8=14\geq10\), there are 3 ways. - \(c_1=2, c_2=0\): Sum of the first half is \(\{9\}\), and the sum of choosing 0 items from the second half is \(\{0\}\). Since \(9 < 10\), there are 0 ways.

The total is \(4\) ways.

Complexity

Let the half size be \(M = N/2\).

• Time Complexity: Enumeration takes \(O(2^M \cdot M)\), sorting takes \(O(2^M \cdot M)\), and counting via binary search takes \(O(2^M \cdot M)\), leading to an overall time complexity of \(O(2^{N/2} \cdot N)\). Even for \(N=36\), this is around \(2^{18} \times 36 \approx 10^7\) operations, which runs quickly.
• Space Complexity: \(O(2^{N/2})\) to store the sum values of all subsets.

Implementation Points

• Beware of integer overflow: Since \(A_i \leq 10^9\) and we handle the sum of up to \(36\) items, the maximum total sum can reach \(3.6 \times 10^{10}\). Since this overflows standard 32-bit integers (int), be sure to use 64-bit integers (long long) for sums, \(X\), and the answer.

• Categorize by item count: By separating lists according to the “number of chosen items” rather than just storing sums, we can easily handle the count constraint \(c_1 + c_2 = K\).

• Use binary search: Sorting the second half and using lower_bound to count the “number of elements greater than or equal to a value” in \(O(\log)\) time is the core of this approach. Checking all pairs directly would take \(O(2^{N/2} \times 2^{N/2})\), which will TLE.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;
    long long X;
    scanf("%d %d %lld", &N, &K, &X);
    vector<long long> A(N);
    for(int i=0;i<N;i++) scanf("%lld", &A[i]);
    
    int n1 = N/2;
    int n2 = N - n1;
    
    // left: for each count, list of sums
    vector<vector<long long>> left(n1+1), right(n2+1);
    
    for(int mask=0; mask<(1<<n1); mask++){
        int cnt = __builtin_popcount(mask);
        long long sum = 0;
        for(int i=0;i<n1;i++) if(mask&(1<<i)) sum += A[i];
        left[cnt].push_back(sum);
    }
    for(int mask=0; mask<(1<<n2); mask++){
        int cnt = __builtin_popcount(mask);
        long long sum = 0;
        for(int i=0;i<n2;i++) if(mask&(1<<i)) sum += A[n1+i];
        right[cnt].push_back(sum);
    }
    
    for(int c=0;c<=n2;c++) sort(right[c].begin(), right[c].end());
    
    long long ans = 0;
    for(int c1=0;c1<=n1;c1++){
        int c2 = K - c1;
        if(c2 < 0 || c2 > n2) continue;
        auto& R = right[c2];
        for(long long s1 : left[c1]){
            long long need = X - s1;
            // count of R >= need
            int idx = lower_bound(R.begin(), R.end(), need) - R.begin();
            ans += (long long)(R.size() - idx);
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.