 # RAMLEELA - EDITORIAL (IEMCO16)

Practice

Contest

Author: Shrirupa Bhattacharjee

Tester: Bhavesh Toshniwal

Editorialist: Shrirupa Bhattacharjee

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] be the number of ways to place a diya at the end of the row , and dp[i][j] 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] can be solved by considering all the arrangements of dp[i-k][j] where 1<=k<=n1. Similarly dp[i][j] can be solved by considering all the arrangements of dp[i][j-k] where 1<=k<=n2. The answer will be the sum of dp[d][c] and dp[d][c].

### 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 and dp, which is equal to 1. If Rohit wants to put a diya at the end, the state dynamics of the dp[i][j] will go to the state dp[i-k][j], where k lies between 1 and min(n1,i). If Rohit wants to put a candle, the state dynamics of the dp[i][j] will go to the state dp[i][j-k], 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] and dp[d][c]. Since the values can be very large, we perform the modulo operation at every step.

Pseudo Code

MOD=1e9+7;

dp=dp=1;

for(i=0;i<=d;i++){

for(j=0;j<=c;j++){

for(k=1;k<=min(i,n1);k++){

dp[i][j]+=dp[i-k][j];

dp[i][j]%=MOD;}

for(k=1;k<=min(j,n2);k++){

dp[i][j]+=dp[i][j-k];

dp[i][j]%=MOD;}}}

print (dp[d][c]+dp[d][c])%MOD

### AUTHOR’S SOLUTION:

Author’s solution can be found here

4 Likes

Nice One!!! Thanks 1 Like

Nice blog!!! Thank you for passing this information.As a staff of case qatar.The algorithm was really helpful for me.

yupp…the author explained it very well!!

1 Like