SPOJ: M3TILE Solution Description

Question

I am trying to solve this programming problem , but since I cannot figure it out, I found a solution on the Internet. but I can’t understand why this solution works either.

the task is to calculate how many paths there can be 3 * n ( n >= 0 , n is the only input) the rectangle is completely filled with 2 * 1 dominoes.

eg. (red lines represent dominoes):

This is what I first painted on a piece of paper when I read the text, and saw that there are three possible combinations that a 3 * 2 rectangle can have, and that if n is odd, the solution is 0, because this is not a way to fill the entire rectangle then (one part will always remain uncovered dominoes).

So, I thought the solution was just 3^n if n was even, and 0 if n was odd. It turns out I was wrong.

I found a relatively simple solution here:

 #include <iostream> using namespace std; int main() { int arr[31]; arr[0]=1; arr[1]=0; arr[2]=3; arr[3]=0; for(int i = 4; i < 31; i++) { arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get } int n; while(1) { cin >> n; if(n == -1) { break; } cout << arr[n] << endl; } return 0; } 

Why does it work ?!

Answer 1

Let T(n) be the number of tile methods in a 3×n panel with 2×1 tiles. In addition, let P(n) be the number of ways to split a 3×n board into one corner, removed using 2×1 tiles. Suppose n is large enough ( >= 4 ).

Then consider how you can start shingles on the left (or right, it doesn't matter).

You can place a tile covering the upper left corner in two ways: vertical or horizontal. If you place it vertically, the tile covering the lower left corner should be placed horizontally, creating a configuration

 | == 

This leaves P(n-1) ways to partition the remainder. If you place it horizontally, you can place the slab covering the bottom left corner horizontally or vertically. If you place it vertically, you are in the same situation as before, you have just reflected, and if you place it horizontally, you must place the plate horizontally between them,

 == == == 

will leave you with a 3×(n-2) board to the tile. In this way,

 T(n) = T(n-2) + 2*P(n-1) (1) 

Now, looking at the 3×(n-1) panel with one remote (already closed) corner (let's say the upper left one), you can either place the plate vertically under it, indicating

 = | 

and leaving you with a 3×(n-2) board to the tile, or you can place two tiles horizontally below it, indicating

 = == == 

and then you have no choice but to place another plate horizontally at the top, leaving you

 === == == 

with a 3×(n-3) board minus the angle

 P(n-1) = T(n-2) + P(n-3) 

Adding

 T(n) = T(n-2) + 2*(T(n-2) + P(n-3)) = 3*T(n-2) + 2*P(n-3) (2) 

But, using (1) with n-2 instead of n , we see that

 T(n-2) = T(n-4) + 2*P(n-3) 

or

 2*P(n-3) = T(n-2) - T(n-4) 

Inserting this in (2) gives a repetition

 T(n) = 4*T(n-2) - T(n-4) 

qed

Answer 2

Share my tut.Hope image helps.

Answer 3

Start placing the tiles on the left, and the other types of problems you end up are shown in the diagram. In each case, I first place the red tile, then the yellow tile, and finally the green tile.

x (n) = x (n-2) + 2 * f (n-1) from cases (a), (b), (c)

f (n) = x (n-1) + f (n-2) from cases (d), (e).

We can express f (n) in terms of x (n).

Look at the image for further explanation.

Problem with tiles - Image

Source: https://www.quora.com/Can-somebody-explain-solution-to-SPOJ-com-Problem-M3TILE