AverageVarianceSubset | Topcoder Archive

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:

Let mu = (x_1 + ... + x_n) / n be the mean of the set.
Let y_i = (x_i - mu)^2 be the square of the difference between x_i and the mean.
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.

Definition

Class:: AverageVarianceSubset
Method:: average
Parameters:: int[], int
Returns:: double
Method signature:: double average(int[] s, int R)
(be sure your method is public)

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

```
{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,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.

{5,1,3,2}

1000000000

Returns: 1.2476851851851847

{1,11,111,1111,11111,111111,1111111,11111111,111111111}

Returns: 1.1349430459217174E9

{1,11,111,1111,11111,111111,1111111,11111111,111111111}

999999999

Returns: 9.989198236452121E14

{1,1000000000}

1000000000

Returns: 8.3333333166666672E16

Note that the answer can be very large.

```
{1,1000000000}
```
```
1
```
```
Returns: 0.0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.