Overview

Given \(N\) light bulbs that are initially off, there are \(M\) switches, each of which toggles (flips on/off) specified light bulbs. The problem asks for the “minimum number of switches to press” such that, after pressing some switches, exactly \(K\) bulbs are lit.

Since the number of switches \(M\) is at most \(23\), which is small, we can solve this efficiently using Meet-in-the-middle.

---

Analysis

1. Naive Brute Force and Its Limitations

For each switch, there are \(2\) choices: “press” or “don’t press.” With \(M\) switches, there are \(2^M\) total combinations. When \(M \leq 23\), this gives \(2^{23} \approx 8.4 \times 10^6\) combinations.

In fast languages like C++, brute-forcing all \(2^{23}\) combinations might fit within the time limit. However, in interpreted languages like Python, performing “bulb state computation” and “popcount (counting lit bulbs)” for each state causes TLE (Time Limit Exceeded) due to constant factor overhead within the typical 2-second time limit.

2. Speeding Up with Meet-in-the-Middle

We split the set of switches into a first half of \(M_1\) switches and a second half of \(M_2\) switches. - \(M_1 = \lfloor M/2 \rfloor\) (at most \(11\)) - \(M_2 = M - M_1\) (at most \(12\))

With this split, the number of combinations for each group is at most \(2^{11} = 2048\) and \(2^{12} = 4096\) respectively, which are very small.

1. First half exploration: Enumerate all “bulb states” achievable by combinations of the first half switches, along with “the minimum number of switches to achieve each state,” and record them in a dictionary.
2. Second half exploration: Similarly, enumerate all “bulb states” and “minimum switch counts” for combinations of the second half switches, recording them in a dictionary.
3. Merge (combination): When combining a first-half state \(s_1\) (with switch count \(w_1\)) and a second-half state \(s_2\) (with switch count \(w_2\)), the final bulb state is \(s_1 \oplus s_2\) (\(\oplus\) denotes XOR, exclusive or). Among all combined states where the number of lit bulbs (number of set bits) is exactly \(K\), we find the one that minimizes \(w_1 + w_2\).

---

Algorithm

1. Bit Representation of Bulb States

We represent the state of \(N\) bulbs as an \(N\)-bit integer. - Bulb \(i\) is lit \(\leftrightarrow\) the \(i\)-th bit from the bottom is 1 - Bulb \(i\) is off \(\leftrightarrow\) the \(i\)-th bit from the bottom is 0

The initial state is all bulbs off, so it is the integer 0. We precompute the information about which bulbs each switch affects as a bitmask. The operation of pressing a switch corresponds to an XOR (exclusive or) operation between the current state and the switch’s mask.

2. DP (Full Enumeration) for First and Second Halves

For the first \(M_1\) switches, we add switches one by one, updating all achievable states and the minimum weight (number of switches pressed). The same process is performed for the second \(M_2\) switches.

3. Merge with Sorting and Pruning

We sort the results stored in dp1 (first half) and dp2 (second half) in ascending order of “number of switches (weight).”

When taking elements \((s_1, w_1)\) and \((s_2, w_2)\) from the two lists to combine them, we apply the following powerful pruning (early termination): - When a tentative minimum ans has already been found, if \(w_1 + w_2 \geq \text{ans}\), we cannot improve the minimum by exploring further, so we break out of the inner loop or the outer loop to skip.

This allows the merge process, which has a worst-case complexity of \(O(2^{M_1} \times 2^{M_2}) = O(2^M)\), to terminate extremely quickly on average.

---

Complexity

• Time complexity: \(O(2^{M_1} + 2^{M_2} + \text{time for merge})\) The full enumeration of the first and second halves finishes in \(2^{11} + 2^{12} = 6144\) loop iterations, which is instantaneous. The merge process has a worst case of \(2^{23}\) loop iterations, but by sorting in ascending order of weight and applying pruning, the actual number of iterations explored becomes very small (even in worst cases, it runs in tens to hundreds of milliseconds in Python).
• Space complexity: \(O(2^{M/2})\) The dictionary size for storing first-half and second-half states is at most \(2^{12} = 4096\), consuming almost no memory.

---

Implementation Details

Fast Popcount (Counting Set Bits)

We need to count the number of set bits in the XOR-combined value xor_val = s1 ^ s2. Python’s bin(x).count('1') is convenient but becomes a bottleneck when called many times inside a loop.

In this code, we precompute the bit counts for all 12-bit numbers (from \(0\) to \(4095\)) in an array pc. Since \(N \leq 23\), the popcount of a 23-bit number can be computed in constant time \(O(1)\) by splitting it into the lower 12 bits and the upper 11 bits and looking up the table:

ones = pc[xor_val & 0xfff] + pc[xor_val >> 12]

Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    switches = []
    idx = 3
    for _ in range(M):
        c = int(data[idx])
        mask = 0
        for j in range(c):
            mask |= 1 << (int(data[idx + 1 + j]) - 1)
        switches.append(mask)
        idx += 1 + c
        
    M1 = M // 2
    M2 = M - M1
    
    dp1 = {0: 0}
    for j in range(M1):
        sw = switches[j]
        next_dp = dp1.copy()
        for state, w in dp1.items():
            ns = state ^ sw
            nw = w + 1
            if ns not in next_dp or nw < next_dp[ns]:
                next_dp[ns] = nw
        dp1 = next_dp

    dp2 = {0: 0}
    for j in range(M1, M):
        sw = switches[j]
        next_dp = dp2.copy()
        for state, w in dp2.items():
            ns = state ^ sw
            nw = w + 1
            if ns not in next_dp or nw < next_dp[ns]:
                next_dp[ns] = nw
        dp2 = next_dp

    pc = [0] * 4096
    for i in range(4096):
        pc[i] = pc[i >> 1] + (i & 1)

    list1 = sorted(dp1.items(), key=lambda x: x[1])
    list2 = sorted(dp2.items(), key=lambda x: x[1])

    ans = 1000
    for s1, w1 in list1:
        if w1 >= ans:
            break
        for s2, w2 in list2:
            if w1 + w2 >= ans:
                break
            xor_val = s1 ^ s2
            ones = pc[xor_val & 0xfff] + pc[xor_val >> 12]
            if ones == K:
                ans = w1 + w2
                
    if ans == 1000:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    solve()

---

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