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;
}
In counting towers solution you have written dp[i][p] is Number of ways to fill from ith position till nth position But I think what you mean is number of ways to fill from 0th position to ith position
Yeah... Thank you for pointing out the mistake...I have corrected it as well as added some explanation (although the formatting may not be very good, advice on that will be highly welcomed).
this is kartik arora's, code and explanation If i'm not wrong.
can you explain these 3 lines of code-
Hey i have a doubt, Is there any way in which we can calculate answer for multiple queries without Recalculating whole dp in Counting Digts problem as Tight depends of the current digit in the number and i tried but can't seem to find one.
what does the number in the bracket means? Counting Towers (2413) ? what does 2413 means?
it means 2413
is that the expected rating of the problem or some kind of indexing?
it means 2413
Id in the url if you go to that question on the cses site
In Counting Tilings, container can have atmost ~89 masks for any (i,j) so 89*(2^10)*1000.