3xN tiling problem with blocks of size 3x1 or 2x2
https://cs.stackexchange.com/questions/123463
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I know there are a number of different tiling problems and some of them have been discussed here: Number of ways of tiling a 3*N board with 2*1 dominoes problem Domino and Tromino Combined Tiling DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?. My domain has different requirements which are as below: https://www.codingame.com/ide/puzzle/3n-tiling
Height will be 3, tile sizes are: 2x2, 3x1, 1x3
there are possible choices for 3x6:
┌─────┬─────┐ ┌───┬───┬───┐ ┌─────┬─────┐ ┌─┬─┬─────┬─┐
├─────┼─────┤ │ │ │ │ ├───┬─┴─┬───┤ │ │ ├─────┤ │
├─────┼─────┤ ├───┴─┬─┴───┤ │ │ │ │ │ │ ├─────┤ │
└─────┴─────┘ └─────┴─────┘ └───┴───┴───┘ └─┴─┴─────┴─┘
┌─┬─────┬─┬─┐ ┌─┬─┬─┬─────┐ ┌─────┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┐
│ ├─────┤ │ │ │ │ │ ├─────┤ ├─────┤ │ │ │ │ │ │ │ │ │ │
│ ├─────┤ │ │ │ │ │ ├─────┤ ├─────┤ │ │ │ │ │ │ │ │ │ │
└─┴─────┴─┴─┘ └─┴─┴─┴─────┘ └─────┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┘
(illustration copied from Codingame problem section).
I have come up with the following DP relation:
dp[i] = (dp[i-1] + (i >= 3 ? dp[i-3] : 0) + (i >= 6 ? dp[i-6] * 2 : 0))
dp[i-1] means at each state, you can add a 1x3 (illustration below) to previous state to get to the current state.
┌─┐
│ │
│ │
└─┘
dp[i-3] means if your width is at least 3, you can stack up three 3x1 vertically to 3 states ago (width - 3) to get to current state.
┌─────┐
├─────┤
├─────┤
└─────┘
dp[i-6] means when my width is greater than or equal to 6, I can add three 2x2 squares horizontally next to each other, then put two 3x1 rectangles on top of them to 6 states ago(width - 6), in two ways, to get to current state).
┌───┬───┬───┐ ┌─────┬─────┐
│ │ │ │ ├───┬─┴─┬───┤
├───┴─┬─┴───┤ │ │ │ │
└─────┴─────┘ └───┴───┴───┘
But looks like I'm missing something, my solution for 3x12 returns 124, while it should be 154. Any help is appreciated.
Edit:
After a lot of thoughts and getting some ideas from answers, I came up with this solutions (Image represents a top down DP approach)
Basically, based on the image,
- To get to 1xN state, we can take 1 time, 1x3 and so dpHeight1[n] = dpHeight1[n-3]
- To get to 2xN state, we can either take 1 time 2x2 so dpHeight2[n] = dpHeight2[n-2] or we can take 2 times 1x3: dpHeight2[n] += dpHeight2[n-3]
- to get to 3xN, we can either take 1 time 3x1, so dpHeight3[n] = dpHeight3[n-1] or we can take 3 time 1x3, dpHeight3[n] += dpHeight3[n-3] or take 1 time 2x2 and 1 time 1x3, exception here is we can take 1x3 first or after we take 2x2, but they both have same count, so: dpHeight3[n] += (dpHeight1[n-3] * dpHeight2[n-2] * 2)
And this the code:
dpHeight1[0] = 1//height = 1
dpHeight2[0] = 1//height = 2
dpHeight3[0] = 1//height = 3
for (int width=1; width <= n; width++) {
//take out one 1x3
dpHeight3[width] = (dpHeight3[width-1])%mod
if width >= 2 {
dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-2])%mod
}
if width >= 3 {
//put 1 time 3x1
dpHeight1[width] = (dpHeight1[width] + dpHeight1[width-3])%mod
//put 2 vertically stacked 3x1
dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-3])%mod
//take out 3 vertically stacked times 3x1
dpHeight3[width] = (dpHeight3[width] + dpHeight3[width-3])%mod
//take out 1 time 2x2 and put it on top of 1 time 3x1
// or take out 1 time 3x1 and put it on top of 1 time 2x2
dpHeight3[width] = (dpHeight3[width] + 2 * (dpHeight2[width-2] * dpHeight1[width-3]))%mod
}
}
But still not getting the result.
Solution
This counting problem is one of the classical problems that can be solved efficiently by dynamic programming.
Since we should find the number of ways to fill a 3 by $n$ rectangle, a natural set of subproblems is the number of ways to fill a 3 by $m$ rectangle, where $m\le n$. However, it turns out it is practically impossible to find a recurrence relation with finite terms between them. The difficulty comes from the following configuration. And configurations that contain that kind of configurations.
┌───┬───┬─────┬─────┬─────┬ - - - - - - - - ─┬─────┬─────┬─────┬───┐
│ │ ├─────┼─────┼─────┼ - - - - - - - - ─┼─────┼─────┼─────┤ │
├───┴─┬─┴───┬─┴───┬─┴───┬─┴ - - - - - - - ─┬─┴───┬─┴───┬─┴───┬─┴───┤
└─────┴─────┴─────┴─────┴ - - - - - - - - ─┴─────┴─────┴─────┴─────┘
So, we have to select more subproblems. Here is one way to choose them.
- Let $W_0[m]$ be the number of ways to cover the shape shown below, a 3 by $m$ rectangle. Our ultimate goal is $W_0[m]$.
┌──────────┐
│ │
3 │ │
└──────────┘
m
- Let $W_1[m]$ be the number of ways to cover the first shape shown below, a 3 by $m$ rectangle with an extra 1x1 square at the top-right corner. By symmetry, $W_1[m]$ is also the number of ways to cover the second shape shown below.
m+1 m
┌────────────┐ ┌──────────┐
│ ┌─┘ 1 │ │
3 │ │ 3 │ └─┐
└──────────┘ └────────────┘ 1
m m+1
- Let $W_2[m]$ be the number of ways to cover the first shape shown below, a 3 by $m$ rectangle with an extra 1x2 square at the top-right corner. By symmetry, $W_2[m]$ is also the number of ways to cover the second shape shown below.
m+1 m
┌────────────┐ ┌──────────┐
│ │ 2 │ └─┐
3 │ ┌─┘ 3 │ │ 2
└──────────┘ └────────────┘
m m+1
How to find the recurrence relations?
We will try to cover the space at the rightmost boundary of the above shapes in all possible ways, always making sure that what is left to cover is still one of the above shapes.
Consider $W_0[m]$. We have the following 4 ways to cover the rightmost space.
┌────────┬─┐ ┌────┬─────┐ ┌──────┬───┐ ┌────┬─────┐
│ │ │ │ ├─────┤ │ │ │ │ └─┬───┤
│ │ │ │ ├─────┤ │ ┌─┴───┤ │ │ │
└────────┴─┘ └────┴─────┘ └────┴─────┘ └──────┴───┘
What is left: 3x(m-1) 3x(m-3) 3x(m-3)+2 3x(m-3)+2
So, we have $\quad\quad W_0[m] = W_0[m - 1] + W_0[m - 3] + W_2[m - 3] * 2. $
Consider $W_1[m]$. We have the following 2 ways to cover the rightmost space of the first shape.
┌──────┬─────┐ ┌──────┬─────┐
│ ├───┬─┘ │ ┌─┴───┬─┘
│ │ │ │ ├─────┤
└──────┴───┘ └────┴─────┘
What is left: 3x(m-2) 3x(m-3)+1
So we have $\quad\quad W_1[m] = W_0[m - 2] + W_1[m - 3].$
Consider $W_2[m]$. We have the following 2 ways to cover the rightmost space of the first shape.
┌────────┬───┐ ┌──────┬─────┐
│ │ │ │ ├─────┤
│ └─┬─┘ │ ┌─┴───┬─┘
└──────────┘ └────┴─────┘
What is left: 3x(m-1)+1 3x(m-3)+2
So we have $\quad\quad W_2[m] = W_1[m - 1] + W_2[m - 3]. $
Using the above three recurrence equations, now we can compute all $W_0[i],W_1[i],W_2[i]$, in order of increasing $i$, starting from $i=3$, given the following initial conditions, $$ \begin{aligned} W_0[0] &= W_0[1] = W_0[2] = 1,\\ W_1[0] &= W_1[1] = 0\quad \text{ and }\quad W_1[2] = 1,\\ W_2[0] &= W_2[1] = W_2[2] = 0. \end{aligned}$$
Here are the first 20 values for $W_0(\cdot)$.
m: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
W_0: 1 1 2 3 4 8 13 19 35 58 89 154 256 405 681 1131 1822 3025 5012 8156
The above approach is fast enough for both the problem at codechef and the same problem at codingame.
However, if $n$ is very large, such as $10^{15}$, it may take days to compute. We will need to introduce the power of matrix or generating function. Those techniques can speed up the computation exponentially.
For more information about this sequence, check the On-Line Encyclopedia of Integer Sequences.
There is, in fact, a recurrence relation that involves only $W[m]$, the number of ways to fill a 3 by $n$ rectangle. (It was denoted $W_0[m]$ in the above paragraphs.) For all $m\ge9$,
$$W[m] = W[m-1] + 3W[m-3] - 2W[m-4] - W[m-6] + W[m-7] + W[m-9]$$
OTHER TIPS
Here is a systematic way to approach it. I suggest you define three values:
$A_0(n)$ is the number of ways to tile a $3 \times n$ region.
$A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.
$A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of it already covered.
Then you should be able to express each $A_i(n)$ in terms of $A_j(m)$ for $m < n$. This gives you a mutual recurrence relation for these three values. It is easy to construct these recurrent relations based on a case analysis of how the leftmost column is covered.
You can then compute these using dynamic programming, in order of increasing $m$. Or, you can substitute into each other and get a single recurrence relation for $A_0(n)$ in terms of $A_0(m)$ for $m<n$, if you prefer.
Regarding your solution:
Yeah, you're missing something. For instance, a solution could start
┌───┬───┬─────┐
│ │ ├─────┤
├───┴─┬─┴───┬─┴
└─────┴─────┴──
and continue from there; that won't be counted in your case analysis.
In general, you would change the question slightly: "How many ways are there to tile an X by N area by adding tiles individually and always adding the next tile so that it covers the topmost of the leftmost uncovered squares". Obviously that doesn't change the number of possible tilings at all since each square must eventually be covered.
Since you are tiling the area from the left to the right, you then analyse what the boundary between the tiled area and the untiled area could look like (or what the rectangle containing all the untiled squares could look like).
In your example, you start with a complete rectangle. You can then add 1x3 vertically, 1x3 horizontally at the top, or 2x2 at the top. 1x3 vertically gives the same shape. After 1x3 horizontally, you can add 1x3 horizontally in the middle row and are then forced to add 1x3 horizontally at the bottom, giving a complete square again. Or you can add 2x2 at the bottom, leaving the top left square covered. And so on. You can do that systematically.
And then as D.W. said, you get several mutually recursive formulas. Depending on the number X and the number of available shapes, this will be more or less complicated.
I spent a night on this problem and still can not get the right answer, I feel like I am missing something.
I tried to follow D.W. reasoning and ended up with those relations :
$A0(n) = A0(n - 1) + A0(n - 3) + 2×A2(n - 3)$
$A2(n) = A2(n - 3) + A3(n - 3)$
$A3(n) = A0(n) + A3(n -3)$
Am I wrong in those relations ?
If it's correct I guess it's my way to compute it, but I am too uncertain about those relations right now...
Here a pic to show you my thoughts process (f() would be A0 and g() would be A2 and h() would be A3)
