[Bitmask DP note] CSES Counting Tilings

CONTEXT:

Hi guys, so someone asked me this problem from CSES problemset. While solving it I realized there are plenty of interesting ways to solve this problem and for a beginner who is starting with dynamic programming, it is a nice exercise for them to go through all the ways as solving this problem as it gives a decent amount of exposure to the standard techniques and one might be able to get a lot of value out of it if done sincerely. So I thought it would be a good idea to dot all these ideas/solutions in one place, so one doesn’t have to search through a thousand places to learn them. I want to make it clear that this post isn’t a tutorial or an editorial and the techniques listed are pretty standard and most of you might be already aware of them, it’s just a collection of somewhat neatly written codes and ideas for beginners who are starting out with dp.


NOTATION:

  • B_i(K) = \begin{cases} 1& \text{$i$th bit of $K$ is set}\\ 0& \mathrm{otherwise}\\ \end{cases}
  • C(K,L) → Number of ways to go from a mask K to a mask L on filling the unoccupied cells in mask K.

  • F_ii th Fibonacci number.

  • \phi → Golden Ratio


\mathcal{O}(2^{N}NM) Solution:

DP[i][j][k] \rightarrow \text{ solution when we're currently at the point $(i,j) $ and first $i$ bits}\\\text{of $k$ correspond to $j$th column and rest of the bits belong to $j-1$ column}
DP[i][j][k] = \begin{cases} DP[i-1][j][k\oplus2^i]+DP[i-1][j][k\oplus 2^{i-1}]& B_i(k) \ \mathrm{and}\ B_{i-1}(k)\\ DP[i-1][j][k\oplus2^i] & \mathrm{otherwise}\\ \end{cases}

Final answer will be DP[N-1][M][0]. Since transitions a re straight forward I’ve dropped a couple of dimensions in the code. For details refer to USACO tutorial

CODE
#include "bits/stdc++.h"
using namespace std ;
const int M =1e9+7 ; 
int main(){
  int n,m ;
  cin >> n >> m ;
  vector<int>dp(1<<n) ;
  dp[(1<<n)-1]=1 ;
  for(int j=0;j<=m;j++){
    for(int i=0;i<n;i++){
      vector<int>DP(1<<n) ;
      for(int k=0;k<(1<<n);k++){
        (DP[k]+=dp[k^(1<<i)])%=M ;
        if(i&&(k>>i&1)&&(k>>(i-1)&1))
          (DP[k]+=dp[k^(1<<(i-1))])%=M ;
      }
      swap(dp,DP) ;
    }
  }
  cout<<dp[0] ;
 
}

\mathcal{O}(4^N\ M ) Solution:

DP[j][k] \rightarrow \text{Number of ways to fully cover first $j-1$ columns and have a } \\ \text{mask $k$ on the $j$th column where every set bit in $k$ corresponds to an already}\\ \text{occupied cell and unset bit to unoccupied cells.}
\displaystyle DP[j+1][L]=\sum_{K=0}^{2^N-1}C(K,L)\times DP[j][K]

Final answer would be DP[M+1][0]

CODE
#include "bits/stdc++.h"
using namespace std ;
const int M =1e9+7 ; 
const int mxN=1e3,mxM=(1<<10) ;
int DP[mxN+1][mxM+1],C[mxM+1][mxM+1] ;
int main(){
  int n,m ;
  cin >> n >> m ;
  for(int k=0;k<(1<<n);k++){
    for(int l=0;l<(1<<n);l++){
      int c=1;
      for(int i=0;i<n;i++){
        if((k>>i&1)&&(l>>i&1)){
          c=0 ; break ;
        }
        if(!(k>>i&1)&&!(l>>i&1)){
          if(i+1<n&&!(k>>(i+1)&1)&&!(l>>(i+1)&1)){
            i++ ;  continue  ;
          }
          c=0 ;  break ;
        }
      }
      C[k][l]=c ;
    }
  }
  DP[0][0]=1 ;
  for(int j=0;j<m;j++)
    for(int k=0;k<(1<<n);k++)
      for(int l=0;l<(1<<n);l++)
        (DP[j+1][l]+=C[k][l]*DP[j][k])%=M ;
  cout << DP[m][0];
}

\mathcal{O}((1+\phi)^NM) Solution:

This solution is essentially the same as a previous solution but this time instead of calculating all the ways in which we can reach a particular mask we calculate the number of masks where we can transition to from a particular mask in a recursive manner. Runtime of this solution will be \displaystyle M\times\sum_{i=0}^N\binom{N}{i}\mathcal{O}(F_i) \equiv \mathcal{O}((1+\phi)^NM). Transitions and states are exactly the same. For details refer to Tutorial on Broken profile DP

CODE
#include "bits/stdc++.h"
using namespace std ;
const int mxN=1e3,M=1e9+7 ;
int dp[mxN+1][(1<<10)+1],n,m ;
void calc(int i,int j,int k,int l){
  if(i==n){
    (dp[j+1][l]+=dp[j][k])%=M ;
    return ;
  }
  if(k>>i&1){
    calc(i+1,j,k,l) ;
    return ;
  }
  if((i+1<n)&&!(k>>(i+1)&1))
    calc(i+2,j,k,l) ;
  calc(i+1,j,k,l^(1<<i)) ;
}   
int main(){
  dp[0][0]=1 ;     
  cin >> n >> m ;
  for(int j=0;j<m;j++)
    for(int k=0;k<(1<<n);k++)
      calc(0,j,k,0) ;
  cout << dp[m][0] ;
}

\mathcal{O}(8^N \log M) Solution:

This is my favorite, this solution is also an extension of \mathcal{O}(4^NM) solution but here we can clearly every see that interstate transition is independent of the column index hence(only depends on C(K, L)) we can speed up this solution by matrix exponentiation.

CODE
#include "bits/stdc++.h"
#define ll long long 
using namespace std ;
const int M =1e9+7 ; 
int n,m ; 
struct mat {
  vector<vector<ll>>a ;
  int N;
  mat(int _N):N(_N){
    a=vector<vector<ll>>(N,vector<ll>(N)) ;
  }
  void ide(){
    for(int i=0;i<N;i++)
      a[i][i]=1  ;
  }
  mat operator*(const mat &o) const {
    mat r(N);
    for(int i=0; i<N; ++i)
      for(int k=0; k<N; ++k)
        for(int j=0; j<N; ++j)
          r.a[i][j]=(r.a[i][j]+a[i][k]*o.a[k][j])%M;
    return r;
  }
};
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);   
  cin >> n >> m ;
  mat R(1<<n),C(1<<n) ;
  for(int k=0;k<(1<<n);k++){
    for(int l=0;l<(1<<n);l++){
      int c=1;
      for(int i=0;i<n;i++){
        if((k>>i&1)&&(l>>i&1)){
          c=0 ; break ;
        }
        if(!(k>>i&1)&&!(l>>i&1)){
          if(i+1<n&&!(k>>(i+1)&1)&&!(l>>(i+1)&1)){
            i++ ;  continue  ;
          }
          c=0 ;break ;
        }
      }
      C.a[l][k]=c;
    }
  }
  R.ide() ;
  for(;m;C=(C*C),m/=2)
    if(m&1)
      R=(R*C) ;
  cout << R.a[0][0] ;
}

This solution will not pass for constraints where N is large but will work fine even for tremendously large M's, for constraints like : N\le6,M\le10^{12}

5 Likes

Can you explain the transitions of O(2^N NM ) , I am unable to understand the transitions from USACO tutorial

Did you understand the states correctly? I mean how is this figure representing DP[1][3][01011_2]?
image

1 Like

Yes , the first 2 are from 3rd column ( 0-based indexing) and last 3 from 2nd column

All right, so say we encounter an unset bit in the mask of k (empty cell) then the number of ways for such cell (i,j) with mask k will be DP[i-1][j][k\oplus2^i] as the state definition says all cells till (i,j-1) should be filled \implies i th bit in the mask of k should be set but since it is unset right now we xor it with 2^i to set it and then we can get its value from the previous row.
Now say we encounter a set bit then there are 2 ways

  • We had it covered by a horizontal tile (1x2) in that case it is essential for us to have the (i,j-1) cell empty in the previous step. But in the current mask k it’s set so we again xor it with 2^i to unset it and now we can take the value from the previous step by DP[i-1][j][k\oplus 2^i]
  • We covered it with a vertical tile, but then we must ensure that it isn’t the 1st cell and also the cell (i-1,j) is covered \implies i-1 th bit in k is set. After this validation we again check what should the scenario in the previous step should be, the cell (i-1,j) should be empty so that we can place a vertical tile here but currently, in the mask, it is set so we again xor it with 2^{i-1} to toggle it (we don’t care about i th bit currently as by state definition it should be empty and it’s not present in the mask in the previous step)hence it would also contribute to state (i,j,k) by a value of DP[i-1][j][k\oplus2^{i-1}]
1 Like

Okk , Got it Thanks :slightly_smiling_face:

1 Like

hey bhai i abhay patel i want to help from you