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

Vineyard

Please answer, if any doubts write in comments. – Vineyard

What is the issue ? Can you show some bit of code because it's hard to understand where you're stuck. – Muffle

How big is the array? How big can the numbers get? – Kaiserism

I don't know how to proceed. It is equivalent of this problem: codechef.com/DI15R080/problems/MINMAXTF – Vineyard

The question you have linked to, is different. It wants to find a way to divide the array such that the subset with maximum sum is minimum. If you still can't solve it, edit the question. – Kaiserism

Answer 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).

Kaiserism

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

It is still O(nlogn). – Syringe

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

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. – Kaiserism

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

Yes, I would say the complexity is bounded by O(n log(k * n)) = O(n log(n) + n log(k)) where k is the largest number in the array. – Suction

Answer 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)).

Kemppe

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 – Likable

Answer 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/

Runnels

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

Answer 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)

Caprifoliaceous

Answer 5

This can be solved using dynamic programming:

Lets define first DP[n,m] to be the optimal solution for dividing the subarray C[1..n] into m parts. Where each part has at least one element.

DP[n,1] = sum(C1:Cn)
DP[n,n] = max(C1:Cn)
DP[n,m] = min( sum(Ck:Cn) + DP[k-1,m-1] )
          where k goes from m to n

Explanation:
DP[n,1] - Base case, when the number of partitions is 1 there is only one way - all elements left (from 1 to n).
DP[n,n] - Whenever the number of partitions are equal to the number of elements left in the array there is only one legal way to divide it - each element in a different partition, so the partition with the maximum sum is the maximum element in the array.
DP[n,m] - This is the main solution. We don't know exactly how many elements will be our next partition, so we need to go over all options and get the minimum from it.

Syringe

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). – Kaiserism

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. – Syringe

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

Answer 6

The division is just a brute force problem. You have to focus to the function to minimize. So what you have to minimize is the deviation from the average.

int sum_arr(int *arr,int size)
{
    int res=0;
    while (size-->0)
       res+=*arr++;
   return res;
}
int   minimize( const int *array, int size)
{
    int i,j,cur_i;
    double dev, cur_min,avg=(double)sum_arr(array,size)/size;

    for (i=1;i<size-1;i++)
      {
         dev=abs(avg-sum_arr(array,i));
         dev+=abs(avg-sum_arr(array+i,size-i);
         if (dev<cur_min)
         {
              cur_min=dev;
               cur_i=i;
         }
      }
     return cur_i;
}

A simple code would be:(Not tested)

Markley

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

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) – Markley

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

Answer 7

// This code works only if you have to find in a contiguous segment

bool isPossible(vector<int>& nums, int mid, int k) {
  int n = nums.size(), Count = 1, Sum = 0;
  for(int i = 0; i < n; i++) {
    if(nums[i] > mid)  return false;
    Sum += nums[i];
    if(Sum > mid) {
      Count++;
      Sum = nums[i]
    }
  }
  return Count <= k;
}
int Func(vector<int>& nums, int k) {
  int n = nums.size();
  int low = 0, high = accumulate(nums.begin(), nums.end(), 0);
  while(low <= high) {
    int mid = (low + high) / 2;
    if(isPossible(nums, mid, k)) {
      ans = mid;
      high = mid - 1;
    }  else  {
      low = mid + 1;
    }
  }
  return ans;
}

Spiritualty

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Vitus