CareerCup

Hint: Binary Search on the Answer

1) ELP's algorithm is correct but not efficient enough, it is an O(n*n*k) algorithm.
2) ChaoSXDemon's algorithm is not enough to solve this problem, but with some modification, it did help to figure out how many pieces of cakes the largest cake will have in the optimal solution, so that it is possible to speed up ELP's algorithm to be O(n*k).

In ELP's algorithm, there is an assumption that in the optimal solution, there must be at least one cake Vx which gets no wasted at all and it can be divided into V without any volumes remained (namely, Vx % V == 0). We can prove this by assuming the opposite case in the optimal solution. If in the optimal solution, every cake has certain volumes wasted, the V we find in that case can be increased obviously, which means it is not the optimal solution. So there must be at least one cake Vx which gets no wasted at all.

ChaoSXDemon's algorithm can be used to figure out how many pieces of cakes the largest cake will have in the optimal solution. For the largest cake, it may be divided into [1...k] parts.
Here are the steps I copied from ChaoSXDemon's algorithm (assume cake0 is divided into k0 parts, and with step 5 modified):
1. Sort the input cake from largest to smallest.
2. Starting at the number of input people, guess that each person gets cake[0] / k0 units
3. Check and verify given cake[0]/k0 units can be assigned to k people
4. If step 3 worked, decrease k0 by one and assign this bigger unit and repeat step 3
5. If during step 4 any check failed, revert to previous value
5.1 if previous value can result k pieces in total (the number of guests given) for all cakes, return it as the best result
5.2 if previous value can result (k + 1) or more pieces in total for all cakes, this means even the largest cake can have some volumes remained (we can at least discard the extra one piece from the largest cake), which violates the assumption we conclude. So previous value is not the optimal solution, and we can figure out cake[0] will be divided into current value k0 parts. Since the largest cake has some volumes remained, we cannot compute the V directly by dividing V0/k0.

I will use an example to illustrate this, consider input:
vols={6, 5, 12}, k = 4

1. sort vols, vols = {12, 6, 5}
2. k0=4, V=12/4=3, total = 12/3 + 6/3 + 5/3 = 4 + 2 + 1 = 7 > 4, k0--
3. k0=3, V=12/3=4, total = 12/4 + 6/4 + 5/4 = 3 + 1 + 1 = 5 > 4, k0--
4. k0=2, V=12/2=6, total = 12/6 + 6/6 + 5/6 = 2 + 1 + 0 = 3 < 4
5. when k0=3, total = 5 = 4 + 1, so k0=3 is not in the optimal solution, k0 should be 2
So we already know in the optimal solution, the largest cake cake[0] (with volume 12) should be divided into 2 pieces. So cake[0] will be divided into 2 parts, and each part should be larger than 4 and less than 6, but we don't know the exact size of it yet since cake[0] has some volumes remained.

Since there will be at least one cake that can be divided without any waste, we need to find out that cake. Intuitively, you can use the V for k0=3 (V=4) to compute the remained volumes for each cake to find out which cake is the cake with smallest volume remained for each piece it has. When V=4,
1. for cake[1]=6, it has 2 units (6-4=2) remained, and each piece can be increased by 2.
2. for cake[2]=5, it has 1 unite remained, and each piece can be increased by 1.
3. We will pick the cake with smallest increment, and it will be the cake that gets no waste at all, and we can get V by computing V = 5 / 1 = 5 in this case.

The entire process will be O(n*k) + O(n).

Additionally, if you examine closely, you will find that to find the k0 for cake[0] from 1...k, you can use binary search to speed it up, which means this algorithm can be an O(nlgk) algorithm.

Any comment is appreciated. Thanks.

Pseudocode:
Go through each cake, dividing it up into between 1 and numCustomers slices. Then carry that slice size through the other cakes to see how much was wasted. If the wasted amount is less than the max then set it as the new max.
Ruby Code:
{{
def wasted_cake(cakes, ci, slices, numCustomers)
# if we can cut everything out of cake CI using slices, then return the waste
if slices > numCustomers then return nil end

sliceSize = cakes[ci].to_f / slices.to_f
numSlices = slices

cakes.length.times do |i|
if i == ci then next end

cake = cakes[i]
while numSlices < numCustomers && cake >= sliceSize
cake -= sliceSize
numSlices += 1
end
end

if numSlices == numCustomers then
return ($sum - sliceSize * numCustomers) else
return nil end
end

def cut_cakes(cakes, numCustomers)
$sum = 0
cakes.each do |cake|
$sum += cake
end

minWasted = Float::MAX
maxSlice = nil

cakes.sort!
cakes.length.times do |i|
(1..numCustomers).each do |slices|
wasted = wasted_cake(cakes,i,slices,numCustomers)
if nil == wasted then next end

if wasted < minWasted then
minWasted = wasted
maxSlice = cakes[i]/slices.to_f
else
break
end
end
end

return maxSlice
end

puts cut_cakes([1,2,300],5)
puts cut_cakes([1,2,3],1)
puts cut_cakes([1,2,3],2)
puts cut_cakes([1,2,3],3)
puts cut_cakes([1,2,3],4)
puts cut_cakes([1,2,3],5)
puts cut_cakes([1,2,3],6)
}}

60.0
3.0
2.0
1.5
1.0
1.0
1.0

1. Sort the input cake from largest to smallest.
2. Starting at the number of input people, guess that each person gets cake[0] / k units
3. Check and verify given cake[0]/k units can be assigned to k people
4. If step 3 worked, decrease k by one and assign this bigger unit and repeat step 3
5. If during step 4 any check failed, revert to previous value and return the best result

The time complexity if O(kN) where k is number of people and N is the number of cakes. So if k = N or larger then it's basically O(N^2)

float calculateWaste(float* cakeUnits, int length, float piece, int k){
	int peopleLeft = k;
	float waste = 0;
	for(int i=0; i<length; i++){
		if(peopleLeft == 0){
			waste += cakeUnits[i];
		}else{
			if(cakeUnits[i] < piece) return -1;
			int maxPeople = (int)floor(cakeUnits[i]/piece);
			maxPeople = maxPeople > peopleLeft ? peopleLeft : maxPeople;
			waste += cakeUnits[i] - piece*maxPeople;
			peopleLeft -= maxPeople;
		}
	}
	return waste;
}

float* assignCake(float* cakeUnits, int length, int k){
	float* result = new float[2];
	int totalPeople = k;
	result[0] = cakeUnits[0] / k;
	result[1] = calculateWaste(cakeUnits, length, result[0], totalPeople);
	float prevUnit = result[0];
	float prevWaste = result[1];
	while(result[1] > 0){
		printf("Unit: %3.4f Wasted: %3.4f\n", result[0], result[1]);
		k--;
		prevUnit = result[0];
		prevWaste = result[1];
		result[0] = cakeUnits[0] / k;
		result[1] = calculateWaste(cakeUnits, length, result[0], totalPeople);
	}
	result[0] = prevUnit;
	result[1] = prevWaste;
	return result;
}

int main(int argc, char** argv){

	float cakes[] = {4, 4, 2};
	int length = sizeof(cakes) / sizeof(cakes[0]);
	float* result = assignCake(cakes, length, 6);

	printf("%3.4f per person wasting %3.4f units\n", result[0], result[1]);

	system("PAUSE");
	return 0;
}

Outputs:

Unit: 0.6667 Wasted: 6.0000
Unit: 0.8000 Wasted: 5.2000
Unit: 1.0000 Wasted: 4.0000
Unit: 1.3333 Wasted: 2.0000
1.3333 per person wasting 2.0000 units
Press any key to continue . . .

Objective:
1. Minimize the total waste by volume (not by flavor)
2. Maximize distribution (so maximum number of people must be served)

Constraints:
1. A person cannot have more than one flavor
2. More than one flavor cannot be distributed to a person
3. One flavor can be distributed to more than one person
4. Per person cake share V lies between Vmin and Vmax

Logic:
To minimize the waste by volume, the per person share must be adjusted to achieve the minimal waste.

Arrange the cakes in descending order Vmax to Vmin
	Setup a cake distribution list: KDistribList[]
	Setup the waste basket: wasteBasket
	For each cake in the list:
		Check if KDistribList size = K { 
			If YES, then add the remaining cakes to wasteBasket
			Exit; distribution is complete 
		}
		Count the number of times V goes into Vcake
		Throw the remainder into waste basket { wasteBasket = wasteBasket+ Vcake%V }
		If (Vcake/V <= (K - KDistribList.Size) { //Meaning there are spaces left
			add the Vs to distribution list KDistribList[] = [The Vs extracted from Vcake]			
		} else if (Vcake/V > (K - KDistribList.Size) { 
			//Meaning there are more pieces than spaces left
			add as much Vs to distribution list KDistribList[] that will fit
			add the remaining to wasteBasket { wasteBasket = wasteBasket+ Vcake%V }
		}

The above algorithm assumes that K => N, there are either same or more people than cakes. If there are more cakes than people (N > K), then the above algorithm still applies, but there will always be more cakes wasted in this scenario, but we will maximize the distribution (meaning every person will get a piece guaranteed.)

Also, since minimizing waste is an objective, the way to do so is to play around with the choice of V to see what yields the minimum wasteBasket value. So we will need to repeat this algorithm for different choices of V and check for wasteBasket minima.

what say?

Given N cakes and K people with N >= K
Find the (N - K + 1)th volume cake in asc order.
This can be done in O(N) given that input is not sorted, or O(logN) if it is sorted.

1) Take the volume of the smallest cake Vsmallest
2) Divide all the cakes into slices of of size Vslice = Vsmallest
4) Obtain the number of slices Nslices you would get if you divided all the cakes into slices of size Vslice
3) If Nslice is less than the number of people, then dived the smallest cake into to slices and set Vslice into Vsmallest/2
4) Repeat until the number of slices is greater than or equal to the number of people
5) If Nslice was to large (to many slices per person to start) then elliminate the smallest cake and start with the second largest cake

I assume V1,V2, .... Vn are sorted.

slicesPerCustomer= f(N)

int f(i){
   if i=1 then return V1/K else
   if Vi / K > f(i-1) then return Vi / K else return f(i-1)
}

asume the v1, v2.....vn are all integers

bindary search v,

vmax = max (v1,v2,...vn);
vmin = min (v1, v2....vn);

while (vmin<vmax)
{
v = (vmin+vmax)/2;
if ( [v1 v2.....vn] has k times v ) then vmin = v;
else vmax = v;
}

return vmin;


time complexity: O (n log|vmax-vmin| )
example: 10000, 1, 1, ....3, 1... k=2, v=5000
8,7,6,3,1 k=3, v = 4
......

Convert it to a mathematical equation and use Newton iteration method to get the root.
The function is:
f(v)=sum{lowerBound(vi/v)}-k.
Here is the code:

/**
 * 
 * @param vs volume of cakes
 * @param k number of guests 
 */
	public double splitCake(double[] vs, int k){
		double lv=1;
		double rv=0;
		for(double d:vs)
			rv+=d;
		
		//newton method to find the root
		while(rv-lv>0.0001){
			double middle=(lv+rv)/2;
			double loss=lossFunc(vs, k, middle);
			if(loss>0)
				lv=middle;
			else if(loss<0)
				rv=middle;
			else{
				lv=middle;
				break;
			}
		}
		
		//System.out.println(lv);
		return lv;
	}
	
/**
 * \sum_{i=1}^n floor(v_i/v) - k
 * @param vs
 * @param k
 * @param v
 * @return
 */
	protected int lossFunc(double[] vs, int k, double v){
		int num=0;
		for(int i=0; i<vs.length; i++)
			num+=((int)(vs[i]/v));
		return num-k;
	}

Model it as a mathematical function and use Newton iteration to find the root.
f(v)=sum (lowerBound(vi/v))

Here is the code:

/**
 * 
 * @param vs volume of cakes
 * @param k number of guests 
 */
	public double splitCake(double[] vs, int k){
		double lv=1;
		double rv=0;
		for(double d:vs)
			rv+=d;
		
		//newton method to find the root
		while(rv-lv>0.0001){
			double middle=(lv+rv)/2;
			double loss=lossFunc(vs, k, middle);
			if(loss>0)
				lv=middle;
			else if(loss<0)
				rv=middle;
			else{
				lv=middle;
				break;
			}
		}
		
		//System.out.println(lv);
		return lv;
	}
	
/**
 * \sum_{i=1}^n floor(v_i/v) - k
 * @param vs
 * @param k
 * @param v
 * @return
 */
	protected int lossFunc(double[] vs, int k, double v){
		int num=0;
		for(int i=0; i<vs.length; i++)
			num+=((int)(vs[i]/v));
		return num-k;
	}

Binary search over V.

1. Assume the cakes are already sorted by volume, so V1 is smallest and Vn is largest
2. First try setting V=V1 and see if that works (usually doesn't)
3. Now, check the wastage from each cake, call them W1...Wn
4. Imagine we want to reduce V by as little as possible to produce 1 additional piece
5. We can do so by picking the cake with the most wastage, and setting V such that we can produce that 1 additional piece from this cake. If there's a tie for most wastage, use the cake with largest volume.
6. Repeat this process until we have enough pieces

For example, assume the volumes are {10, 14, 16, 22, 30} and K=10 people.
First set V=10. That would produce {1, 1, 1, 2, 3} pieces, or 8 total.
Calculate wastage as {0, 4, 6, 2, 0}.
We realize that the 3rd cake has the most wastage (6), so we should try to produce the additional piece from this cake. To produce 2 pieces from cake 3, V should be 8.

Now we can produce {1, 1, 2, 2, 3} pieces, or 9 total.
Calculate wastage as {2, 6, 0, 6, 6}.
So we should use last cake to produce the additional piece, and set V=30/4 or 7.5
Now we can produce {1, 1, 2, 2, 4}, or 10 pieces.

Sorry I don't have proof that this greedy algorithm works, nor even 100% sure it works.

Let k be the total number of people, going to have the cake.
-> First take each cake say v1, divide it with k, and store it into float, if the value is not a perfect integer.
Ex: float f = v1/k;
-> now take that float value and assign it to integer using math.floor. which will round to the perfect integer.
-> Now subtract this integer from float, which will give minimum wastage in cake.
-> So total number of cakes x float values gives minimum wastage.
Ex: Let volume of cake = 15 kg.
People = 4.
float f = 15/4; f = 3.75
int perHead = Math.floor(3.75); perHead = 3;
float wastage = f - perHead; wastage = 0.75;
So, total wastage = wastage * total number of cakes.

Imagine there are 2 cakes and you are the second person to choose a piece. Since person 1 is sure to claim the biggest cake, you have the choice to either pick the smaller cake or half of the bigger cake.
Behind you is your friend who also wants some cake, assuming you chose to split the larger cake, then your friend can either claim the smaller cake or split the bigger cake with the 3 of you

So this seems like a greedy algorithm,

(defn maxPos [ls] (.indexOf ls (apply max ls)))

(defn distributeCake [cakeVol people]
           (loop [claims (vec (repeat (count cakeVol) 0))
                  peopleLeft people]
             (if (= 0 peopleLeft) claims
               (let [maxPos (maxPos (map #(/ %1 (inc %2)) cakeVol claims)) ]
                 (recur (assoc claims maxPos (inc (claims maxPos))) (dec peopleLeft))))))

(distributeCake [32 42 52 133] 55)
=> [6 9 11 29]

(apply min (map / [32 42 52 133] (distributeCake [32 42 52 133] 55)))
=> 133/29  , or the smallest volume

edit: I guess I didn't explain the last step. Once you optimize for the solution where not everyone recieves the same volume as an intermediate step, you can find the volume everyone gets by dividing each volume by how many people and returning the minimum.

Does this not solve this problem:

1. Obtain the GCD of the volumes of the cake.
2. Divide all the cakes with this volume.
3. Distribute those pieces equally among the K people.

we will waste (K-1)GCD_Vol in this way.

Does this not solve this problem:

1. Obtain the GCD of the volumes of the cake.
2. Divide all the cakes with this volume.
3. Distribute those pieces equally among the K people.

we will waste (K-1)GCD_Vol in this way.