Problem Link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2408

Note:

After reading the problem statement, most of our instant intuition will go with the Dynamic Programming approach understandably to solve this problem. Yes, that is obviously correct but another approach would be Binary Search which is unlikely to come to our mind at first. But Binary Search approach is more efficient in solving this problem compared to the Dynamic approach in terms of time and space complexity. Also, once you understand this approach, it’s easier to implement than the Dynamic one!

Here, the non-breaking property of the input array, that is you’ll have to maintain the serial of the containers in the conveyor belt (array). So we can choose to guess the minimal capacity of the container by calculating what would be the initialization of left and right in code. This initialization is an important step in this problem. In binary search, if the problem is not so straightforward as this one, initializing the left and right correctly is the first big step.

binarySearch():

Here, as I will guess minimum capacity, so the left limit would be the minimum possible value of the answer, thus the maximum element of the array. And the right limit would be the maximum possible value of the answer, the sum of all elements of the array.

Then we would run binary search within this range and would call the checkM function whether the mid satisfies the given limit of containers – m or not.

-If yes, then that’s a probable answer so we will keep that in our next iteration, and since in the next iteration we can find a lesser capacity amount than this one, we would update mid=right.

-If not, that means, our mid (the chosen probable capacity) is lower than any probable answer as it is requiring more containers than m. So we will update left=mid+1.

And in the end, if the condition left<right is not met, the code will exit the while loop, and now we can return left or right, that does not matter in this case(ultimately left and right would be equal while exiting the loop) due to the condition set for the loop and updating mid the way I did. In my code, I have written right as it seems easier to me to understand.

checkM():

This function is pretty straightforward. If with our predicted possible value (mid), all the elements of the array can be distributed in exactly m containers then it returns true, if it requires more than m containers we break immediately and return false.

I hope solving these types of problems using Binary search would increase the range of our intuition to solve a problem with an efficient and easier approach – Binary search.

Code:

#include <bits/stdc++.h>

using namespace std;

bool checkM(vector<int>& v, int m, int probableCap)
{
    int sz=v.size();
    int total=0, cnt=1;
    for(int i=0; i<sz; i++)
    {
        total+=v[i];
        if(total>probableCap)
        {
            total=v[i];
            cnt++;
            if(cnt>m) return 0;
        }
    }
    return 1;
}

int binarySearch(vector<int>& v, int left, int right, int m)
{
    int mid;
    while(left<right)
    {
        mid=left+(right-left)/2;
        if(checkM(v, m, mid)) right=mid;
        else left=mid+1;
    }
    return right;
}
int main()
{
    int n, m;
    while(cin>>n>>m)
    {
        vector<int> v;
        int sum=0, maxx_element=-1, x;
        for(int i=0; i<n; i++)
        {
            cin>>x;
            v.push_back(x);
            sum+=x;
            maxx_element=max(x,maxx_element);
        }
        int left=maxx_element, right=sum;
        cout<< binarySearch(v,left,right,m)<<endl;
    }
    return 0;
}