My solution for Problem "1348E - Phoenix and Berries" 78860291

Let, DP[X][R]= Number of baskets that can be completely filled using the shrubs indexed from X to N — 1 (0 based indexing), given that we have R number of red berries to start with.

Note that for every shrub, if:-

• the total number of berries a[X] + b[X] (both red and blue) in a shrub is greater than or equal to K,

• and there are both red and blue berries in the shrub.

Then, we'll fill one basket completely, with these K berries and pass on the remaining berries to the next shrub. There can be at most K - 1 different ways in which we fill a basket containing both red and blue berries from the same shrub.

For example if the Xth shrub contains 2 red berries and 10 blue berries and K = 4, then the possible combinations are:-

RED    BLUE
1      3
2      2

(All the combinations with either zero red berries or zero blue berries will be taken care of in the last part)

Whenever, the count of any of these passed on red and blue berries becomes greater than or equal to K, we immediately fill a basket with it and pass on the remaining (R % K, B % K) berries to the next shrub.

Important observation:

It can be observed that if we know the number of red berries that are being passed on to the X + 1th shrub, we also know the exact number of blue berries that are being passed along with those red berries. Therefore we do not need to keep track of number of blue berries passed, i.e, we do not need to consider B as another dimension in states of DP.

Number of blue berries passed = (Sum of total number of berries in each shrub starting from 1st shrub ending at Xth shrub — Number of red berries R passed onto (X + 1)th shrub) % K

If we receive R red berries and B blue berries from the Xth shrub (passed onto the X + 1th shrub), and the total number of berries in the X + 1th shrub is greater than or equal to K, i.e., a[X] + b[X] >= K, then we fill exactly 1 basket with these K berries. After selecting a total of K berries (all possible different combinations of red and blue), from X + 1th shrub, we'll add the remaining red and blue berries to R and B and find mod K.

The number of red berries R and blue berries B is always stored as R % K and B % K, because if we have at least K red berries or/and K blue berries, we can completely fill (R / K) + (B / K) baskets.

Another Case

If the number of berries in a shrub is less than K, then we cannot fill a basket completely, using berries, entirely from this particular shrub, therefore we'll have to add the number of red and blue berries in this shrub to R and B respectively, fill R / K and B / K baskets completely, and pass on R % K and B % K red and blue berries respectively, to the next shrub.

We solve the above case even when a[X] + b[X] >= K, to consider the combination :-

RED   BLUE
0     K
K     0

and pass on the remaining red and blue berries to the next shrub. :)

We have to find DP[0][0]

long long dp(int x, int r, int g)  // r red berries and g blue berries
{
	if(x == n)    //terminating condition
		return 0;
	if(DP[x][r] != -1)    //value already found before
		return DP[x][r];
	DP[x][r] = 0;
	int rem_r, rem_g;
	if(a[x] + b[x] >= k)
	{
                // considering all possible combinations of red and blue berries to completely fill a basket
		for(int i = 1; i < min(a[x] + 1, k); i++)
		{
			if(i <= a[x] && (k - i) <= b[x])
			{
				rem_r = r + a[x] - i;
				rem_g = g + b[x] - (k - i);
				DP[x][r] = max(DP[x][r], 1 + (rem_r / k) + (rem_g / k) + dp(x + 1, rem_r % k, rem_g % k)); 
			}
		}
	}
        // passing onto the next shrub, the total red and blue berries from this shrub along with the previous red and blue berries passed onto this shrub
	rem_r = r + a[x];
	rem_g = g + b[x];
	DP[x][r] = max(DP[x][r], (rem_r / k) + (rem_g / k) + dp(x + 1, rem_r % k, rem_g % k));
	return DP[x][r];
}