5
$\begingroup$

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) enter image description here

Basically, based on the image,

  1. To get to 1xN state, we can take 1 time, 1x3 and so dpHeight1[n] = dpHeight1[n-3]
  2. 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]
  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.

$\endgroup$
  • 1
    $\begingroup$ dpHeight3[n] += (dpHeight1[n-3] * dpHeight2[n-2] * 2) This is wrong. There are more arrangement. $\endgroup$ – John L. Apr 10 at 2:20
  • $\begingroup$ @JohnL. thanks, do you think the whole intuition is wrong or just some arrangements missing that if taken into consideration with the same approach should work? $\endgroup$ – Amir Rezvani Apr 10 at 2:33
  • 1
    $\begingroup$ @AmirRezvani I would say you were closer before your edits, but since I could not figure it out too I am not sure.. $\endgroup$ – Logan Wlv Apr 10 at 7:24
4
$\begingroup$

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]$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for the detailed explanation, I had serious issues detecting type 1 and type 2. Just for my reference when your did your analysis, where did you start? I mean did you start subtracting each shape (1x3, 3x1, 2x2) from a 3xn region (top down approach)? I tried that and could only find out an L shape (by taking 1x3 at top and 2x2 at bottom, same as 2x2 at top and 1x3 at bottom) thanks $\endgroup$ – Amir Rezvani Apr 10 at 23:55
  • 1
    $\begingroup$ For all types, try covering the rightmost spaces. For type I, try covering "the rightmost 4 1x1 squares.". A 1x3 has to be used to cover the top right 1x1 square. Then there are two ways to cover the rightmost two 1x1 squares that are not covered yet. $\endgroup$ – John L. Apr 11 at 0:14
  • 1
    $\begingroup$ I just improved this answer a lot. It should be much clearer now. $\endgroup$ – John L. Apr 11 at 13:19
  • 2
    $\begingroup$ If "try covering the rightmost spaces" also seems a bit daunting, first focus on the various ways in which you can fill one particular cell - say the top-right most cell. And that will usually force some other cells in the rightmost columns to be filled in some particular way. If not, you'll have to do another round of case work using a different cell now. $\endgroup$ – CodeChef Apr 12 at 2:24
  • $\begingroup$ $W[m]\sim0.3878\cdot1.64528386\cdot^m$. $\endgroup$ – John L. May 26 at 1:14
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Awesome! Thanks Sir! I'm having issues with coming up with dp intuitions! $\endgroup$ – Amir Rezvani Apr 2 at 0:56
  • 1
    $\begingroup$ get a single recurrence relation for 𝐴0(𝑛) in terms of 𝐴0(𝑚) for 𝑚<𝑛 how is that possible ? You always have one that refer to itself ? $\endgroup$ – Logan Wlv Apr 10 at 7:35
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Awesome!. Thanks for the clarification, I wish I could come up with intuitions myself... $\endgroup$ – Amir Rezvani Apr 2 at 22:39
0
$\begingroup$

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)

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I added my second approach which failed again! $\endgroup$ – Amir Rezvani Apr 10 at 2:12
  • $\begingroup$ I suggest editing your answer to include a self-contained definition of your notation. I notice you are using different notation than in my post, so I'm not sure how to interpret it. It might be more appropriate to ask a new question about your approach. Before doing that, I suggest you find the smallest $n$ for which your approach gives the wrong answer, and show the correct count and a list of all solutions, show the count given by your formula, and compare the list of all solutions to your case analysis you used to come up with your formula. $\endgroup$ – D.W. Apr 10 at 20:34
  • $\begingroup$ solution is available now @ CodeChef if that helps: codechef.com/INOIPRAC/problems/INOI2002 . This was by far the most annoying recursion formula that I could not find recursion relation for!!! $\endgroup$ – Amir Rezvani Apr 10 at 22:14
  • $\begingroup$ @AmirRezvani Well even with the solution I don't understand my mistake, I want to understand ! D.W. I will try that thank you $\endgroup$ – Logan Wlv Apr 11 at 9:54
  • 1
    $\begingroup$ I think I understood ! Basically in my pic I was misscomputing the spaces. 2 * g(n - 3) -> 2 * g(n - 2) logic and so on. I was taking account the edge and that was wrong $\endgroup$ – Logan Wlv Apr 11 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.