Connection Status:
Competition Arena > TreeUnion

TreeUnion

SRM 581 · 2012-12-13 · by gojira_tc

SRM 581 · 2012-12-13 · by gojira_tc · Dynamic Programming, Graph Theory, Math
Class Name: TreeUnion
Return Type: double
Method Name: expectedCycles
Arg Types: (vector<string>, vector<string>, int)
Problem Statement

Problem Statement

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Manao is studying graph theory and simple cycles in particular. A simple cycle of length L ≥ 3 in graph G is a sequence of vertices (v0, v1, ..., vL-1) such that all v0, v1, ..., vL-1 are pairwise distinct and for each i=0..L-1, an edge between vi and v(i+1) mod L exists in G.

Manao is interested in graphs formed by connecting two trees. The connection process is as follows. Manao takes two trees composed of N vertices each. The vertices in each tree are labeled from 0 to N - 1. Then, he generates a permutation P of numbers from 0 to N - 1 uniformly at random. Finally, the graph is formed by connecting vertex i of the first tree to vertex P[i] of the second tree, for each i from 0 to N - 1. To remove ambiguity, the vertices of the first tree within the graph are referred to as A0, A1, ..., AN-1 and the vertices of the second graph are referred to as B0, B1, ..., BN-1. Manao wants to know the expected number of simple cycles of length K in the resulting graph.

You are given two String[]s, tree1 and tree2. Merge the elements of tree1 to obtain a single string formatted as a space-separated list of N - 1 integers describing the first tree. Let x[i] denote the i-th integer (0-based index) in the list. Then, for each i, we have 0 ≤ x[i] ≤ i and in our tree the vertices x[i] and i+1 are connected by an edge. tree2 describes the second tree in the same fashion.

Compute and return the expected number of simple cycles of length K in the graph formed by connecting the two given trees as described above. Two simple cycles are equal if one of them can be cyclically shifted, or reversed and cyclically shifted, to coincide with the second. According to this definition, (1, 2, 3, 4), (2, 3, 4, 1) and (3, 2, 1, 4) are all equal.

Notes

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

Constraints

  • The concatenation of elements of tree1 will be formatted as a space-separated list of N - 1 integers, where N is between 2 and 300, inclusive.
  • tree1 will contain between 1 and 50 elements, inclusive.
  • Each element of tree1 will be between 1 and 50 characters long, inclusive.
  • For each i, the i-th integer (0-based index) in the concatenation of elements of tree1 will be between 0 and i, inclusive, and will have no extra leading zeros.
  • The concatenation of elements of tree2 will be formatted as a space-separated list of N - 1 integers, where N is between 2 and 300, inclusive.
  • tree2 will contain between 1 and 50 elements, inclusive.
  • Each element of tree2 will be between 1 and 50 characters long, inclusive.
  • For each i, the i-th integer (0-based index) in the concatenation of elements of tree2 will be between 0 and i, inclusive, and will have no extra leading zeros.
  • K will be between 3 and 7, inclusive.
Examples
0)
{"0"}
{"0"}
4
Returns: 1.0

Manao has two trees with two vertices each. He can connect them in two ways: Either way, the resulting graph is a single cycle of length 4.

1)
{"0 1"}
{"0 1"}
4
Returns: 1.3333333333333333

Manao has two chains composed of three vertices each. There are 6 possible permutations which result in the following graphs: Each of the two graphs shown in the topmost row contains two cycles of length 4. (Note that in each case the two cycles share the edge A1B1.) Each of the other four graphs only contains one cycle of length 4. Thus the expected number of cycles of length 4 is (2+2+1+1+1+1)/6 = 8/6 = 1.3333333333.

2)
{"0 1"}
{"0 1"}
6
Returns: 0.3333333333333333

These are the same trees as in the previous example, but this time Manao is looking for simple cycles with 6 vertices. Only the topmost two graphs contain a cycle of length 6, thus the expected number of such cycles for a random permutation P is 1/3.

3)
{"0 ", "1 1 1"}
{"0 1 0 ", "1"}
5
Returns: 4.0

The corresponding trees are these:

4)
{"0 1 2 0 1 2 0 1 2 5 6 1", "0 11", " 4"}
{"0 1 1 0 2 3 4 3 4 6 6", " 10 12 12"}
7
Returns: 13.314285714285713

Do not forget to concatenate the elements of the lists first.

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

Coding Area

Language: C++17 · define a public class TreeUnion with a public method double expectedCycles(vector<string> tree1, vector<string> tree2, int K) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous