Connection Status:
Competition Arena > AverageVarianceSubtree

AverageVarianceSubtree

SRM 712 · 2017-02-20 · by cgy4ever

SRM 712 · 2017-02-20 · by cgy4ever · Math
Class Name: AverageVarianceSubtree
Return Type: double
Method Name: average
Arg Types: (vector<int>, vector<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 collection of numbers X = { x_1, ..., x_n } as follows:
  1. Let mu = (x_1 + ... + x_n) / n be the mean of the collection.
  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.

Another example: suppose X = { 0, 0, 0, 1 }. Now we have mu = 1/4. Then we compute that y_1 = y_2 = y_3 = 1/16 and y_4 = 9/16. The average of these four values is 3/16.

You are given a tree T with n vertices, labeled 0 through n-1. More precisely, you are given the int[] p with n-1 elements that describes the edges of the tree. For each valid i, there is an edge between (i+1) and p[i]. The constraints ensure that this will always be a valid tree.

Each vertex of the tree has a positive integer weight. You are given these weights in the int[] weight with n elements.

A subtree of the tree T is any subgraph that is a tree. Alice found all nonempty subtrees of T. For each of them, she took the collection of weights of its vertices and she computed its variance. Bob then computed the average of all the variances computed by Alice. Compute and return the number Bob computed.

Notes

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

Constraints

  • weight will contain between 1 and 50 elements, inclusive.
  • Each element in weight will be between 1 and 1,000,000,000, inclusive.
  • p will contain exactly |weight|-1 elements.
  • For each i, 0 <= p[i] <= i.
Examples
0)
{0,1}
{10,20,30}
Returns: 19.444444444444443

The tree contains the edges 1-0 and 2-1. Thus, it looks as follows: 0-1-2. This tree has six different subtrees. These correspond to the following collections of weights: {10}, {20}, {30}, {10,20}, {20,30}, and {10,20,30}. Their variances are 0, 0, 0, 25, 25, and 200/3. The return value is the average of these six numbers.

1)
{0,1,1}
{10,20,7,6}
Returns: 23.0145202020202

This time the tree looks as shown below. (The numbers in the figure are the weights of those vertices.) 10 - 20 - 7 | 6 This tree has 11 nonempty subtrees. Below we list the collection of weights and its variance for each of the subtrees. {10}, 0.0000000000000000 {20}, 0.0000000000000000 {7}, 0.0000000000000000 {6}, 0.0000000000000000 {10,20}, 25.0000000000000000 {7,20}, 42.2500000000000000 {6,20}, 49.0000000000000000 {20,7,6}, 40.6666666666666643 {10,20,6}, 34.6666666666666643 {10,20,7}, 30.8888888888888857 {10,20,7,6}, 30.6875000000000000

2)
{0}
{1,1000000000}
Returns: 8.3333333166666672E16

The answer can be very large

3)
{0,0,1,0,2,3,3,6}
{1,11,111,1111,11111,111111,1111111,11111111,111111111}
Returns: 4.432586365551198E14
4)
{}
{712}
Returns: 0.0

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

Coding Area

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

Submitting as anonymous