PROBLEM LINK:
Author: Sandeep Singh
Tester: Arkapravo Ghosh
Editorialist: Sandeep Singh
DIFFICULTY:
SIMPLE
PREREQUISITES:
Dynamic Programming
PROBLEM:
There are N stairs out of which K stairs are wet. We have to find the no. of ways to reach the N - th stair by avoiding all the wet stairs and only moving forward. It is given that only 1 or 2 stairs can be skipped at once i.e. from ith stair we can go to i+1- th, i+2-th and i+3-th stair only.
QUICK EXPLANATION:
We use dynamic programming to solve this, storing the answers to subproblems in the array dp[]. Since Chozi only moves forward, the only possible way to reach any ith (i>3) stair is the sum of ways to reach i-1th, i-2th, and i-3th stair. But if any stair is wet, then there are 0 ways to reach it. By setting the proper base cases, we can get the no. of ways to reach ith stair by the following equation
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
EXPLANATION:
After observation, you will realize that the solution to this problem is the same as that of tribonacci series with a small catch that there are wet stairs in between which will not contribute in further calculations. Since the only possibility to reach a stair is from any of the previous 3 stairs, the no. of ways to reach a dry stair will be the sum of ways of reaching the previous 3 stairs.
We will first set the base conditions as follows (Note that all calculations are using 1 based indexing)
For the sake of simplicity we will set dp[0]=1;
Now for the first stair, if it’s wet, dp[1]=0, else dp[1]=1 since Chozi can directly step on the first stair.
For the second stair, if its wet, dp[2]=0, else dp[2]=dp[1]+dp[0], as Chozi can step directly on 2 - nd stair or reachi it via stair 1;
similarly dp[3]=0,if stair 3 is wet, else dp[3]=dp[2]+dp[1]+dp[0]
For the rest of the stairs, if the ith stair is wet, Chozi cannot step on that stair so dp[i]=0, else dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
Also, we have to print answer modulo 10^9+7 so all calculations are done accordingly.
Here is a snippet of the recurrence formula.
This shows the bottom-up approach.
Time complexity is O(N).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define M 1000000007
ll dp[10000005];
using namespace std;
void solve(){
int N,K,i,temp;
cin>>N>>K;
memset(dp,-1,sizeof(dp));
for(i=0;i<K;i++){
cin>>temp;
dp[temp]=0;
}
dp[0]=1;
for(i=1;i<=N;i++){
if(dp[i]!=0){
if(i==1)
dp[i]=dp[i-1];
else if(i==2)
dp[i]=dp[i-2]+dp[i-1];
else
dp[i]=(dp[i-1]%M+dp[i-2]%M+dp[i-3]%M)%M;
}
}
cout<<dp[N]<<endl;
}
int main() {
//freopen("ip5.in", "r", stdin);
//freopen("op1.out", "w", stdout);
int T ;
cin>>T;
while(T--)
solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define T int tt; cin>>tt; while(tt--)
const ll MOD = (ll)(1e9+7);
int main() {
fastio;
//find_primes();
//binomial_pre();
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
T {
int n, k;
cin >> n >> k;
ll wet[n] = {0};
rep(i, 0, k) {
int x;
cin >> x;
wet[x] = 1;
}
ll dp[n+3] = {0};
dp[n] = 1;
for(int i = n-1; i >= 0; --i) {
if(wet[i]) continue;
dp[i] = (dp[i+1]+dp[i+2]+dp[i+3])%MOD;
}
cout << dp[0] << '\n';
}
return 0;
}