Setter : Mohammad Salik
Tester : Hasan Jaddouh
Editorialist : Mohammad Salik
Difficulty
Medium
Prerequisites
Dynamic Programming
Problem
You are given 2 boxes box1 and box2 containing p and q sweets respectively .A person wants to pick N sweets from these 2 boxes$ ( N<=p+q ) $with the following conditions :
- No more than Si sweets can be taken from box i in one step .
- box i cannot be opened more than Bi times in total
We have to find the number of different ways in which the above task can be performed (mod 10^9+7)
Explanation
Few Points to Note :
- $B1,B2$ cannot be more than 50 :: at max 50 sweets are present in the box , and when one box is opened at least 1 sweet has to be taken from it. - $S1,S2$ cannot be more than 50 :: at max 50 sweets are present in the box , so not more than 50 sweets can be eaten from it a time.For Subtask 1:
A simple recursive solution will pass for subtask 1.
long long recurse(int a,int b,int m,int b1d,int b2d,int s1d,int s2d)
{
if(a>p)
return 0;
if(b>q)
return 0;
if(b1d>b1)
return 0;
if(b2d>b2)
return 0;
if(m==n)
return 1;
if(m==0)
{
return recurse(a+1,b,m+1,b1d+1,b2d,s1d+1,0)+recurse(a,b+1,m+1,b1d,b2d+1,0,s2d+1);
}
else
{
if(s1d==s1)
//no more sweets can be taken from box1 in this step now so we switch to box2
{
return recurse(a,b+1,m+1,b1d,b2d+1,0,s2d+1);
}
else if(s2d==s2)
//no more sweets can be taken from box2 in this step so we switch to box1
{
return recurse(a+1,b,m+1,b1d+1,b2d,s1d+1,0);
}
else if(s1d>0)
//the last sweet was taken from box1
{
return recurse(a+1,b,m+1,b1d,b2d,s1d+1,0)+recurse(a,b+1,m+1,b1d,b2d+1,0,s2d+1);
}
else if(s2d>0)
//the last sweet was taken from box2
{
return recurse(a+1,b,m+1,b1d+1,b2d,s1d+1,0)+recurse(a,b+1,m+1,b1d,b2d,0,s2d+1);
}
}
}
recurse(0,0,0,0,0,0,0);
The code runs in exponential time , so only subtask 1 can pass
For Subtask 2 and 3:
A DP(Dynamic Programmed) code needs to be written. With current variables being stored in the dp table,the time complexity will be much higher for subtask 2 and 3 to pass
//(int a,int b,int m,int b1d,int b2d,int s1d,int s2d)
//----50----50----100-----50------50------50------50
Time Complexity : 50$5010050505050*$10(test cases)( order of 10 ^ 11 )
Few Points to Note :
- We can find how many times the other box has been opened if we have the information about how many times the first box has been opened . i.e. B2 can be found out if we have the value of B1 and the information about which was the very first box to be opened.
- s1d and s2d cannot be more than 0 at the same time : which implies that we can remove one of the states from our dp.
- We do not need the variable m in our dp state as m is a dependant variable (always equal to sum of a and b)
s1d and s2d replaced by variables named cont ,representing the the number of times a particular box has been opened continuously, and boxnumber representing which box has been opened cont times consequetively.
b1d and b2d replaced by variables b1d and val
If 2nd box is opened initially:
val = 1
else
val = 0
If the first box to be opened was box 1 and boxnumber is 1 ( i.e the first box is being currently opened )
b2d = b1d -1
If the first box to be opened was box 2 and boxnumber is 1 ( i.e the first box is being currently opened )
b2d = b1d
If the first box to be opened was box 1 and boxnumber is 2 ( i.e the second box is being currently opened )
b2d = b1d
If the first box to be opened was box 2 and boxnumber is 2 ( i.e the second box is being currently opened )
b2d = b1d +1
Incorporating these conditions in the form of variables :
if(boxnumber==1)
b2d=b1d-1+val;
else
b2d=b1d+val;
Final Code :
long long recurse(int a,int b,int m,int b1d,int cont,int boxnumber,int val)
{
if(a>p)
return 0;
if(b>q)
return 0;
if(b1d>b1)
return 0;
int b2d,s1d,s2d;
if(boxnumber==1)
b2d=b1d-1+val;
else
b2d=b1d+val;
if(b2d>b2)
return 0;
if(m==n)
return 1;
if(dp[a][b][b1d][cont][boxnumber][val]!=-1 )
return dp[a][b][b1d][cont][boxnumber][val];
if(boxnumber==1)
{
s1d=cont;
s2d=0;
}
else
{
s2d=cont;
s1d=0;
}
if(s1d==s1)
{
dp[a][b][b1d][cont][boxnumber][val]=recurse(a,b+1,m+1,b1d,1,2,val);
return dp[a][b][b1d][cont][boxnumber][val]%mod;
}
else if(s2d==s2)
{
dp[a][b][b1d][cont][boxnumber][val]=recurse(a+1,b,m+1,b1d+1,1,1,val);
return dp[a][b][b1d][cont][boxnumber][val]%mod;
}
else if(s1d>0)
{
dp[a][b][b1d][cont][boxnumber][val]=(recurse(a+1,b,m+1,b1d,s1d+1,1,val)
+recurse(a,b+1,m+1,b1d,1,2,val))%mod;
return dp[a][b][b1d][cont][boxnumber][val];
}
else if(s2d>0)
{
dp[a][b][b1d][cont][boxnumber][val]=(recurse(a+1,b,m+1,b1d+1,1,1,val)+
recurse(a,b+1,m+1,b1d,s2d+1,2,val))%mod;
return dp[a][b][b1d][cont][boxnumber][val];
}
}
recurse(1,0,1,1,1,1,0) //box 1 opened initially //boxnumber=1,val=0 //b1d=1 ( box 1 opened continuously once ) +recurse(0,1,1,0,1,2,1)) //box 2 opened initially //boxnumber=2,val=1 //b1d=0 ( box 1 opened continuously zero times )
//(int a,int b,int b1d,int cont,int boxnumber,int val)
//----50----50---- 50------50----------2------------2 Time Complexity : 50$$50$∗$50$∗$50$∗$2$∗$2$$10 ( order of 10 ^ 7 )
Time Complexity
O(T*p*q*min(B1,p)*min(S1,p)*4) per testcase
Space Complexity
O(p*q*min(B1,p)*min(S1,p)*4)
