Broken profile dynamic programming

Prerequisites: Dynamic Programming, Bit masking

Consider the following problem.

Problem: In how many ways can you fill an

$n \times m$ board with

$2 \times 1$ dominoes such that whole board is covered and no two dominoes overlap with each other?

Constraints:

$1 \leq n \leq 9$

$1 \leq m \leq 1000$

Solution: One way of solving this problem is to obtain a recurrence relation for a given

$n$ in terms of

$m$ . For example, if

$n = 2$ , we get the recurrence relation

$f_{m} = f_{m-1} + f_{m-2}$ And if

$n = 3$ , we get the recurrence relation

$f_{m} = 4f_{m-1} - f_{m-2}$ Click here for detailed explanation on above recurrence relations.

But obtaining recurrence relation becomes harder as

$n$ increases. So, instead we shall approach this problem in a different way. Let us define profile of some column as an n-bit binary integer which gives information of the occupancy of blocks in that column i.e. if

$i$ th bit is equal to

$1$ then

$i$ th block in that column is occupied by some domino and if it is equal to

$0$ then it is not occupied. Let us define our DP state as

$dp[i][p]$ (1-based indexing) which is equal to numbers of ways of filling first

$i$ columns completely with dominoes (without leaving any block as empty). Here

$p$ is the profile of

$(i+1)$ th column obtained after filling first

$i$ columns. Note that, the

$(i+1)$ th column should not contain a complete domino as our intention is to use dominoes for filling the first

$i$ columns. Here is an example.

But how do we obtain the relation between the states? One way is to obtain the value of

$dp[i][p]$ from

$dp[i-1][q]$ by expressing the former as the sum of all

$dp[i-1][q]$ for which there exists a filling of

$(i)$ th column with dominoes, leaving the

$i+1$ th column with profile

$p$ . Time complexity for calculating

$dp[i][p]$ is equal to

$O(2^n)$ . As there are

$m \times 2^n$ states, so the total time complexity becomes equal to

$O(m \times 2^{2n})$ .

But we would get TLE verdict for above algorithm. To avoid this, instead of finding all possible profiles

$q$ such that

$dp[i-1][q]$ can produce

$dp[i][p]$ , for a given profile

$q$ we find all possible profiles

$p$ such that

$dp[i-1][q]$ can produce

$dp[i][p]$ and add the value of

$dp[i-1][q]$ to

$dp[i][p]$ . This means that we check all possible ways of filling the

$i$ th column which has profile

$q$ . To do this let us analyse the

$i$ th column from

$1$ st block of the column to

$n$ th block of the column.

If the

$j$ th block is already occupied by some domino, then do nothing.

Else, this block can be filled in at most two ways as listed below

Place a domino in blocks $(i,j)$ and $(i+1,j)$ and mark them as occupied.
Place a domino in blocks $(i,j)$ and $(i,j+1)$ and mark them as occupied if ( $j+1)$ block exists and is unoccupied.

Each permutation filling the current column produces a unique profile

$p$ representing the

$(i+1)$ th column. So we add

$dp[i][q]$ to

$dp[i+1][p]$ where

$q$ is the profile of

$i$ th column before filling.

Now, observe that for

$i = 0$ , filling first

$0$ columns completely and having profile

$p$ for

$1$ st column is possible iff

$p = 0$ . This implies that

$dp[0][p]$ is equal to

$1$ for

$p = 0$ and equal to

$0$ for all

$p \neq 0$ .

Since we need to fill all

$m$ columns with the profile for

$(m+1)$ th column equal to 0 (as there exists no

$(m+1)$ th column), the required answer is equal to

$dp[m][0]$ .

Run Time Analysis: For a particular column with

$k$ empty blocks, the worst case run time of the above analysis is

$O(f_{k})$ , where

$f_{k}$ is

$k$ th fibonacci number. There

$^{n}C_{k}$ profiles with

$k$ empty blocks. Also there are

$m$ columns. So, the total run time is

$m \times \sum_{k = 0}^{n}$

$^{n}C_{k} \times O(f_{k})$ which is equal to

$O(m \times (1+ \phi)^n)$ . Observe that this algorithm is very efficient than the previous one.

Source for this topic.

P.S. This is my first blog post. Any constructive feedback is welcome :).

Practice Problems:

1. Same problem but with

$3 \times 1$ dominoes.

2. Mosaic

Code:

	int board[m+1][n+1], dp[m+1][(1<<n)];
	int n,m;

	bool occupied(int i, int q){ //Check if ith block is occupied in profile q.
	return q&(1 << (i-1));
	}

	void search(int i, int j, int p, int q){
	if(i == n+1){
	dp[j+1][p] += dp[j][q];
	return;
	}
	if(occupied(i, q)){
	search(i+1, j, p, q);
	return;
	}
	if(i+1 <= n && !occupied(i+1, q)){
	search(i+2, j, p, q);
	}
	if(j+1 <= m){
	search(i+1, j, p^(1 << (i-1)), q);
	}
	}

	int main(){
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1; //Initial condition
	for(int j = 1; j < m; j++){
	for(int q = 0; q < (1<<n); q++){
	search(1, j, 0, q);
	}
	}
	cout<<dp[m][0]<<endl;
	}

view raw brokenProfileDP.cpp hosted with ❤ by GitHub

Evilbuggy

Search This Blog

Broken profile dynamic programming