This is my first Blog. I hope, this blog would be useful for the programmers out there. This blog is an extension to a previous CSES DP editorial written by icecuber. The link to the blog is here. It was a great editorial and which inspired me to complete that with these few leftover problems.
Problems covered in this editorial:Counting Towers, Elevator Rides, Counting Tilings, Counting Numbers.
Feel free to point out mistakes
Counting Towers (2413)
dp[i][p]=Number of ways to fill from 0th position till the ith position.
here p denotes the tile at ith position as following:
dp[i][0] => number of ways for the same such that ith position consist of 2 tiles of width 1 each.
dp[i][1] => number of ways for the same such that ith position consist of 1 tile of width 2.
So,recurrence would be:
recurrencedp[i][1] = 2*dp[i-1][1] + dp[i-1][0]
dp[i][0]= dp[i-1][1] + 4*(dp[i-1][0])
dp[i][1] = 2*dp[i-1][1] +dp[i-1][0]
=>2*ways because we can either extend the current level to one level down or keep another new tile + 1*ways because we can only keep another new tile and cannot extend the current level downwards
dp[i][0] = dp[i-1][1]+ 4*dp[i-1][0]
=>1*ways because we can only keep another new set of tiles and cannot extend the current level + 4*ways because we can either keep a new tile, or extend both the sides together or extend a single side at one time(left or right side, so intotal 4 ways
Time complexity here is O(N) for preprocessing and O(1) for answering each query. So, O(T + N) in total.
Code
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<b;i++)
#define modm 1000000007
#define ll long long
const int N=1000005;
ll dp[N][2];
int main(){
dp[1][0]=1;
dp[1][1]=1;
for(int i=2;i<=N;i++){
dp[i][1]=(2*(dp[i-1][1]%modm))%modm + (dp[i-1][0]%modm);
dp[i][0]=(dp[i-1][1]%modm)+(4*(dp[i-1][0]%modm))%modm;
}
int t;cin>>t;
while(t--){
int n;cin>>n;
cout<<(dp[n][0]%modm+dp[n][1]%modm)%modm<<"\n";
}
return(0);
}
Elevator Rides (1653)
its a classical problem of dp with bitmasking. here, I have defined dp as follows:
dp[number of rides][weight on the last elevator used]
So, basically, as number of rides is atmost 20, we can use mask to represent the people we have carried to the top of the building. I have added comments in the code to make it easy to comprehend and understand.
Code#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ff first
#define ss second
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cout.tie(0);
int n,x;cin>>n>>x;
vector<int> w(n);
for(int i=0;i<n;i++){
cin>>w[i];
}
vector<pii> dp(1<<n);
dp[0]={1,0};
for(int mask=1;mask<(1<<n);mask++){
//to store the best result for a particular mask. Best result means less number of rides
pii bestResult={INT_MAX,INT_MAX};
for(int j=0;j<n;j++){
if(mask &(1<<j)){
auto res = dp[mask^(1<<j)];
//the jth person can be accommodated in the last ride, we have used, so number of rides remain same
if(res.ss + w[j] <=x ){
res={res.ff,res.ss+w[j]};
}
//the jth person need another new ride
else{
res = {res.ff+1, w[j]};
}
bestResult=min(bestResult,res);
}
}
dp[mask] =bestResult;
}
cout<< dp[(1<<n)-1].ff<<"\n";
return(0);
}
Counting Numbers (2220)
It is a good problem for learning digit DP.
dp state is defined as follows:
dp[ith digit from left][previous digit][leading zeroes][tight]
leading zeroes are the zeroes that come before the first non-zero digit in a number eg:0034, 012.
I have added comments in the code for better understanding. This is a standard digit DP problem.
Code#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<b;i++)
#define int long long
int dp[20][10][2][2];
// finding number of numbers having no adjancent digit from 0 to n
int solve(string& num,int n,int prev_dig,int i,bool leading_zeroes,int tight){
if(i==n){
return(1);
}
if(prev_dig!=-1 and dp[i][prev_dig][leading_zeroes][tight]!=-1){
return(dp[i][prev_dig][leading_zeroes][tight]);
}
// bounds for the ith digit - possible values for the ith digit
int lb = 0;
int ub = (tight==1)?(num[i]-'0'):9;
int ans=0;
f(dig,lb,ub+1){
//case of similar adjancent digits
if(dig==prev_dig and dig!=0){continue;}
// case when '00' occurs in the number (but not at the start(seen from left side))
if(dig==prev_dig and dig==0 and leading_zeroes==0){continue;}
ans+= solve(num,n,dig,i+1,leading_zeroes&dig==0 ,tight&(dig==ub));
}
return(dp[i][prev_dig][leading_zeroes][tight]= ans);
}
bool check(string a){
int ns=a.size();
bool flag=true;
f(i,1,ns){
if(a[i-1]==a[i]){flag=false;}
}
return(flag);
}
int32_t main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cout.tie(0);
string a,b;
cin>>a>>b;
int na=a.size();
int nb=b.size();
memset(dp,-1,sizeof(dp));
int ans= solve(b,nb,-1,0,1,1);
memset(dp,-1,sizeof(dp));
ans -= solve(a,na,-1,0,1,1);
ans+= check(a)?1:0;
cout<<ans<<"\n";
return 0;
}
Counting Tilings (2181)
This is a very interesting classical problem of DP with bitmasking. Here masking is used to represent the blocks currently filled in ith column due to arrangement of blocks on (i-1)th column.
here dp state is defined as follows:
dp[i][mask] = number of ways to fill the grid from ith column to mth column such that the ith column arrangement due to (i-1)th column is represented by mask.
I have added comments in the code for better understanding.
Code#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<b;i++)
#define int long long
#define modm 1000000007
#define vi vector<int>
#define pb push_back
int n,m;
int dp[1005][(1<<12)];
//generating all possible mask- representing all possible states given the current mask
//here i represents the row
void generate_next_masks(int current_mask,int i,int next_mask, vi& container){
if(i==(n+1)){
container.pb(next_mask);
return;
}
if(current_mask&(1<<i)){
generate_next_masks(current_mask,i+1,next_mask,container);
}
if(i!=n){
if(((current_mask & (1<<i))==0) and ((current_mask&(1<<(i+1))) ==0) ){
generate_next_masks(current_mask,i+2,next_mask,container);
}
}
if((current_mask&(1<<i))==0){
generate_next_masks(current_mask, i+1 , next_mask+(1<<i) , container);
}
}
int solve(int col,int mask){
if(col == (m+1)){
//checking that no block flows out of the board at the last column. That's there is not block of size 1x2 in the ith column
if(mask==0){
return(1);
}
return(0);
}
if(dp[col][mask]!= -1){return(dp[col][mask]);}
int ans=0;
vi next_masks;
generate_next_masks(mask,1,0,next_masks);
//trying with all possible mask for the current column
for(auto maskk : next_masks){
ans = (ans%modm + solve(col+1,maskk)%modm)%modm;
}
next_masks.clear();
return(dp[col][mask]=ans%modm);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
memset(dp,-1,sizeof(dp));
cout<<solve(1,0)<<"\n";
return 0;
}