ABX02 - EDITORIAL

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)

3 Likes

Is an O(n^2) Algorithm possible?

We can use the fact that the boxes must appear alternately. Consider the boxes are opened total l times. Then we have 2 choices about which box was opened first. If l is odd, the box opened first must be opened exactly \lceil l/2 \rceil times, and the other box must be opened exactly \lfloor l/2 \rfloor times. If l is even, the same choice applies but each must be opened exactly l/2 times. Additionally, if x is contributed by box 1, N-x must be contributed by box 2. So finally answer can be represented as

\sum_{l=1}^N \sum_{x=0}^N f_1(\lfloor l/2 \rfloor, x) \times f_2(\lceil l/2 \rceil, N-x) + f_1(\lceil l/2 \rceil, x) \times f_2(\lfloor l/2 \rfloor, N-x)

where f_b(j, k) is the number of valid sequences in which we can get a total of k by picking from box b exactly j times. This is can be calculated by dp in \mathcal{O}(p^3 + q^3) as

f_b(j, k) = \sum_{i=1}^{S_b} f_b(j-1, k-i)

As @teja349 says here, using prefix sums it is possible to calculate the dp in \mathcal{O}(p^2 + q^2), giving a total complexity of \mathcal{O}(p^2 + q^2 + N^2).

6 Likes

Here is a code for the O(N^2) algorithm:
Solution

What really disappointed me is that there was no difference between an N^2 or N^3 solution vs a very trivial N^4 or N^5 (some even passed an N^6) dp. It kills the point of having subtask based scoring.

3 Likes

I agree with u that n^5 and n^6 shouldn’t have passed. But the time limits were such that n^4 was intended to pass. What u r saying is now basically they should have made time limits such that n^4 didn’t pass and a very hard solution was required. This would make it an entirely different hard problem but they didn’t intend to make it such a hard problem.

I beleive that the n^4 solution is around cf div1 B difficulty while n^3 would be a cf div1 C difficulty and n^2 would be cf div1 D difficulty. So prolly they intended it to be a cf div1 B difficulty problem.

Yes precisely said. The question wasn’t intended to be a very hard one and hence the constraints.

The N^3 Solution is in no way hard. It was what came naturally to me and I’m just a noob 4* :stuck_out_tongue:
I just mean to say that in a problem where N^3 and then a prefix sum (very basic trick I guess) optimized N^2 is possible, in lunchtime, being IOI style it should be the expected 100 point solution. N^4 should have got like 50 points or something, perhaps another subtask.

Also @mathecodician it is surprising that a prefix sum changes a CF Div1C to a Div1D in your opinion. (Not to mention that the problem is obviously much easier than that).

1 Like

@meooow If l is odd, then we have an option to choose which box will be the first box and you have covered that case for each of them in the equation. But if l is even, then why do we need two terms (separated by +), won’t it be redundant, or I am missing something?

@shubhambhattar you’re right, you could just say that for even l you need to compute 2 \times f_1(l/2, x) \times f_2(l/2, N-x).
But the expression for the odd l case also works for even l because then, of course, l/2 = \lfloor l/2 \rfloor = \lceil l/2 \rceil, so I didn’t put it separately.

@meooow Actually my query is why do we need two terms if they’ll both compute the same thing? Like in case where l is odd, we have the option to choose one of them as the first and that will affect the answer so we need two different terms, but in even case, we should only consider one term.

the editorial does’nt have a link to problem at top it will be great if you can fix this.

@meooow Got it. I was missing the case that we can start with both box_1 and box_2. Thus, we have two possibilities and hence you are multiplying it by 2.

@shubhambhattar, yes that’s it :slight_smile: