SS1 - Editorial

PROBLEM LINK:

Practice
Contest

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.

Capture

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;
} 
4 Likes

When will the editorial of "Nutella needs more help " will come out ?

1 Like
1 Like

:joy::joy: nehi denge re baba

1 Like