Connection Status:
Competition Arena > DiameterOfRandomTree

DiameterOfRandomTree

SRM 677 · 2015-11-03 · by cgy4ever

SRM 677 · 2015-11-03 · by cgy4ever · Dynamic Programming, Graph Theory
Class Name: DiameterOfRandomTree
Return Type: double
Method Name: getExpectation
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Given a tree, let d(u,v) be the distance between nodes u and v in the tree. In other words, d(u,v) is the length of the only simple path that connects u and v. The diameter of the tree is the maximum of all d(u,v).

You are given int[]s a and b, each containing n-1 elements. These describe a tree with n nodes, labeled 0 through n-1. For each valid i, the nodes a[i] and b[i] are connected by an edge.

The length of each edge is generated randomly. More precisely, the length of each edge is either 1 or 2 with equal probability. The lengths of edges are mutually independent.

Return the expected value of the diameter of the given tree.

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • a and b will contain the same number of elements.
  • Each element in a will be between 0 and |a|, inclusive.
  • Each element in b will be between 0 and |a|, inclusive.
  • The graph will be a tree.
Examples
0)
{0,1,2,3}
{1,2,3,4}
Returns: 6.0

This graph is a single path: 0-1-2-3-4. In this case, the diameter will always be the distance between nodes 0 and 4. The expected length of each edge is 1.5, thus the expected distance between 0 and 4 equals 4 * 1.5 = 6.

1)
{0,0,0}
{1,2,3}
Returns: 3.375

This tree has three edges: 0-1, 0-2, and 0-3. There are four possible cases: With probability 1/8 all three edges have length 1. In this case, the diameter is 2. With probability 3/8 the edges have lengths (1,1,2). In this case, the diameter is 3. With probability 3/8 the edges have lengths (1,2,2). In this case, the diameter is 4. With probability 1/8 all three edges have length 2. In this case, the diameter is also 4. Thus, the expected diameter is (1/8)*2 + (3/8)*3 + (3/8)*4 + (1/8)*4 = 27/8 = 3.375.

2)
{0,0,0,1,4}
{1,2,3,4,5}
Returns: 6.25
3)
{0,0,0,0,0,0,0,0}
{1,2,3,4,5,6,7,8}
Returns: 3.9609375
4)
{0,0,0,1,2,3,5,6,8}
{1,2,3,4,5,6,7,8,9}
Returns: 10.53125

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

Coding Area

Language: C++17 · define a public class DiameterOfRandomTree with a public method double getExpectation(vector<int> a, vector<int> b) · 90 test cases · 2 s / 256 MB per case

Submitting as anonymous