Overview

There are \(N\) light bulbs and \(M\) switches. Pressing each switch toggles the ON/OFF state of the corresponding light bulbs. The problem asks for the minimum number of switches that need to be pressed so that exactly \(K\) light bulbs are lit at the end.

Analysis

1. State Representation and Transitions

The ON/OFF state of light bulbs can be represented using bits (0 for off, 1 for on). The set of light bulbs affected by each switch can similarly be represented as a bitmask (indicating which bits are set).

The operation of pressing a switch (toggling the state) on a given light bulb state corresponds to the bitwise exclusive OR (XOR, ^) operation. For example, if the bit string representing the current state of the light bulbs is current_mask and the bitmask of the switch being pressed is mask[idx], then the state after pressing the switch is expressed as current_mask ^ mask[idx].

2. Feasibility of Exhaustive Search

The number of switches \(M\) is at most \(23\). Since each switch has 2 choices — “press” or “don’t press” — there are \(2^M\) total combinations. When \(M = 23\), \(2^{23} \approx 8.4 \times 10^6\) (approximately 8.4 million) combinations exist. This is sufficiently small relative to the typical execution time limit (usually 2 seconds), so we can afford to exhaustively search all combinations.

3. Optimization (Pruning)

To further reduce execution time and search more efficiently, we combine depth-first search (DFS) with pruning. Specifically, we apply the following techniques:

• Pruning by tentative minimum value: During the search, if the number of switches already pressed is greater than or equal to the “best answer (minimum value) found so far,” then continuing the search cannot improve the optimal solution. Therefore, we cut off the search at that point.
• Prioritizing the “don’t press” choice: By exploring the case of not pressing a switch first, we can explore states with fewer switches pressed at an earlier stage. This allows the tentative minimum value to be updated to a small value quickly, making the above pruning more effective.

---

Algorithm

1. Converting input to bitmasks: The information about which light bulbs each switch affects is converted to 0-indexed and stored as a bitmask (integer value).
2. Exhaustive search using DFS: We define a recursive function dfs(idx, current_mask, switch_count) that examines switches in order from the \(0\)-th to the \((M-1)\)-th.
   • Base cases:
     • If switch_count is greater than or equal to the current tentative minimum ans, cut off the search (pruning).
     • When all switch choices have been made (idx == M), if the number of set bits in the current state current_mask (the number of lit bulbs) equals \(K\), update ans with switch_count.
   • Transitions:
     • Don’t press the current switch: dfs(idx + 1, current_mask, switch_count)
     • Press the current switch: dfs(idx + 1, current_mask ^ mask[idx], switch_count + 1)
3. Output the answer: After the search is complete, if ans remains at its initial value, output -1 indicating it is impossible; otherwise, output ans.

---

Complexity

• Time complexity: Worst case \(O(2^M)\) Even in the worst case, the number of states is \(2^{23} \approx 8.4 \times 10^6\), and the transition at each state is performed with \(O(1)\) bitwise operations, so it easily fits within the execution time limit. Moreover, due to pruning, the actual number of search nodes explored is significantly smaller than this.
• Space complexity: \(O(M)\) The maximum depth of recursive calls is \(M\), so the memory consumed by the system stack is minimal.

---

Implementation Notes

• Using std::popcount: By using std::popcount (introduced in C++20) or __builtin_popcount, we can count the number of set bits in an integer (the number of lit bulbs) in \(O(1)\).

• Converting from 1-indexed to 0-indexed: The light bulb numbers in the input range from \(1\) to \(N\), but since we use the bit shift operation (1U << s), we decrement the bulb numbers to range from \(0\) to \(N-1\) for processing.

  Source Code

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

using namespace std;

int N, M, K;
vector<unsigned int> mask;
int ans = 1e9;

void dfs(int idx, unsigned int current_mask, int switch_count) {
    if (switch_count >= ans) return;
    if (idx == M) {
        if (std::popcount(current_mask) == K) {
            ans = min(ans, switch_count);
        }
        return;
    }
    // スイッチを押さない場合を先に探索（押す個数が少ない方を優先して枝刈りを効かせる）
    dfs(idx + 1, current_mask, switch_count);
    // スイッチを押す場合
    dfs(idx + 1, current_mask ^ mask[idx], switch_count + 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> M >> K)) return 0;

    mask.resize(M, 0);
    for (int i = 0; i < M; ++i) {
        int c;
        cin >> c;
        for (int j = 0; j < c; ++j) {
            int s;
            cin >> s;
            --s;
            mask[i] |= (1U << s);
        }
    }

    dfs(0, 0, 0);

    if (ans > M) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

---

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