PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: harsh_h
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
simple
PREREQUISITES:
None
PROBLEM:
Given N, count the number of ways of coloring an N\times N grid with the colors white and black, such that no two black cells share a side and the number of black cells is \left\lfloor \frac{N^2}{2} \right\rfloor.
EXPLANATION:
Let’s solve for even and odd N separately.
First, consider the case when N is even.
Here, N^2 is even, so \left\lfloor \frac{N^2}{2} \right\rfloor = \frac{N^2}{2} represents exactly half the cells on the board.
Along with the condition that no two black cells must be adjacent, there are in fact exactly two ways to color the N\times N grid: the chessboard coloring, and the inverse chessboard coloring (distinguished by whether the top-left cell is white or black).
Essentially, we’re forced to color alternate cells black here.
Proof
We’ll show that in an optimal solution, no two adjacent cells can be colored white.
Suppose (i, j) and (i, j+1) are both white.
Since N is even, the board can be broken up into 2\times 1 and 1\times 2 pieces as follows:
- For every column that’s not the j-th or (j+1)-th, use 2\times 1 pieces from top to bottom: you’ll need \frac{N}{2} pieces for each column.
- For the j-th and (j+1)-th column, use 1\times 2 pieces instead, again from top to bottom - so each piece will include one cell from column j and one from column j+1, for N pieces in total.
Now, note that under this scheme, (i, j) and (i, j+1) will form a single piece. Throw it out, since we don’t intend to color either of them black.
Each remaining piece now contains two adjacent cells, which means at most one cell in each piece can be colored black.
However, the number of remaining pieces is (N-2)\cdot \frac{N}{2} + N-1 = \frac{N^2 - 2N + 2N - 2}{2} = \frac{N^2-2}{2}, so by coloring one cell from each black, we obtain \frac{N^2-2}{2} black cells.This is less than the maximum possible, which is \frac{N^2}{2}.
So, if there are ever two adjacent white cells, the resulting coloring cannot be optimal in size if no two black cells are adjacent.
Note that this means once cell (1, 1) is given a color, everything else is decided uniquely.
(1, 1) can be either white or black, so we have two valid colorings.
Next, let’s look at odd N.
Now, \left\lfloor \frac{N^2}{2} \right\rfloor = \frac{N^2 - 1}{2}
Note that this is in fact less than the maximum number of cells we can color black, which is actually \frac{N^2 + 1}{2}, obtained by chessboard-coloring the grid with (1, 1) being black.
In particular, this gives us a way to obtain a coloring with \frac{N^2 - 1}{2} black squares: take the aforementioned chessboard coloring, and remove any one cell from it.
Alternately, we can also take the inverse chessboard coloring (where (1, 1) is white), which will give us exactly \frac{N^2 - 1}{2} cells.
This gives us \frac{N^2+1}{2} + 1 different colorings already.
As it turns out, this is all of them!
Proof
We’ll use a similar strategy to the even case with 1\times 2 and 2\times 1 pieces (a.k.a dominos), but a bit more involved.
Consider the standard chessboard coloring of an N\times N grid, with (1, 1) being colored black.
Since N is odd, as mentioned earlier, this will give us \frac{N^2 + 1}{2} black squares, which is more than we want.
So, in any valid coloring, at least one of them must be missing.
Note that these are the squares (1, 1), (1, 3), (1, 5), \ldots, (1, N), (2, 2), (2, 4), \ldots, (2, N-1), (3, 1), \ldotsLet (x, y) be the “first” one to be missing.
Here, “first” means that we choose the one with minimum x; and if there are multiple, choose the one with minimum y.Now, since this is a chessboard coloring, x+y must be even - so either x and y are both even, or they’re both odd.
We’ll look at the two cases separately.First, suppose x and y are both odd.
Then, do the following:
- The segment from 1 to y-1 in row x has even length; so break it into 2\times 1 pieces.
- The segment from y+1 to N in row x also has even length; so break it into 2\times 1 pieces.
- There are x-1 rows above row x, which is even. So, for each column, break these first x-1 rows into 1\times 2 dominos.
- Similarly, there’s an even number of rows after the x'th, so for each column, break those rows into 1\times 2 dominos.
We now have a domino tiling of the entire grid except (x, y).
Just as in the even case, each domino can have at most one black cell; and since there are \frac{N^2 - 1}{2} of them with us, we want them all to have one black cell.
If a black cell in any domino is fixed, that will uniquely propagate and define the black cells in all other dominos.This gives us two possible colorings for when (x, y) isn’t colored black.
You may note that these two colorings are exactly the chessboard coloring without (x, y), and the inverse chessboard coloring.
Next, let’s look at when x and y are both even.
Once again, the entire grid minus (x, y) can be tiled with dominos.
Specifically, do the following:
- (x-1, y-1) and (x, y-1) as one domino.
- (x+1, y-1) and (x+1, y) as one domino.
- (x+1, y+1) and (x, y+1) as one domino.
- (x-1, y+1) and (x-1, y) as one domino.
This essentially cuts out a 3\times 3 square around (x, y).
Then, for the remaining grid, it’s similar to the previous case: above row x-1 and below x+1 are an even number of rows so every column can be tiled vertically there; and to the left of column y-1 and to the right of y+1 are an even number of columns, so tile the three rows horizontally there.Again, you can see that with this tiling, coloring any one cell black will uniquely determine everything else; so again we obtain two options.
These options, as before, can be observed to be the chessboard coloring with (x, y) removed, and the inverse chessboard coloring.
The inverse chessboard coloring appeared in every (x, y)-removed coloring, but it needs to be counted only once since it’s, well, a single coloring.
That proves our claim of the mentioned colorings being the only ones possible.
In summary, when N is even the answer is 2, and when N is odd the answer is \frac{N^2 + 1}{2} + 1.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
if n%2 == 0: print(2)
else: print((n*n + 1)//2 + 1)