TopCoder problem "GroupingNumbers" used in SRM 280 (Division II Level Three)



Problem Statement

    

Your are given a int[] numbers. Your task is to split these numbers into exactly n groups such that the difference between the highest average of any group and the lowest average of any group is minimized. Each element of numbers must belong to exactly one of the n groups. Return this minimal difference.

 

Definition

    
Class:GroupingNumbers
Method:minRange
Parameters:int[], int
Returns:double
Method signature:double minRange(int[] numbers, int n)
(be sure your method is public)
    
 

Notes

-The return value must be within 1e-9 absolute or relative error of the actual result.
 

Constraints

-numbers will have between 1 and 9 elements inclusive.
-Each element in numbers will be between 1 and 1000 inclusive.
-n will be between 1 and the number of elements in numbers inclusive.
 

Examples

0)
    
{1,2,99,100}
2
Returns: 0.0
The best split is (1,100) and (2,99). Both groups have an average of 50.5, so the difference is 0.
1)
    
{3,3,3,3,3,3,3,3,3}
4
Returns: 0.0
When all the numbers are the same, the average of any group will be that number.
2)
    
{2,3,5,7,11,13}
3
Returns: 0.33333333333333304
The best split is (2,5,13), (3,11) and (7). The first group has an average of 6.66..., and the other two groups both have averages of 7. The difference is 0.33...
3)
    
{1, 2, 2, 998, 667}
2
Returns: 0.0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8077&pm=5937

Writer:

dimkadimon

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy