Overview

For each of \(N\) types of chemicals, we choose one of three options: “don’t use,” “normal mode,” or “heating mode,” and determine whether the total resulting solution is exactly \(K\) mL. We solve this efficiently using Meet in the Middle.

Analysis

Naive Approach and Its Limitations

Each chemical has three choices: “don’t use,” “normal mode (\(A_i\) mL),” or “heating mode (\(B_i\) mL).” If we brute-force all \(N\) chemicals, the number of combinations is \(3^N\).

• When \(N = 26\), \(3^{26} \approx 2.5 \times 10^{12}\), which is far too large to handle in time.

Key Insight: Split in Half

If we split the \(N\) chemicals into two groups (first half and second half), each group has about \(N/2 = 13\) items.

• \(3^{13} = 1{,}594{,}323\) combinations

This is fast enough to enumerate for each group. We compute the set of achievable total values for the first half and the set for the second half, then check whether there exists a pair such that “first half value + second half value = \(K\).”

Concrete Example

When \(N=4\), \(K=10\), and the chemicals are \((3,5), (2,4), (1,6), (7,3)\):

• First half \(\{(3,5), (2,4)\}\) → candidate totals: \(\{0, 2, 3, 4, 5, 7, 8, 9\}\)
• Second half \(\{(1,6), (7,3)\}\) → candidate totals: \(\{0, 1, 3, 4, 6, 7, 8, 9, 10, 13\}\)

Taking \(7\) from the first half and \(3\) from the second half gives \(7 + 3 = 10 = K\), so the answer is Yes.

Algorithm

1. Split the \(N\) chemicals into the first half (\(\lfloor N/2 \rfloor\) items) and the second half (the rest).
2. Enumerate all three choices for every chemical in the first half, and build the set of possible total values left_sums.
3. Similarly enumerate the second half and build the set right_sums (stored in a Python set).
4. For each element \(l\) in left_sums, check in \(O(1)\) whether \(K - l\) is contained in right_sums.
5. If any such pair is found, output Yes; otherwise, output No.

During enumeration, for the current set of candidates, for each chemical we generate three patterns: “keep as is (don’t use),” “\(+A_i\) (normal mode),” and “\(+B_i\) (heating mode),” progressively building up the candidates.

Complexity

• Time complexity: \(O(3^{N/2})\)
  • We enumerate \(3^{N/2}\) candidates for each of the first and second halves, and matching is done in \(O(1)\) per lookup using a set. When \(N = 26\), this is approximately \(3^{13} \approx 1.6 \times 10^6\), which is fast enough.
• Space complexity: \(O(3^{N/2})\)
  • For storing the candidate total values of each group in a set.

Implementation Notes

• Enumeration implementation: Using a set and processing chemicals one by one to expand candidates is concise.

• \(K\) can be up to \(10^{15}\): Python natively supports arbitrary-precision integers, so there is no concern about overflow.

• Selecting 0 chemicals: By including a total of \(0\) as the initial value, this case is handled naturally (when \(K = 0\), selecting nothing is the valid case).

• Splitting into first and second halves: Splitting as evenly as possible minimizes the maximum number of enumerations.

  Source Code

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    
    items = []
    for i in range(N):
        a = int(input_data[2 + 2*i])
        b = int(input_data[3 + 2*i])
        items.append((a, b))
    
    # Meet in the middle approach
    # Each item has 3 choices: not used (0), normal mode (A_i), heated mode (B_i)
    # Split into two halves
    
    half1 = N // 2
    half2 = N - half1
    
    def enumerate_sums(item_list):
        """Enumerate all possible sums from a list of items."""
        sums = {0}
        for a, b in item_list:
            new_sums = set()
            for s in sums:
                new_sums.add(s)       # don't use this item
                new_sums.add(s + a)   # normal mode
                new_sums.add(s + b)   # heated mode
            sums = new_sums
        return sums
    
    left_items = items[:half1]
    right_items = items[half1:]
    
    left_sums = enumerate_sums(left_items)
    right_sums = enumerate_sums(right_items)
    
    # Check if any left_sum + right_sum == K
    # Store right_sums in a set, then for each left_sum check if K - left_sum is in right_sums
    right_set = right_sums
    
    for ls in left_sums:
        if K - ls in right_set:
            print("Yes")
            return
    
    print("No")

solve()

---

This editorial was generated by claude4.6opus-thinking.