A floor with a pillar
The floor of a hall is a square of 2k × 2k cells, and a column stands in one cell. There is only one kind of tile, an L-shape of three cells, that is, a 2 × 2 square without one cell; the L-shapes may be rotated. Tile the whole floor except the column, without cutting, gaps or overlaps.
The floor has 4k − 1 cells without the column, and this number is always divisible by three. But does that mean the floor can be tiled wherever the column stands?
Input
One line: k, r, c (1 ≤ k ≤ 8, 1 ≤ r, c ≤ 2k), the size of the floor and the row and column of the column; cells are numbered from one.
Output
2k lines of 2k integers: 0 in place of the column, and in the other cells the number of the tile covering it. The numbers can be any positive numbers; each number must stand in exactly three cells forming an L-shape. If there are several tilings, print any.
Examples
Example 1
2 2 3
2 2 3 3 2 1 0 3 4 1 1 5 4 4 5 5
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Try tiling a 4 × 4 floor by hand for different places of the column. Laying tiles row by row from left to right sometimes leads into a corner where an L-shape no longer fits. A method that does not depend on luck is needed.
2Hint 2
Cut the floor into four quarters of 2k−1 × 2k−1. The column stands in one of them, and for that quarter the problem is the same, only half the size. How do you make the other three quarters, which have no column, into the same problem?
3The idea
Put one L-shape at the very centre of the floor so that it takes one cell in each of the three quarters without the column. Then each of the four quarters has exactly one occupied cell, the column or a piece of the central L-shape, and each quarter becomes the same problem of smaller size. A 2 × 2 floor with one occupied cell is exactly one L-shape.
4Walkthrough
A recursive function receives a square (its top left corner and side) and the occupied cell in it. If the side is 1, there is nothing to do. Otherwise find the quarter with the occupied cell; for each of the other three take its cell adjacent to the centre of the big square, the cells (h − 1, h − 1), (h − 1, h), (h, h − 1), (h, h) relative to the corner, where h is half the side, and put one new L-shape on three of them. They really do form an L-shape: all four cells lie in the central 2 × 2 square, and we take three. Then call the function for each quarter with its occupied cell.
This is also a proof: by induction on k, a 2k × 2k floor with one cell removed can be tiled with L-shapes wherever that cell is. This is how Solomon Golomb proved it in 1954, in the paper that started the theory of polyominoes.
4+Solution
5Complexity
T(n) = 4T(n/4) + O(1), where n = 4k is the number of cells: by the master theorem Θ(n), one L-shape per call, and there are (n − 1)/3 calls. The recursion depth is k ≤ 8. Most of the time goes into printing 65,536 numbers.
6Common mistakes
- Greedy tiling by rows. It puts the first fitting L-shape into the first free cell and already on an 8 × 8 floor leaves cells where no L-shape fits (the fourth test).
- The central L-shape facing the wrong way. It must cover the three quarters without the column; if by mistake it covers the quarter with the column, that quarter has two occupied cells and another has none.
- The same “occupied cell” for all quarters. Each quarter needs its own: the column for its own quarter and its own piece of the central L-shape for the others.