Official

E - Tile Grid with One Hole Editorial by evima


From the constraints, we may assume that neither \(H\) nor \(W\) is a multiple of \(L\).
Suppose there exists a tiling method satisfying the conditions.
First, consider the case \(3 \leq L\). We write \(h\bmod L\) on the cells in row \(h\). Let \(C_i\) be the number of cells covered by tiles that have \(i\) written on them. Since \(C_0,C_1,\dots,C_{L-1}\) are all equal modulo \(L\), we see that \(H\equiv 1,L-1 \pmod L\). Similarly, we also see that \(W\equiv 1,L-1 \pmod L\). From \(H \times W=L \times (N+M)+1\), the following two cases are possible:
\(H \equiv 1 \pmod L\) and \(W \equiv 1 \pmod L\) and \(r \equiv 1 \pmod L\) and \(c \equiv 1 \pmod L\)
\(H \equiv L-1 \pmod L\) and \(W \equiv L-1 \pmod L\) and \(r \equiv 0 \pmod L\) and \(c \equiv 0 \pmod L\)
Also, when \(L=2\), it can be shown that one of these cases applies.

Case ①

When \(w \neq c\), since at least one cell in column \(w\) is included in a horizontal tile, we see that \(\frac{W-1}{L}\leq N\). Similarly, we see that \(\frac{H-1}{L}\leq M\). If we write \(h\bmod L\) on the cells in row \(h\), each vertical tile contains each of \(0,1,\dots,L-1\) once, so we see that \(N \equiv \frac{W-1}{L} \pmod L\).
When these conditions are satisfied, there exists a tiling method satisfying the conditions.
We tile the cells in row \(r\) other than \((r,c)\) with horizontal tiles, and the cells in column \(c\) other than \((r,c)\) with vertical tiles. The remaining part can be divided into \(L\times L\) grids. These can be tiled with either \(L\) horizontal tiles or \(L\) vertical tiles, and we can adjust so that there are exactly \(N\) horizontal tiles.

Case ②

When \(w \neq c\), at least \(L-1\) cells in column \(w\) are included in horizontal tiles. Also, among \((1,c),(2,c),\dots,(r-1,c)\) and \((r+1,c),(r+2,c),\dots,(H,c)\), at least \(L-1\) cells each are included in horizontal tiles. From this, we see that \(\frac{(W+1)(L-1)}{L}\leq N\). Similarly, we see that \(\frac{(H+1)(L-1)}{L}\leq M\). If we write \(h\bmod L\) on the cells in row \(h\), each vertical tile contains each of \(0,1,\dots,L-1\) once, so we see that \(N \equiv \frac{(W+1)(L-1)}{L} \pmod L\).
When these conditions are satisfied, there exists a tiling method satisfying the conditions.
We can tile the square region consisting of rows \(r-L+1\) to \(r+L-1\) and columns \(c-L+1\) to \(c+L-1\) by arranging \(2(L-1)\) vertical tiles and horizontal tiles each in a pinwheel pattern. We tile \(L-1\) columns of the upper and lower parts of this square with vertical tiles, and \(L-1\) rows of the right and left parts with horizontal tiles. By appropriately choosing the positions of \(L-1\) rows and \(L-1\) columns, we can divide the remaining part into \(L \times L\) grids and adjust them similarly to case ①.

posted:
last update: