Overview

Among all combinations of “press/don’t press” for each switch, we search for those where the number of lit bulbs ends up being exactly \(K\), and find the minimum number of switches pressed.

Analysis

• Each bulb’s state is a binary value of “on/off”, so the overall state of all bulbs can be represented as a bit set (bitmask).
  For example, if \(N=5\), we use the lower 5 bits of an integer, where bit 1 means on and 0 means off.
• A switch operation “toggles the specified bulbs”, which corresponds to XOR (exclusive or) in bit operations.
  That is, if we represent the effect of switch \(j\) as a bitmask \(mask[j]\), then pressing that switch is:
  \(state \leftarrow state \oplus mask[j]\)
• The constraint is \(M \le 23\), so there are \(2^M \le 2^{23}\approx 8.4\) million possible ways to press switches.
  This is a size where brute-force search is barely feasible.
• However, if we naively
  • compute the “XOR of all pressed switches” from scratch for each subset
    it takes \(O(M)\) per subset, resulting in \(O(M2^M)\) overall, which tends to be too slow in Python.
• Therefore, in this solution we enumerate subsets in Gray code order.
  In Gray code, adjacent sets differ by exactly 1 bit (one switch), so:
  • We can update \(state\) by reflecting only the single changed switch
  • The number of pressed switches can be updated by \(+1/-1\)
    This makes the processing for each subset \(O(1)\).

Algorithm

1. For each switch \(j\), create a bitmask \(mask[j]\) of the bulbs it affects.
2. Initialize the current bulb state \(state\) (bitmask) to 0 (all off), and set \(pressed=0\).
3. Enumerate all subsets in Gray code order.
   • For \(i=0,1,2,\dots,2^M-1\), the Gray code is \(g = i \oplus (i \gg 1)\)
   • Let \(prev\) be the previous Gray code; the changed bit is \(diff = g \oplus prev\)
   • The lowest set bit of \(diff\) is the “toggled switch”, so find its index
4. Let the toggled switch be \(idx\):
   • \(state \leftarrow state \oplus mask[idx]\) (update bulb state)
   • If bit \(idx\) of the Gray code became 1, the switch was pressed so \(pressed += 1\); if it became 0, then \(pressed -= 1\)
5. If the number of set bits in \(state\) (bit_count()) equals \(K\), update the answer candidate with the minimum of \(pressed\).
6. If no update was made by the end, output -1; otherwise output the minimum value.

Complexity

• Time complexity: \(O(2^M + \sum_{j=1}^{M} c_j)\)
  (Gray code enumeration updates each state in \(O(1)\))
• Space complexity: \(O(M)\)
  (mask array for each switch)

Implementation Notes

• Since \(N \le 23\), the bitmask can be managed with a single Python integer.

• Using int.bit_count() efficiently computes the “number of lit bulbs (number of 1-bits)”.

• To find the toggled bit position from the Gray code difference diff:

  • lsb = diff & -diff (lowest set bit)
  • idx = lsb.bit_length() - 1 This is concise.

• Since the input can be large, reading all at once with sys.stdin.buffer.read() ensures stability.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    masks = [0] * M
    for j in range(M):
        c = next(it)
        m = 0
        for _ in range(c):
            s = next(it) - 1
            m |= 1 << s
        masks[j] = m

    total = 1 << M
    state = 0
    pressed = 0
    ans = 10**9

    if state.bit_count() == K:
        ans = 0

    prev_gray = 0
    for i in range(1, total):
        gray = i ^ (i >> 1)
        diff = gray ^ prev_gray
        lsb = diff & -diff
        idx = lsb.bit_length() - 1

        state ^= masks[idx]
        if (gray >> idx) & 1:
            pressed += 1
        else:
            pressed -= 1

        if state.bit_count() == K and pressed < ans:
            ans = pressed

        prev_gray = gray

    print(ans if ans != 10**9 else -1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.