Virus Removal

Subtask 1: represent the infected set by a bitmask. For every choice of three distinct regions, clear those bits and apply the simultaneous midnight spread. Run BFS from the all-infected state to the empty state and reconstruct the path. Bit operations give $O(2^N N^3)$ time and $O(2^N)$ space. The construction below guarantees a path within $N$ days, so a shortest path found by BFS also meets the limit.

Full solution: choose $X=N-2$. At noon on day $k$, clean regions $1,k+1,k+2$ ().

If $N=3$, all regions are cleaned on the first day. Otherwise, after midnight on day $k$, for $1 \leq k \leq N-3$, the clean regions are exactly $[2,$. On day 1, cleaning leaves only region 2 clean after the two endpoints are reinfected. Inductively, adding to the previously clean interval makes clean at noon. At midnight only its two endpoints touch infected regions outside it, leaving clean.

On day $N-2$, clean the remaining regions $1,N-1,N$. No virus remains to spread. The three printed indices are distinct and in range, and $N-2 \leq N$.

The solution uses $O(N)$ time for output and $O(1)$ extra space, excluding output buffers. The checker directly simulates all days in $O(NX)$ time and $O(N)$ space. Since , at most region updates are needed per input file.

Solution written by GPT