Fair workload

FairWorkload  
Used as: Division Two - Level Three:

Value	1000
Submission Rate	19 / 299 (6.35%)
Success Rate	11 / 19 (57.89%)
High Score	. for 914.74 points (8 mins 50 secs)
Average Score	721.75 (for 11 correct submissions)

Used as: Division One - Level Two:

Value	500
Submission Rate	147 / 184 (79.89%)
Success Rate	132 / 147 (89.80%)
High Score	antimatter for 487.35 points (4 mins 36 secs)
Average Score	348.60 (for 132 correct submissions)

This is a very nice question, which can be solved in a couple ways. But first and foremost lets try to understand what the problem is asking us to do.
We are given a number of filing cabinets where each cabinet contains some number of folders. We are also given the number of available workers. What we would like to do is to partition the cabinets amongst the N workers in a such a way that
    (1) each worker works with adjacent cabinets
    (2) number of folders that each worker has to work on (cabinets can not be shared) is spread as evenly as possible.
We are to return the largest partition in our most evenly spread arrangement.

As an example: if we are given 9 cabinets:

        10 20 30 40 50 60 70 80 90

and we have 3 workers, the best solution would be:

        10 20 30 40 50 | 60 70 | 80 90

And the largest partition in this case is 170 (80+90)

Constraints:
    The number of cabinets we will work with is [2..15]
    The max number of workers we will have is [2..15]

This is a nutshell is a problem of generating all N (number of workers) subsets of the cabinets such that the following is always true:

        (1) A subset must contain only adjacent cabinets
        (2) Cabinets can not repeat
        (3) Cabinets can not be omitted: The total number of cabinets in all subsets gives
        us the total set back
        (4) Subsets cannot be empty

Here are a couple approaches to this problem:

(1) First we can generate all the possible valid subsets as follows:
We set a globalMax to be the total number of folders.
We start with the full set of cabinets and we divide this set into two subsets LeftSet and RightSet.
We then take the RightSet and again divide it by into two sets.
We repeat this process until we have generated the same number of sets as we have workers.
For each subset that we generate in this manner we calcuate the LocalMax.
We then compare this LocalMax to the GlobalMax and if GlobalMax is greater than the LocalMax then we set the new GlobalMax to be the value of the LocalMax.
Basically we have found at this point a solution that distributes the folders better.
Once we go through all these sets we return the current GlobalMax.

This can be done in a recursive manner as follows (after lanenal's solution from room 2)

   int globalMax;
   public int getMostWork(int[] f, int w)
   {
      for(int i=0; i<f.length; i++) globalMax += f[i];
      genSubsets(f, -1, w, 0);
      return globalMax;
   }
   void genSubsets(int[] f, int from, int w, int localMax)
   {
      int sum = 0;
      // Final subset
      if(w==1)
      {
        // get the folders for this subset
      for( int i=from+1; i<=f.length-w; i++) sum += f[i];
         // is this the most folders for the current subsets?
         // If yes then update the localMax
         if(localMax<sum) localMax = sum;
         // Is our localMax less than (better) the globalMax
         if(localMax < globalMax) globalMax = localMax;
         return;
      }

      for( int i=from+1; i<=f.length-w; i++)
      {
         // the LeftSubset folders sum
      sum += f[i];
      // Generate the RightSubset by dividing the current
      // subset in two with the pivot at i.
      // Propagate localMax to the RightSubset
      genSubsets(f, i, w-1, sum>localMax?sum:localMax);
      }
   }

(2) Application of Binary Search. For a non-recursive example of this approach please look at Ukraine's code in room 1.

(3) We can also use Dynamic Programming. I will leave this as an exercise to the reader.


----------------------------------------------code------------------------------------------------------------------------------
#include<stdio.h>
#include<bits/stdc++.h>
typedef int lli;
using namespace std;

int getMostWork(vector <int> v, int m)
{

int l=0,r=0;
int size=v.size();
for(int i=0;i<size;i++)
{
r+=v[i];
}

for(int i=0;i<size;i++)
{
l=max(l,v[i]);
}
 
int ret=r;
int ff=0;
while(l<=r)
 {
  if(l==r) ff=1;
   int mid=(l+r)/2;
   int cov=1;
   int sum=0;
   for(int i=0;i<size;i++)
    {
    if(sum+v[i]>mid)
     {
      cov++;
      sum=v[i];
 }
 else
 {
   sum+=v[i];
 }
     
}
 
//  cout<<" l "<<l<<" "<<r<<"  count "<<cov<<" mid "<<mid<<endl;
if(cov<=m)
 {
  //if(cov==m)
   ret=min(ret,mid);
   r=mid;
 }
 else
 {
  l=mid+1;
 }
 if(ff==1) break;
 }
 return ret;

}



int arr[1000000];
int main()
{
int t;
cin>>t;
while(t--)
 {
  int n,m;
  cin>>n>>m;
  vector<int> v;
  for(int i=0;i<n;i++)
    {
   int a;
    cin>>a;
    v.push_back(a);
  }
  
  int ans=getMostWork(v,m);
   cout<<ans<<endl;
 }


}