JOIN
Get Time

   Problem Statement  

 Problem Statement for TreeUnion

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.
 

Definition

    
Class:TreeUnion
Method:expectedCycles
Parameters:String[], String[], int
Returns:double
Method signature:double expectedCycles(String[] tree1, String[] tree2, int K)
(be sure your method is public)
    
 

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.

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 581 Round 1 - Division I, Level Two