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: