REACH_THE_TEMPLE EDITORIAL.
Problem Link:- TEMPLE
SETTER : @jprm2
Editorialist : @jprm2
Difficulty : Easy-Medium
Pre-Requisites : Recursion, Dynamic Programming,Observation.
EXPLANATION
Problem was pretty straight forward that you want to find the number of ways to reach the nth step of a temple taking exactly k steps given
steps sizes are a and b and c. Now first basic approach comes is for recursion. where what you can do simply is like given below.
50 points:- Recursion.
ll exactly_k_steps(ll n,ll steps)
{
if(n==0&&steps==k)
return 1;
if(n<0)
return 0;
if(steps>k)
return 0;
return exactly_k_steps(n-1,steps+1)+exactly_k_steps(n-2,steps+1) +exactly_k_steps (n-3,steps+1);
}
here a=1 ,b=2 and c=3 that is the value of step size or a leap size. for a particular step if your destination is n and you are at level 0 then you can leap either 1 step forward or 2 step forward or 3 step forward so as you move one step now the new problem becomes that for n-1 steps you have to reach inexactly k-1 steps or in k-1 steps you have to travel n-2 remaining steps or in k-1 steps you have to travel n-3 remaining steps .
I am starting with initial 0 steps and when my variable steps becomes exactly k I check if n is 0 or not if it is then I return 1 from that leaf of my recursion tree andelse I return 0 from that leaf that this way or this is not as per the conditions thus at root node finally that is in the main recursion call I will get all the possible solution numbers when at current I presently check by taking all the possible steps that is 1,2,3 .Now this recursion takes for a particular n it takes time equal to 3^k. which was satisfying 1st subtask.
Complete Solution : Dynamic Programming: 100 points.
Now see How we will memorize the our previously obtained problems for a particular n and k in a dp table of dp[10001][101] for storing results and optimizing the solution.
the code snippet is:-
#define P 1000000007
ll dp[100000][100];
ll a,b,c;
ll k;
ll exactly_k_steps(ll n,ll steps)
{
if(n==0&&steps==0)
return 1;
if(n<0)
return 0;
if(steps<0)
return 0;
if(dp[n][steps]!=-1)
return dp[n][steps];
dp[n][steps]= (exactly_k_steps(n-a,steps-1)%P+exactly_k_steps(n-b,steps-1)%P +exactly_k_steps (n-c,steps-1)%P)%P;
return (dp[n][steps])%P;
}
so we consider each new n and k as a particular solution of a particularly a new problem and we save the answer of this new problem and use it directly from
the memorization dp table. . I hope that dp solution is clear to you. modulo 1000000007 is just for preserving the number and not to overflow.
Setter’s and Editorialist’s Solution:
Setters and Editorialists Solutions.
Hope you liked it and feel free to share any approach or ask any doubts in comments below. Other optimal solutions are encouraged too.