Official

A - Three Cells per Row and Column Editorial by evima


It is easy when \(N\) is a multiple of \(3\): we can just put a horizontal block of three squares in each row, as follows.

###......
...###...
......###
###......
...###...
......###
###......
...###...
......###

If we try to do the same when \(N\) is not a multiple of \(3\), there will be some rows where the black block is split to left and right.

###.......
...###....
......###.
##.......#
..###.....
.....###..
#.......##
.###......
....###...
.......###

The above shows the case \(N=10\). The block is split in the \(4\)-th and \(7\)-th rows, making the number of connected components \(N+2\). We can fix this to \(N\) by swapping the \(1\)-st and \(3\)-rd rows and the \(8\)-th and \(10\)-th rows to join the two connected components in these rows.

...###....
......###.
###.......
##.......#
..###.....
.....###..
#.......##
.......###
.###......
....###...

This construction is also applicable for a general \(N\), by swapping the \(1\)-st and \(\lfloor N/3 \rfloor\)-th rows and \((N-\lfloor N/3 \rfloor +1)\)-th and \(N\)-th rows.

posted:
last update: