Overview

Given \(N\) chemicals, each with three choices — “don’t use”, “normal mode (\(A_i\) mL)”, or “heated mode (\(B_i\) mL)” — the problem asks whether it is possible to make the total volume exactly \(K\) mL.

Analysis

Since there are 3 choices for each chemical, naively checking all combinations would result in a computational complexity of \(3^N\). Given the constraint \(N \le 26\), we get \(3^{26} \approx 2.5 \times 10^{12}\), making it impossible to complete a brute-force search within the time limit.

On the other hand, if we consider another classic technique, dynamic programming (DP), the target volume \(K\) can be as large as \(10^{15}\), so a DP indexed by the sum is also infeasible.

Therefore, we utilize a technique called “Meet-in-the-middle”. By splitting the \(N\) elements into two halves (\(N/2\) each) and enumerating all combinations separately for each group, the number of combinations per group becomes \(3^{N/2}\). For \(N=26\), we have \(3^{13} = 1,594,323\), which is well within a manageable range.

Algorithm

The procedure for meet-in-the-middle is as follows:

1. Split into groups: Divide the \(N\) chemicals into the first \(N/2\) and the remaining ones.
2. Enumerate (first half): For the first half of the chemicals, enumerate all possible total volumes and store them in a set (e.g., a Set).
   • At this point, totals exceeding \(K\) can be excluded (since all chemical volumes are positive).
3. Enumerate (second half): Similarly, enumerate all possible total volumes for the second half of the chemicals.
4. Matching: For each total volume \(s_2\) obtained from the second half group, check whether a value \(s_1 = K - s_2\) exists in the set from the first half group.
   • If such a value exists, it is possible to achieve a total of \(K\) (Yes).
   • If no match is found after checking all \(s_2\), it is impossible (No).

Complexity

• Time complexity: \(O(3^{N/2})\)
  • The enumeration for each half takes \(3^{N/2}\), and the matching step takes roughly a constant factor times \(3^{N/2}\). For \(N=26\), \(3^{13} \approx 1.6 \times 10^6\), so it runs fast enough even in Python.
• Space complexity: \(O(3^{N/2})\)
  • Memory for storing up to \(3^{N/2}\) elements is needed to hold all possible total volumes from the first half group.

Implementation Tips

• Using a set: By storing the first half’s total volumes in a set, the lookup “does this value exist?” during the second half’s search can be performed in average \(O(1)\) time.

• Pruning: By discarding combinations as soon as the total exceeds \(K\), we can reduce both memory consumption and computation time.

• Efficient enumeration: The implementation goes smoothly by processing chemicals one by one: for the current “set of possible sums,” create a new set by adding \(0, A_i, B_i\) from the new chemical to each existing sum.

  Source Code

import sys

def solve():
    # Fast input reading from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of drugs, K is the target volume
    N = int(input_data[0])
    K = int(input_data[1])
    
    A = []
    B = []
    for i in range(N):
        A.append(int(input_data[2 + 2*i]))
        B.append(int(input_data[3 + 2*i]))
        
    # Using the meet-in-the-middle technique to reduce complexity from 3^N to 3^(N/2)
    # N <= 26, so 3^26 is too large (~2.5 * 10^12), but 3^13 is manageable (~1.6 * 10^6)
    mid = N // 2
    
    def get_possible_sums(a_part, b_part, target):
        """
        Calculates all possible sums of solution volumes for a given set of drugs.
        Each drug can be used in mode A, mode B, or not at all.
        """
        ps = {0}
        for a, b in zip(a_part, b_part):
            # For each drug, there are three choices for its contribution to the sum:
            # 1. Not used: The sum remains s (already present in ps).
            # 2. Mode A: The sum becomes s + a.
            # 3. Mode B: The sum becomes s + b.
            # Pruning sums that already exceed the target volume K.
            new_a = {s + a for s in ps if s + a <= target}
            new_b = {s + b for s in ps if s + b <= target}
            
            # Update the set of possible sums with the new options
            ps |= new_a
            ps |= new_b
        return ps

    # Generate all possible sums for the two halves of the drugs
    sums1 = get_possible_sums(A[:mid], B[:mid], K)
    sums2 = get_possible_sums(A[mid:], B[mid:], K)
    
    # Meet-in-the-middle check:
    # We need to find if there exists s1 in sums1 and s2 in sums2 such that s1 + s2 = K.
    # This is equivalent to checking if (K - s1) exists in sums2.
    
    # Optimization: Iterate over the smaller set to minimize the number of lookups
    if len(sums1) > len(sums2):
        sums1, sums2 = sums2, sums1
        
    found = False
    for s in sums1:
        if (K - s) in sums2:
            found = True
            break
    
    # Output the result
    if found:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.