Now that we have seen dynamic programming (and a simple tiling problem), it’s time for a more challenging one. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

Problem Statement

Like before, we are given a grid of size $n \times 2$ and we need to count the number of ways in which we can tile the grid such that the entire grid is covered and no tiles overlap. However, now we have two types of tiles available, (a) tiles of size $2 \times 1$ and (b) L-shaped tiles which cover three squares.

Note: Each type of tiles look identical to other tiles of the same type. Two ways of tiling are different based on which tiles are placed and in what orientation.

Since the answer can be very large, output the answer modulo 1000003 (That is, the remainder the answer leaves when divided by 1000003. ).

Example

There are 5 possible ways of tiling a $3 \times 2$ grid.

Tiling 1: 
Three vertical tiles
 __ __ __
|  |  |  |
|__|__|__|
Tiling 2: 
1 vertical tile, followed by 2 horizontal tiles
 __ _____ 
|  |_____|
|__|_____|
Tiling 3: 
2 horizontal tiles, followed by 1 vertical tile
 _____ __
|_____|  |
|_____|__|
Tiling 4: 
2 L-shaped tiles. 
 _____ __
|   __|  |
|__|_____|
Tiling 5: 
2 L-shaped tiles the other way. 
 __ _____
|  |__   |
|_____|__|

Note that it is legal to mix the two types of tiles. For example, the following are some examples of tiling a $4 \times 2$ grid.

 __ _____ __
|  |_____|  |
|_____|_____|
 __ _____ __
|  |__   |  |
|_____|__|__|

IO description

Input description: The first line contains the number of test cases T. The test case is on a separate line, a single number $n$ denoting the length of the grid.

Sample input:

4
2
3
4
10

Output description: Output should contain T lines. Each line should contain the answers for the respective test case, the number of ways of tiling modulo 1000003.

Sample output:

2
5
11
1255

Submitting your solution

Once you are confident of your solution, run your code on the following input. Then take the quiz!

10
3
10
23
60
269
832
1597
5189
25987
76401

Progressive ‘hint-by-hint’ solution

Only look at the hints if you can’t solve the problem for at-least 20-minutes. Read only one hint that you could not figure out on your own. Then spend at-least 20-minutes trying to solve the problem again.

Hint 1 (dynamic programming state):

The first step is to come up with the state. In addition to $f(n)$ = number of ways to tile $n \times 2$ grid, you’ll need to define other types of state. (for the simplest solution).

Hint 2:

The other states are: $g(n)$ = number of ways to tile $n \times 2$ grid plus the top square in the (n+1)th column, and $h(n)$ = number of ways to tile $n \times 2$ grid plus the bottom square in the (n+1)th column. Note that the definitions are symmetric, so it’s okay if you only defined one of them, since $g(n) = h(n)$.

Hint 3 (recursion):

The recursion involves $f(n)$ as a function of $f$ and $g$, as well as $g(n)$ as a function of $f$ and $g$.

Hint 4:

The recursion for $f(n)$ is $f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2)$. The four cases correspond to the right-top corner square being covered with vertical 2 x 1 tile, horizontal 2 x 1 tile, L shaped tile and L-shaped tile the other way. This simplifies to $f(n) = f(n-1) + f(n-2) + 2*g(n-2)$.

Hint 5:

The recursion for $g(n)$ is $g(n) = g(n-1) + f(n-1)$. The two cases correspond to the square in (n+1)th column being covered by a horizontal 2 x 1, or a L-shaped tile.

Full solution

The solution for this assignment is included at the end of the quiz. The code executes within 0.00 seconds.

If we used naive recursion, the solution’s execution time would be way more than our lifetimes!