RAMLEELA - EDITORIAL (IEMCO16)

PROBLEM LINK:

Practice

Contest

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

4 Likes

Nice One!!! Thanks :slight_smile:

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
//