Minesweeper

Research note. I checked the official statement and the official Kotlin Heroes 14 editorial. The tutorial prose for C is not loaded there, but the author solution uses exactly the $3$/$5$ block construction below. The supplied statement is still the source of truth.

Call an empty cell active if it is adjacent to a mine. Since every empty cell may be adjacent to at most one mine, every active cell can be charged to its unique neighboring mine.

The key geometry rule is brutal: in a positive answer, no two mines can be in columns whose indices differ by at most $2$.

Why? If a cell touches two mines, it cannot be empty, so it is forced to be a mine. A vertical pair of mines forces both cells in adjacent columns to be mines, and this propagates until the whole board is mined. Mines in columns at distance $1$ or $2$ force a full mined column between or beside them, then the same propagation happens. A fully mined board contributes $k=0$, so for our $k \ge 1$ cases this is dead.

So every useful mine is isolated: one mine per mined column, and mined columns are spaced by at least $3$.

Now count what one isolated mine can do on a $2 \times n$ board:

• If it is strictly inside the board, it has $5$ neighboring cells, all empty and active.
• If it is on the left or right border, it has $3$ neighboring cells, all empty and active.
• If $n=1$, one mine has exactly $1$ neighboring empty cell.

For $n \ge 2$, every positive solution therefore has

$k = 5b + 3a,$

where $b$ is the number of interior mines and $a \in \{0,1,2\}$ is the number of border mines. This also kills the tempting but wrong idea that $9=3+3+3$ should work. There are only two borders. The third $3$-block has nowhere to live. Geometry says no; no loophole hiding under the couch.

For fixed $a,b$, the minimum number of columns is forced by spacing:

• $a=0$: put interior mines at columns $1,4,7,\dots$, so $n \ge 3b$.
• $a=1$: one border mine plus $b$ interior mines needs $n \ge 3b+2$.
• $a=2$: two border mines plus $b$ interior mines needs $n \ge 3b+4$.

These lower bounds are tight. Construct everything in the bottom row and make the whole top row empty:

• A left border $3$-block uses two columns: bottom pattern *..
• A $5$-block uses three columns: bottom pattern .*..
• A right border $3$-block uses two columns: bottom pattern .*.

All mines are exactly $3$ columns apart, so their affected empty cells do not overlap.

The residue cases are now immediate:

• $k=1$: one column works.
• $k \equiv 0 \pmod 5$: use only $5$-blocks.
• $k \equiv 3 \pmod 5$: use one border $3$-block, then $5$-blocks.
• $k \equiv 1 \pmod 5$ and $k>1$: use two border $3$-blocks, then $5$-blocks.
• $k \equiv 2$ or $4 \pmod 5$: impossible.

The algorithm prints exactly those blocks, so it also prints the minimum possible number of columns.

Complexity is $O(n)$ per test case, where $n$ is the number of printed columns. With $k \le 100$, this is tiny; output size dominates.