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_i → i th Fibonacci number.
-
\phi → Golden Ratio
\mathcal{O}(2^{N}NM) Solution:
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:
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}
