TopCoder problem "MinimumVariancePartition" used in SRM 335 (Division II Level Three)



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

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Dynamic Programming, Math, Sorting