Divide array into k contiguos partitions such that sum of maximum partition is minimum

Question

Here maximum sum subset is one of k subsets that give maximum sum e.g: arr = [10,5,3,7] and k = 2 possible ways to divide arr in k subsets is

  {10,[5,3,7]},{[10,5],[3,7},{[10,5,3],7}

and

{[10,5],[3,7} is the optimal one.

Edit: it is equivalent of https://www.codechef.com/DI15R080/problems/MINMAXTF

Solution 1

Assume you know the answer is x which means sum of the maximum subset is equal to x. You can verify this assumption by a greedy algorithm O(n). (Traverse the array from left to right and pick items until the sum of that subset is lower than x). Now you can binary search on x and find the minimum value for x. The complexity of this algorithm is O(nlogn).

Solution 2

This is an example of binary searching the sample space.

int min_max_sum(std::vector<int> & a, int K) {        

    int n = a.size();    
    long long high = 0, low = 0, mid = 0;

    for (int i = 0; i < n; ++i) {
        high += a[i];
        low = max(a[i], low);
    }

    while(low <= high) {
        mid = (low+high)/2;

        long long part_sum = 0;
        int parts = 1;
        for (int i = 0; i < n; ++i) {
            if (part_sum + a[i] > mid) {
                part_sum = 0;
                parts++;
            } else {
                part_sum += a[i];
            }
        }

        // if no. of parts in less than (or equal to) K then mid needs to (,or can) be more constrained by reducing upper limit
        if (parts <= K) {
            high = mid - 1;
        } else { 
            low = mid + 1;
        }
    }

    return mid;
}

complexity : O(n log(sum(array))).

But since logrithms are exponentially better than linears, this complexity is quite good.

worst case complexity : O(n log(INT_MAX * n))=O(32 n +n log(n))=O(n log(n)).

Solution 3

Lets start with an example. Suppose N=5 and k=3(assuming that there will be three parts after division).Let our array be {1,2,8,4,9}. We can observe that if k was equal to 1, then sum of maximum partition would be sum(all array elements) i.e., 24 and if k=5, then sum of maximum partition would be max(all array elements) i.e, 9. Now, we can observe that as k increases, sum of maximum partition's minimum value decreases. Our algorithm will take the help of binary search in doing so. But how to do it????? By looking at the question-we can see, we have to find the minimum of maximum which arouses the feeling of problems like- "FFFFTTTTTTTT" where we have to find the first T. We are going to do exactly the same stuff but will take the help of a function in doing so.(Look at the code and answer from here, parallelly)..The helper function will find the value of K when the minimum sum of maximum partition is provided.We will initialize low=max(all array elements),here low=9 and high=sum(all array elements)i.e.,high=24.Therefore,mid=16,So,for min_max_dist=16,our helper function will return the number of k required.If number of k>K,it means that our min_max_dist can accommodate more values in it.So,we will increment our low value to mid+1 and if number of k<=K, it means that in less number of partition,we can achieve that min_max_dist,,but we can do more partition and therefore we can decrease high value to mid.So,our code will execute on our example in following way:-

    low           high               mid       number_of_k
    9             24                 16         9
    9             16                 12         2
    9             12                 10         4
    11            12                 11         3

and finally our result->low=11 will be returned..

    #include <bits/stdc++.h>
    #define ll long long int
    using namespace std;

    ll number_of_k(ll arr[],ll n,ll minimum_max__dist){
       ll sum=0;
       ll k=1;
       for(ll i=0;i<n;i++){
          sum+=arr[i];
         if(sum > minimum_max__dist){
           sum=arr[i];
            k++;
          }
      }
    return k;
   }

    ll Max(ll arr[], ll n)
    {
       ll max1 = -1;
       for (ll i = 0; i < n; i++)
          if (arr[i] > max1)
              max1 = arr[i];
      return max1;
    }

    ll Sum(ll arr[], ll n)
    {
      ll sum = 0;
       for (int i = 0; i < n; i++)
       sum += arr[i];
       return sum;
     }

       ll min_max_bin_search(ll arr[],ll n,ll k){
         ll low=Max(arr,n);
         ll high=Sum(arr,n);
         ll mid;
while(low<high){
     mid=low+(high-low)/2;
    if(number_of_k(arr,n,mid)<=k)
       high=mid;
    else
        low=mid+1;
     }
  return low;
  }


 int main()
 {
      ll n,k;
       cin>>n>>k;
       ll arr[n];
       for(ll i=0;i<n;i++)cin>>arr[i];
       cout<<min_max_bin_search(arr,n,k)<<endl;

   return 0;
 }

Time complexity of this algorithm is->O(nlogn)

Read this article on Binary Search-> https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/ and Solve this problem-> http://www.spoj.com/problems/AGGRCOW/

Solution 4

You can find a good writeup about dynamic programming based solution here: https://www.geeksforgeeks.org/painters-partition-problem/ and It's complexity is O(k*N^2).

To get a better solution, you can use the binary search method as suggested by others. You can find a more detailed solution that uses binary search here: https://www.geeksforgeeks.org/painters-partition-problem-set-2/ and it's complexity is O(NlogN)

View more solutions

Comments

[Saeid]

This algorithm will work but not for this problem since N and K are 10^5 and complexity of this algorithm is O(N*K).

[A. Sarid]

First, the OP didn't say anything about the sizes of N and K and complexity. Second, it doesn't mean it won't work, it might not be the most efficient solution, but it works.

[A. Sarid]

I don't think the division is just a brute force problem.

[v78]

hey , your complexity is O( n*log(sum(array)) ). right?

[A. Sarid]

It is still O(nlogn).

[A. Sarid]

@sudomakeinstall2 Nice solution. Can you please add more explanation why this greedy works?

[Saeid]

Sure. Think about it this way: you have some bags that all have x capacity. You want to put the items (from left to right) in these bags, and you want to minimize the number of bags. A greedy approach will work on this problem. You can easily see if the current bag has enough capacity for the current item you should put it in or else it may increase the number of bags required. You can reduce the greedy part of the above problem to this bags problem.

[jurhas]

It is not brute force but the smallest probleme. if you want a linear solution and memory is not a problem, create other two arrays with the partial sum. You compute once the whole sum, and the sum of the i element is gave by sum(i)=sum(i-1)+i mehanweile the remaining sum is gave by sum(n-i)=sum(n-i)-i . complessity O(3*n)== O(n)

[Saeid]

I can't find the variable k in your solution.

[Chao Xu]

@A.Sarid it is no O(n log n). sum(array) can be way larger than n.

[Xinyi Li]

It should be max(sum(Ck:Cn),DP[k-1,m-1]) instead of sum(Ck:Cn) + DP[k-1,m-1] .

[Dhanendra]

Your explanation is a bit broken but it really helped me to get what's happening there, thanks!

[Bhaskar13]

The part_sum =0 should be corrected as part_sum=a[i] inside for loop's if conditional. Test for arr=[1 3 2 4 10 8 4 2 5 3] and K = 4, answer should be 12