CareerCup

At first it seems like a dynamic programming type of problem but looking more closely it reduces to the simple problem of finding the nth Fibonacci number. Denote by f(n) the number of possibilities to tile a 2xn board.

Consider tiling a 2xn board for some n>2. Let us sort all the possibilities according to the last 2 columns. There are f(n-1) possibilities where the last column includes a single tile and there are f(n-2) possibilities where the last 2 columns include 2 horizontally placed tiles. This covers all possibilities and hence: f(n) = f(n-1) + f(n-2) which is exactly the nth Fibonacci number.

The common iterative O(n) solution for finding the nth Fibonacci number is as follows:

public static long tilings(int n){
		if (n<=0){return 0;}
		if (n==1){return 1;}
		long prev = 1;
		long cur = 2;
		for (int i=3;i<=n;i++){
			cur += prev;
			prev = cur - prev;
		}
		
		return cur;
	}

A more efficient solution (O(logn) can be achieved by using the matrix representation for finding the nth Fibonacci number:

private boolean isLegal2By2Matrix(long[][] m){
		if ((m==null) || (m.length!=2)){return false;}
		for (int i=0;i<m.length;i++){
			if ((m[i]==null) || (m[i].length!=2)){return false;}
		}
		
		return true;
	}
	
	private long[][] mul(long[][] m1, long[][] m2){
		if ((!isLegal2By2Matrix(m1)) || (!isLegal2By2Matrix(m2))){return null;}
		
		long[][] res = new long[2][2];
		
		for (int i=0;i<res.length;i++){
			for (int j=0;j<res[i].length;j++){
				res[i][j] = (m1[i][0]*m2[0][j]) + (m1[i][1]*m2[1][j]);
			}
		}
		
		return res;
	}
	
	private long[][] nthPower(long[][] m, int n){
		if ((n<1) || (!isLegal2By2Matrix(m))){return null;}
		if (n==1){return m;}
		long[][] pM = nthPower(m,(n/2));
		long[][] res = mul(pM,pM);
		
		return (n%2==0) ? res : mul(res,m);
	}
	
	public long tilings2(int n){
		if (n<=0){return 0;}
		if (n<=2){return n;}
		
		long[][] m = {{1,1},{1,0}};
		long[][] fm = nthPower(m,n-2);
		
		return (fm[0][0]*2) + fm[0][1];
	}

Please clear my doubt. Are all arrangements unique? What I mean it consider a 2x3 board, there can be 2 unique ways of arranging 2x1 tiles. However, you can also do another ways if you consider all arrangements unique.

_____
| |___|
I_ |___| is same as

_____
|___| |
|___| _|

I din't understand why f(3) is not 24: here are all the possibilities:

If I'm right the formula to f(n) is f(n)=n*2*f(n-1), or I'm missing something?

|a|b|c| |a|c|b| |b|a|c| |b|c|a| |c|b|a| |c|a|b|
|a|b|c| |a|c|b| |b|a|c| |b|c|a| |c|b|a| |c|a|b|

|a|a|c| |b|b|c| |a|a|b| |c|c|b| |c|c|a| |b|b|a| 
|b|b|c| |a|a|c| |c|c|b| |a|a|b| |b|b|a| |c|c|a| 

|c|a|a| |c|b|b| |b|a|a| |b|c|c| |a|c|c| |a|b|b| 
|c|b|b| |c|a|a| |b|c|c| |b|a|a| |a|b|b| |a|c|c|

I think the solution would be
F(n) = int(n/2) * (n+1)

Every 2x2 block on the board will result in 2 ways.. and in 'n' is odd, we need to place one more block which has n + 1 options.

Can anyone please tell me if this doesn't work in any case?

Thank you.

f(1) = 1 + (1-1)+ (1-1) = 1
f(2) = 2 + (2-1)+ (2-1) = 4

It's a combination problem

for i from 0 to [n/2]
sum = 0
sum = sum + Combination (pick n-2*i elements from n-i elements)

In a board of 2 x N (2 rows and N cols) tiles, N - 2 x 1 tiles can be placed.
Therefore each of N tiles has an option of being placed Horizontal(0) or Vertical(1): Orientation and a choice of position.
The solution is split into solving Orientation for each tile and then its positions.

Deciding Orientation:
Choose 0 or 1 for each tiles, therefore pow(2,N) possibilities. For ex: 100 - place first tile vertical and next two tiles horizontal

But there are two restrictions to this approach
Restriction:1) There cannot be odd number of Horizontal tiles as it creates a horizontal space that can be filled only by another horizontal tile.(applicable for a board of 2 rows and N cols - for N x 2 board vice versa with Vertical applies)
So choose 0 or 1 for each tile from 1 to n-1.There are pow(2,n-1) possibilities and decide the orientation for the last tile based on the number of horizontal tiles.
If there are odd number of horizontal tiles upto n-1, then the choice for last tile is horizontal. If even number of horizontal tiles found upto n-1 then choice for the last is vertical. As there is only one orientation for the last tile, the total number of choices till now is pow(2,n-1)
Restriction:2) there should be two consecutive Horizontal tiles so that they can placed one below the other. Choice of 010 is physically invalid in the board as the arrangement will become either 001 or 100. In other words horizontal should be followed by horizontal. So from the pow(2,n-1) possibilities, some of the possibilites should be reduced

Summing up above two, there should be even number of tiles and horizontal tiles should be paired next to each other (that is 00 in choice)

For ex:
possibilities of placeing 3 - 2x 1 tiles in a 2 x 3 board
001
010 - invalid (when placed in the board will become 100 or 001)
011 - invalid (odd number of horizontal)
100
101 - invalid (odd number of horizontal)
110 - invalid (odd number of horizontal)
111
only 3 possiblities out of pow(2,3-1) = 4 possibilities (or out of 8 possibilties for 3 tiles as shown above)

Position:
for example if we choose the arrangement 100, three tiles A,B,C can be arranged 3! ways
Similarly for 001 and 111.

So there are 3 * 3! = 18 possible arrangements in the board.

This is more like a math problem, you can come up with a closed math formula. As explained above, it's like getting # of possible pattern of V(vertical) and H(horizontal) letters where #V + (2*#H) = N. So it will be Sigma(i=0,2,..,N) (((N-i)/2) + i))! / (i! ((n-i)/2)!) when N is even, or Signa(i=1,3,..,N) (same) when odd.