Greedy Algorithm Problem: Geek collects the balls

 I haven't posted for a while, 8 months to be precise. I am practicing DSA nowadays after a lot of soul searching. My plans have taken a left turn very wildly. Hope I achieve my goals.... I do have backup plans so hope that it keeps me in safe position

Anyways, I came upon this question in Geeks for Geeks portal. Its a medium-level problem. So I found that ,for this question there were no articles or videos giving the correct solution that works in GFG portal and successfully runs all testcases. There is a GFG video but while its core logic is correct, it doesn't take into account all the different possibilities of solving each testcase so their code doesn't work

Here is the link to the GFG video:

Video link for problem

Problem statement:

There are two parallel roads, each containing N and M buckets, respectively. Each bucket may contain some balls. The balls in first road are given in an array a and balls in the second road in an array b. The buckets on both roads are kept in such a way that they are sorted according to the number of balls in them. Geek starts from the end of the road which has the bucket with a lower number of balls(i.e. if buckets are sorted in increasing order, then geek will start from the left side of the road).
Geek can change the road only at a point of intersection i.e. a point where buckets have the same number of balls on two roads. Help Geek collect the maximum number of balls.

Explaination:

There are two arrays a and b which have N and M values respectively. They are both sorted in increasing order. If at any point in array a ,there is a element with same value at any point in array b then at this point we can switch our iteration of array. Basically we have to maximize sum of elements taken from both arrays in a linear manner such that its maximum using this condition.

So if you observe that there is no way to actually determine which array/road will have the maximum sum till the first intersection point other to calculate it using two variables. So we do that. And how do we iterate over both arrays, We use the merge technique in merge sort algorithm. We maintain two pointers i and j and increment i when a[i]<b[j] and j when a[i]>b[j]. We can't do the opposite as if one element is greater than other element then that means all the elements to the right of the greater element are greater than it so this will produce a incorrect merge. We declare an array R[2] representing both sums

When we increment i then we add that element a[i] to R[0] and for b[j] we add it to R[1]. Note if iterate in this way and if there is a intersection point then i and j will definitely meet as they are in sorted order. During this condition we maintain two counts ca and cb . Then we consider the case when there are duplicates of intersection point. I will explain how we will add it later but for now we just count how many duplicates are there in ca and cb respectively.

Then we have think that basically we have to maximize our sum for each road. So to do that each road's sum can be affected by two outcomes. For eg: for road 0 if we start from beginning then we just iterate over all the duplicate intersection points and add them to R[0] then another possibility is that we came adding from road 1 and we iterate over all duplicates and add them to R[1] then we switch roads at the first intersection point element ,then we add all its duplicates too. Similarly we do for road1

There is one more case that in some testcases if ca>1 and cb>1 then its possible that we get the maximum sum by going shift roadings at first intersection point element and then going through all duplicates of that road and then switching back to the original road and iterating from there we get the sum .So we need to consider this.

This may happen when there are large no of duplicates in one array whose value  is sufficiently large in the array. This case is not possible if any intersection point duplicate is none as we can't turn back

a example test case for above condition is:

4 5 6 7 8 8 9

1 1 8 8 8 8 8

 Code:

int R[] = {0, 0};
    int i = 0, j = 0;
    while (i < N && j < M) {
        if (a[i] < b[j]) R[0] += a[i++];
        else if (a[i] > b[j]) R[1] += b[j++];
        else {
            int v = a[i], ca = 0, cb = 0;
            while (i < N && a[i] == v) 
            {ca++; i++;}
            while (j < M && b[j] == v)
            {cb++; j++;}
          
            int r0 = Math.max(R[0] + ca*v, R[1] + (ca+cb-1)*v);
            int r1 = Math.max(R[1] + cb*v, R[0] + (ca+cb-1)*v);
            
            if (ca > 1 && cb > 1) {
                r0 = Math.max(r0, R[0] + (ca+cb-2)*v);
                r1 = Math.max(r1, R[1] + (ca+cb-2)*v);
            }
            
            R[0] = r0; R[1] = r1;
        }
    }
    while (i < N) R[0] += a[i++];
    while (j < M) R[1] += b[j++];
    return Math.max(R[0], R[1]);

Note:This isn't my code originally ,I modified it so it could work in java

So why does this code works? while the one in GFG Video doesn't , its because they don't consider all the possible ways the roads can be traversed. They even make the sum zero(here R[0] and R[1]), while sum is an important variable that represents the path through which they have travelled(while one sum can be achieved through many ways ,here the elements and no of elements are fixed). Here we consider all possibilities .