CF 1914G2 - Light Bulbs (Hard Version)

Rating: 2300
Tags: combinatorics, data structures, dfs and similar, dp, graphs, hashing
Solve time: 36s
Verified: no

Solution

Problem Understanding

We are given a row of $2n$ light bulbs, with each color from $1$ to $n$ appearing exactly twice. All bulbs start turned off. We are allowed to initially turn on any subset $S$ of bulbs. After that, we can apply two operations repeatedly: first, if a color has one bulb on and its pair off, we can turn the second on; second, if two bulbs of the same color are on with at least one bulb between them, we can turn on any bulb strictly between them. The goal is to find the smallest initial set $S$ that guarantees all bulbs can be lit and to count the number of such minimal sets modulo $998244353$.

The key constraints are that $n$ can reach $2 \cdot 10^5$ summed over all test cases, which rules out any naive approach that iterates over all subsets of bulbs. Operations must therefore run in roughly $O(n)$ per test case to fit the 3-second limit.

The tricky part is that turning on bulbs in one interval may unlock bulbs in another interval via the "between two bulbs of the same color" rule. Naive solutions that simply pick one bulb from each color can fail if intervals overlap. For example, consider 1 2 1 2. Picking both first bulbs, 1 and 2, initially works. Picking only the first 1 fails to light the second 2, because the second operation cannot be applied yet.

Edge cases include sequences where pairs are nested or interleaved. For instance, 1 2 3 1 2 3 requires at least two bulbs initially turned on. A careless approach might assume "pick any