TopCoder problem "CakesEqualization" used in SRM 421 (Division I Level Two)



Problem Statement

    

You are organizing a party and have bought several pieces of cake for it. The weights of these pieces are given in the int[] weights, where each element corresponds to the weight of a single piece.

After looking at the pieces more carefully, you became worried that they have different weights and decided to make these differences smaller. In order to do this, you can make at most maxCuts cuts. With each cut you can choose one of the pieces you currently have and divide it into two distinct pieces. Note that each of these two pieces can be chosen again when making subsequent cuts.

Your goal is to produce cuts in such way that the difference between the maximal and the minimal pieces' weights becomes as small as possible. Find the best way of making cuts and return the optimal difference.

 

Definition

    
Class:CakesEqualization
Method:fairDivision
Parameters:int[], int
Returns:double
Method signature:double fairDivision(int[] weights, int maxCuts)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-weights will contain between 1 and 50 elements, inclusive.
-Each element of weights will be between 1 and 1,000,000,000, inclusive.
-maxCuts will be between 1 and 100,000, inclusive.
 

Examples

0)
    
{1, 3}
2
Returns: 0.0
First, choose the piece with weight 3 and cut it into pieces with weights 1 and 2. Then, choose the piece with weight 2 and cut it into two pieces with weight 1. Now all pieces have the same weight, so the answer is 0.
1)
    
{1, 1, 1, 1, 1}
4
Returns: 0.0
Even though you are allowed to make 4 cuts, there is no sense in making any of them.
2)
    
{1, 3}
1
Returns: 0.5
The same case as in example 0, but now you are allowed to make only one cut. The best thing to do is to cut the piece with weight 3 into two pieces with weights 1.5.
3)
    
{7, 11, 13}
10
Returns: 0.3999999999999999
4)
    
{13, 69, 41, 37, 80}
27
Returns: 1.4666666666666668

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10074

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13512&pm=10074

Writer:

ivan_metelsky

Testers:

PabloGilberto , Yarin , Olexiy

Problem categories:

Greedy