MinimumVariancePartition
SRM 335 · 2007-01-17 · by soul-net
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.
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.
{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.
{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.
{54,653,876,2,75}
5
Returns: 0.0
Each sample must contain a single element, and therefore the resulting variance is 0.
{42,234,10,1,123,545,436,453,74,85,34,999}
5
Returns: 1700.7397959183672
{1000}
1
Returns: 0.0
Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MinimumVariancePartition with a public method double minDev(vector<int> mixedSamples, int k) · 91 test cases · 2 s / 256 MB per case