**My solution for Problem "[problem:1348E]" [submission: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 `X`th 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 + 1`th 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 `X`th shrub (passed onto the `X + 1`th shrub), and the total number of berries in the `X + 1`th 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 + 1`th 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];↵
}↵
~~~~~↵
↵
===================================================================↵
↵
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 `X`th 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 + 1`th 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 `X`th shrub (passed onto the `X + 1`th shrub), and the total number of berries in the `X + 1`th 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 + 1`th 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];↵
}↵
~~~~~↵
↵
