PROBLEM LINK:
Author: Shrirupa Bhattacharjee
Tester: Bhavesh Toshniwal
Editorialist: Shrirupa Bhattacharjee
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
DYNAMIC PROGRAMMING
PROBLEM:
You have been provided with no:of diyas d, no:of candles c, maximum no:of diyas that can be placed together n1 and maximum no:of candles that can be placed together n2 .
QUICK EXPLANATION:
The problem can be best solved using dynamics. Let dp[i][j][0] be the number of ways to place a diya at the end of the row , and dp[i][j][1] be the number of ways to place a candle at the end of the row after ‘i’ no:of diyas and ‘j’ no:of candles have already been arranged. dp[i][j][0] can be solved by considering all the arrangements of dp[i-k][j][1] where 1<=k<=n1. Similarly dp[i][j][1] can be solved by considering all the arrangements of dp[i][j-k][0] where 1<=k<=n2. The answer will be the sum of dp[d][c][0] and dp[d][c][1].
EXPLANATION:
Consider the state dp[i][j][x]. The first parameter ‘i’ - indicates the total no:of diyas used till now, similarly second parameter ‘j’ - indicates the no:of candles used till now, the third parameter x (0/1) - indicates what Rohit wants to put at the end of the line. The initial state can be given as dp[0][0][1] and dp[0][0][0], which is equal to 1. If Rohit wants to put a diya at the end, the state dynamics of the dp[i][j][0] will go to the state dp[i-k][j][1], where k lies between 1 and min(n1,i). If Rohit wants to put a candle, the state dynamics of the dp[i][j][1] will go to the state dp[i][j-k][0], where k lies between 1 and min(n2,j). Hence the total no:of ways of arranging diyas and candles is equal to sum of dp[d][c][0] and dp[d][c][1]. Since the values can be very large, we perform the modulo operation at every step.
Pseudo Code
MOD=1e9+7;dp[0][0][0]=dp[0][0][1]=1;
for(i=0;i<=d;i++){
for(j=0;j<=c;j++){
for(k=1;k<=min(i,n1);k++){
dp[i][j][0]+=dp[i-k][j][1];
dp[i][j][0]%=MOD;}
for(k=1;k<=min(j,n2);k++){
dp[i][j][1]+=dp[i][j-k][0];
dp[i][j][1]%=MOD;}}}
print (dp[d][c][0]+dp[d][c][1])%MOD
AUTHOR’S SOLUTION:
Author’s solution can be found here
