Overview

This problem asks us to find the number of ways to choose \(K\) sweets out of \(N\) such that the sum of their satisfaction values is at least \(X\). By focusing on the constraint \(N \le 36\), we can solve this efficiently using Meet-in-the-middle (half-enumeration).

Analysis

Naive Approach (Brute Force) and Its Limitations

The first idea is to try all possible combinations of choosing \(K\) sweets out of \(N\) (\({}_N \text{C}_K\) ways). However, when \(N = 36\) and \(K = 18\), the number of combinations is \({}_{36} \text{C}_{18} = 90,751,353,000 \approx 9 \times 10^{10}\), which will far exceed the time limit (usually around 2 seconds) resulting in Time Limit Exceeded (TLE).

Considering Dynamic Programming (DP)

We could also consider dynamic programming where the states represent the total satisfaction value. However, since the satisfaction value \(A_i\) of each sweet can be up to \(10^9\), this approach is impractical due to memory and time limits caused by the huge array size required.

Solution via Meet-in-the-Middle

Here, we focus on the constraint \(N \le 36\). Although brute-forcing all \(36\) elements directly is impossible, what if we split the array into two halves: the first half of \(N_1 = \lfloor N/2 \rfloor\) elements (at most 18) and the second half of \(N_2 = N - N_1\) elements (at most 18)?

Choosing a subset from 18 elements has only \(2^{18} = 262,144\) possibilities. This is small enough for a computer to compute in an instant.

Therefore, we can solve the problem with the following steps: 1. Enumerate all possible “sums of satisfaction values when choosing \(k_1\) sweets” from the first half. 2. Enumerate all possible “sums of satisfaction values when choosing \(k_2\) sweets” from the second half. 3. For combinations where \(k_1 + k_2 = K\), efficiently count the number of pairs satisfying (first half sum) + (second half sum) \(\ge X\).

Algorithm

1. Splitting the Sweets: Split the array of sweets \(A\) into the first half \(A_1\) (size \(N_1\)) and the second half \(A_2\) (size \(N_2\)).

2. Enumerating Sums: For each of \(A_1\) and \(A_2\), generate lists of total satisfaction values grouped by the number of chosen sweets \(c\).

   • sums1[c]: List of sums when choosing \(c\) sweets from the first half
   • sums2[c]: List of sums when choosing \(c\) sweets from the second half

3. Sorting: Sort each sums1[c] and sums2[c] in ascending order for efficient counting.

4. Counting via Two Pointers: Iterate over the number of sweets \(k_1\) chosen from the first half, from \(0\) to \(N_1\). In this case, the number of sweets chosen from the second half is fixed to \(k_2 = K - k_1\) (only process when \(0 \le k_2 \le N_2\)).

Count the number of pairs of elements s1 (from sums1[k1]) and s2 (from sums2[k2]) such that their sum is at least \(X\). When iterating through s1 in increasing order, the smallest position (index \(j\)) of s2 satisfying s1 + s2 >= X moves to the left (towards smaller values) as s1 grows larger. Utilizing this property, we can move pointer \(j\) from right to left using the “two pointers” technique to count the valid pairs efficiently for each \(k_1\).

Complexity

• Time Complexity: \(O(N \cdot 2^{N/2})\)

  • Enumerating the sums for the first and second halves takes \(O(2^{N/2})\) time.
  • Sorting and counting via two pointers takes \(O(N_1 \cdot 2^{N/2}) = O(N \cdot 2^{N/2})\) time.
  • When \(N = 36\), \(2^{18} \approx 2.6 \times 10^5\), leading to around \(N \cdot 2^{N/2} \approx 9.4 \times 10^6\) operations, which easily fits within the time limit.

• Space Complexity: \(O(2^{N/2})\)

  • Storing the enumerated sums for the first and second halves requires keeping \(2^{N_1} + 2^{N_2} \le 2 \times 2^{18} \approx 5.2 \times 10^5\) elements in memory.

Implementation Points

• Grouping by Count: It is important not just to enumerate the sums of satisfaction, but to group them by the “number of chosen sweets \(c\)”. This allows us to properly evaluate only those combinations where the total number of selected sweets is exactly \(K\).

• Direction of Two Pointers: When iterating through s1 in ascending order (from smallest to largest), the boundary \(j\) satisfying s1 + s2 >= X decreases as s1 increases. Therefore, by starting the pointer \(j\) from the end of the array and moving it to the left as long as the condition is satisfied, we can count the pairs in \(O(\text{len}(s1) + \text{len}(s2))\) time.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    K = int(input_data[1])
    X = int(input_data[2])

    A = [int(x) for x in input_data[3:]]

    N1 = N // 2
    N2 = N - N1

    A1 = A[:N1]
    A2 = A[N1:]

    def get_sums(arr):
        n = len(arr)
        res = [[] for _ in range(n + 1)]
        res[0].append(0)
        for x in arr:
            for c in range(n - 1, -1, -1):
                if res[c]:
                    res[c + 1].extend([s + x for s in res[c]])
        return res

    sums1 = get_sums(A1)
    sums2 = get_sums(A2)

    for c in range(N1 + 1):
        sums1[c].sort()
    for c in range(N2 + 1):
        sums2[c].sort()

    ans = 0

    for k1 in range(N1 + 1):
        k2 = K - k1
        if 0 <= k2 <= N2:
            s1_list = sums1[k1]
            s2_list = sums2[k2]
            len2 = len(s2_list)

            j = len2
            for s1 in s1_list:
                while j > 0 and s1 + s2_list[j - 1] >= X:
                    j -= 1
                ans += len2 - j

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.6-flash-high.