Problem Statement

In this problem a sample will be a collection of numbers. The mean of a sample is the average of all the numbers it contains. The variance of a sample is the sum of the squares of the distances from each number in the collection to its mean, divided by its number of elements. For example, if the sample is {3,4,7,10} the mean is 6 and the variance is (32+22+12+42)/4=7.5

We have k samples that have been combined into one collection and we need to split them up. The only thing we remember about the samples is that none of them were empty, but they could potentially each have a different number of elements. What you need to do for us is find the partition of mixedSamples, the collection, that minimizes the sum of the variances of the obtained samples. See examples for further clarification.

Definition

 Class: MinimumVariancePartition Method: minDev Parameters: int[], int Returns: double Method signature: double minDev(int[] mixedSamples, int k) (be sure your method is public)

Constraints

-mixedSamples will contain between 1 and 50 elements, inclusive.
-Each element of mixedSamples will be between 1 and 1000, inclusive.
-k will be between 1 and the number of elements in mixedSamples, inclusive.

Examples

0)

 {3,4,7,10} 1
Returns: 7.5
 Since all elements are part of the same sample, the result is simply the variance as it was shown in the problem statement.
1)

 {1000,500,1,500} 3
Returns: 0.0
 You need to partition the sample into 3 non empty sets. The partition that minimizes the sum of the variances is {1000},{1},{500,500}. The variance of each of these samples is equal to 0.
2)

 {54,653,876,2,75} 5
Returns: 0.0
 Each sample must contain a single element, and therefore the resulting variance is 0.
3)

 {42,234,10,1,123,545,436,453,74,85,34,999} 5
Returns: 1700.7397959183672
4)

 {923,456,12,12,542,234,11,12,10,9} 4
Returns: 1850.3333333333333

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10659&pm=7363

soul-net

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Dynamic Programming, Math, Sorting