Connection Status:
Competition Arena > AverageVarianceSubset

AverageVarianceSubset

SRM 712 · 2017-02-20 · by cgy4ever

SRM 712 · 2017-02-20 · by cgy4ever · Math
Class Name: AverageVarianceSubset
Return Type: double
Method Name: average
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its mean. As a special case, we can compute the variance of a nonempty finite set X = { x_1, ..., x_n } as follows:
  1. Let mu = (x_1 + ... + x_n) / n be the mean of the set.
  2. Let y_i = (x_i - mu)^2 be the square of the difference between x_i and the mean.
  3. The variance of X, denoted var(X), can now be computed as the average of all y_i. (In other words, as the sum of all y_i, divided by n.)
For example, if X = { 0, 1 }, we have mu = 1/2, then y_1 = y_2 = 1/4, and finally var(X) = (1/4 + 1/4) / 2 = 1/4.

The range of a nonempty finite set is the difference between its maximum and its minimum. For example, the range of the set { 40, 51, 67, 70 } is 70 - 40 = 30.

You are given a int[] s that contains a set of distinct positive integers. You are also given an int R.

Consider all nonempty subsets of s with range less than or equal to R. Alice computed the variance of each of those subsets. Bob took all Alice's results and computed their average. Compute and return the number computed by Bob.

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • s will contain between 1 and 50 elements, inclusive.
  • Elements in s will be distinct.
  • Each element in s will be between 1 and 1,000,000,000, inclusive.
  • R will be between 0 and 1,000,000,000, inclusive.
Examples
0)
{1,2,3}
1
Returns: 0.1

This set has seven nonempty subsets. Out of those, five have range at most 1: {1}, {2}, {3}, {1,2}, and {2,3}. Alice computed the variance of each of these subsets: The variance of {1} is 0. The variance of {2} is 0. The variance of {3} is 0. The variance of {1,2} is 1/4. The variance of {2,3} is 1/4. Bob took Alice's results and computed their average: (0 + 0 + 0 + 1/4 + 1/4) / 5 = 1/10.

1)
{1,2,3}
3
Returns: 0.3095238095238096

This time Alice will consider all seven nonempty subsets. The two new subsets: The variance of {1,3} is 1. The variance of {1,2,3} is 2/3. Bob will then compute the value (0+0+0+1/4+1/4+1+2/3)/7 = 13/42.

2)
{5,1,3,2}
1000000000
Returns: 1.2476851851851847
3)
{1,11,111,1111,11111,111111,1111111,11111111,111111111}
123456
Returns: 1.1349430459217174E9
4)
{1,11,111,1111,11111,111111,1111111,11111111,111111111}
999999999
Returns: 9.989198236452121E14
5)
{1,1000000000}
1000000000
Returns: 8.3333333166666672E16

Note that the answer can be very large.

Submissions are judged against all 68 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AverageVarianceSubset with a public method double average(vector<int> s, int R) · 68 test cases · 2 s / 256 MB per case

Submitting as anonymous