Overview

This problem asks us to find the total number of ways to choose \(K\) sweets out of \(N\) such that the sum of their satisfaction values is at least \(X\).

Idea

If we try to search all possible combinations, the total number of ways can be up to \(_{36}\mathrm{C}_{18} \approx 9 \times 10^9\), which will not finish in time (resulting in TLE). For subset sum problems like this where the number of elements \(N\) is up to around 40, meet-in-the-middle is an effective technique.

We split the array into two halves: the first half and the second half. For each subset in both halves, we enumerate the “number of chosen elements” and the “sum of satisfaction values”. If we choose \(j\) elements in the first half, we need to choose \(K - j\) elements in the second half. If the sum chosen in the first half is \(s\), we look for choices in the second half with a sum of at least \(X - s\), allowing us to efficiently calculate the total number of valid combinations.

Algorithm

1. Split the array: Divide the \(N\) elements into the first half with \(N_1 = N / 2\) elements and the second half with \(N_2 = N - N_1\) elements.
2. Enumerate the first half: Use bitwise brute-force search to iterate over all ways to choose elements from the first half. For each count \(j\) of chosen elements, store the sum of satisfaction values in a list L_sums[j].
3. Enumerate the second half: Similarly, use bitwise brute-force search for the second half and store the satisfaction sums in R_sums[j] according to the count \(j\) of chosen elements.
4. Sort the second-half lists: Sort each list R_sums[j] to enable binary search.
5. Count valid combinations:
   • Consider choosing \(j\) elements (\(j = 0 \dots K\)) from the first half. In this case, we must choose \(K - j\) elements from the second half.
   • For each sum \(s\) stored in L_sums[j], the required sum from the right side is at least \(X - s\).
   • Perform a binary search on R_sums[K - j] to count the number of elements greater than or equal to \(X - s\), and add this count to the answer.

Complexity

• Time Complexity: \(O(2^{N/2} \log(2^{N/2}))\) The bitwise brute-force search takes \(O(2^{N/2})\), and sorting and binary searching take \(O(2^{N/2} \log(2^{N/2}))\). When \(N=36\), \(2^{18} \approx 2.6 \times 10^5\), which runs fast enough.
• Space Complexity: \(O(2^{N/2})\) This is proportional to the size of the lists storing the subset sums for the first and second halves.

Implementation Details

• Since the satisfaction values \(A_i\) of the sweets and their sums may exceed \(10^9\), use a 64-bit integer type (such as long long in C++) to prevent overflow.

• When performing binary search, using lower_bound on the sorted array allows us to quickly find the first iterator satisfying the condition “at least \(X - s\)”. The required count can be calculated as the distance from that iterator to the end of the array (end() - it).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    long long X;
    cin >> N >> K >> X;
    
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    int N1 = N / 2;
    int N2 = N - N1;
    
    vector<vector<long long>> L_sums(N1 + 1);
    vector<vector<long long>> R_sums(N2 + 1);
    
    for (int mask = 0; mask < (1 << N1); mask++) {
        long long sum = 0;
        int cnt = 0;
        for (int i = 0; i < N1; i++) {
            if (mask & (1 << i)) {
                sum += A[i];
                cnt++;
            }
        }
        L_sums[cnt].push_back(sum);
    }
    
    for (int mask = 0; mask < (1 << N2); mask++) {
        long long sum = 0;
        int cnt = 0;
        for (int i = 0; i < N2; i++) {
            if (mask & (1 << i)) {
                sum += A[N1 + i];
                cnt++;
            }
        }
        R_sums[cnt].push_back(sum);
    }
    
    for (int i = 0; i <= N2; i++) {
        sort(R_sums[i].begin(), R_sums[i].end());
    }
    
    long long ans = 0;
    for (int j = 0; j <= K; j++) {
        if (j > N1 || K - j > N2) continue;
        for (long long s : L_sums[j]) {
            long long target = X - s;
            auto it = lower_bound(R_sums[K - j].begin(), R_sums[K - j].end(), target);
            ans += R_sums[K - j].end() - it;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

This editorial was generated by or-glm5.2-high.