Problem Statement
Time limit is 3 seconds.
Given is a small simple graph. It has N vertices, labeled 0 to N-1. For each valid i, it contains an undirected edge between vertices X[i] and Y[i] with length L[i].
We have a biased coin. With probability P/100 the coin gives the result "erase" and in all other cases it gives the result "keep".
For each edge of the given graph we are going to throw the coin once and we perform the action it tells us: either we erase the edge or we keep it.
Once that is done, we are going to compute the cost of the minimum spanning forest of the remaining graph.
Calculate and return the expected value of the cost we'll get.
Definition
- Class:
- Forest
- Method:
- solve
- Parameters:
- int, int[], int[], int[], int
- Returns:
- double
- Method signature:
- double solve(int N, int[] X, int[] Y, int[] L, int P)
- (be sure your method is public)
Notes
- Return values with an absolute or a relative error at most 10^(-9) will be accepted.
- All throws of the coin are mutually independent.
- A subgraph of a graph is called spanning if it contains all vertices of the original graph and has the same connected components.
- The cost of a graph is defined to be the sum of all its edge lengths.
- The minimum spanning forest of a given graph G with positive edge lengths is the one with the minimum cost among all the spanning subgraphs of G.
Constraints
- N will be between 1 and 9, inclusive.
- X, Y, and L will contain the same number of elements.
- That number will be between 0 and N*(N-1)/2, inclusive.
- All elements of X and Y will be between 0 and N-1, inclusive.
- For each i, X[i] will not equal Y[i].
- The unordered pairs { X[i], Y[i] } will all be distinct.
- All elements of L will be between 1 and 100, inclusive.
- P will be between 0 and 100, inclusive.
Examples
3
{0, 0, 1}
{1, 2, 2}
{3, 4, 5}
0
Returns: 7.0
The graph is a triangle with edge lengths 3, 4, and 5. The coin always tells us to keep the edge, so we are guaranteed to keep the entire graph. Its minimum spanning forest contains the edges 0-1 (length 3) and 0-2 (length 4), so the final cost is guaranteed to be 3+4 = 7.
3
{0, 0, 1}
{1, 2, 2}
{3, 4, 5}
100
Returns: 0.0
Here the coin tells us to erase all the edges. After we are done with the coin flips, the graph is guaranteed to consist of just three isolated vertices. Its only spanning subgraph (and thus the minimum spanning forest) is the graph itself, and its cost is zero. (The empty sum is always zero.)
2
{1}
{0}
{47}
90
Returns: 4.699999999999999
With probability 90% we erase the edge and the cost will be 0, with probability 10% we keep it and the cost will be 47. The expected cost is therefore 0.9 * 0 + 0.1 * 47 = 4.7.
3
{0, 0, 1}
{1, 2, 2}
{3, 4, 5}
50
Returns: 5.375
There are eight equally likely possibilities for what happens during the erasing. Two of them correspond to examples 0 and 1. In each of the remaining six cases the cost of the minimum spanning subgraph is equal to the total cost of edges that weren't erased.
2
{0}
{1}
{20}
50
Returns: 10.0
2
{1}
{0}
{15}
6
Returns: 14.1
2
{1}
{0}
{33}
46
Returns: 17.82
3
{0, 1, 0}
{1, 2, 2}
{20, 10, 20}
72
Returns: 13.560960000000001
3
{0, 2, 1}
{2, 1, 0}
{29, 3, 32}
81
Returns: 11.940511999999996
3
{2, 1, 2}
{0, 0, 1}
{92, 72, 77}
7
Returns: 150.129156
4
{3, 0, 3, 2, 2, 2}
{1, 1, 0, 0, 1, 3}
{30, 10, 30, 10, 10, 10}
56
Returns: 34.641426800640005
4
{1, 1, 3, 2, 2, 3}
{3, 0, 2, 0, 1, 0}
{46, 13, 45, 3, 17, 7}
4
Returns: 25.363952467968
4
{0, 2, 2, 3, 1, 3}
{1, 0, 1, 0, 3, 2}
{22, 10, 66, 56, 98, 78}
13
Returns: 104.34738241983601
5
{4, 1, 3, 2, 4, 0, 1, 3, 4, 2}
{1, 3, 0, 3, 2, 1, 2, 4, 0, 0}
{30, 10, 10, 10, 10, 10, 20, 20, 30, 10}
32
Returns: 46.548408874128576
5
{0, 1, 0, 1, 4, 0, 1, 0, 4, 2}
{4, 3, 2, 2, 3, 3, 4, 1, 2, 3}
{1, 23, 15, 36, 18, 3, 25, 63, 20, 9}
43
Returns: 57.19042629054973
5
{4, 0, 3, 4, 1, 2, 3, 1, 0, 0}
{2, 4, 2, 3, 3, 1, 0, 4, 2, 1}
{46, 65, 37, 22, 73, 60, 3, 97, 9, 77}
84
Returns: 74.66797097679569
6
{5, 4, 5, 0, 5, 2, 2, 2, 1, 4, 3, 3, 5, 1, 3}
{0, 1, 2, 3, 1, 1, 0, 4, 3, 0, 5, 4, 4, 0, 2}
{10, 30, 30, 20, 20, 30, 10, 20, 30, 30, 10, 30, 30, 30, 30}
27
Returns: 87.9211302414394
6
{4, 4, 0, 3, 3, 3, 1, 2, 0, 1, 3, 1, 4, 4, 4}
{1, 2, 5, 1, 2, 0, 5, 5, 2, 2, 5, 0, 0, 3, 5}
{7, 3, 30, 30, 4, 1, 56, 2, 35, 31, 14, 15, 1, 16, 3}
47
Returns: 41.81949746840829
6
{4, 3, 1, 0, 2, 5, 4, 5, 4, 0, 2, 2, 2, 4, 1}
{3, 0, 2, 5, 4, 3, 5, 1, 0, 1, 3, 0, 5, 1, 3}
{51, 54, 14, 56, 77, 92, 43, 41, 86, 94, 80, 66, 10, 61, 71}
1
Returns: 172.79154737307212
7
{1, 3, 4, 6, 1, 1, 3, 4, 0, 5, 1, 3, 6, 4, 2, 4, 0, 0, 0, 1, 1}
{0, 6, 5, 2, 4, 3, 5, 3, 6, 6, 6, 2, 4, 2, 5, 0, 2, 3, 5, 2, 5}
{30, 20, 30, 10, 30, 20, 10, 10, 30, 30, 10, 20, 20, 30, 10, 10, 30, 20, 10, 30, 30}
44
Returns: 87.27222078069553
7
{6, 4, 1, 2, 1, 6, 0, 4, 2, 1, 3, 5, 4, 6, 6, 6, 1, 6, 5, 3, 0}
{5, 5, 3, 5, 0, 2, 3, 2, 0, 4, 2, 0, 3, 4, 0, 3, 2, 1, 1, 5, 4}
{1, 3, 7, 5, 14, 13, 9, 31, 1, 2, 5, 1, 2, 3, 51, 4, 1, 9, 1, 6, 15}
28
Returns: 11.911929310363346
7
{4, 0, 6, 2, 1, 1, 4, 4, 6, 1, 3, 0, 1, 6, 5, 0, 3, 6, 4, 4, 2}
{1, 3, 0, 5, 0, 2, 3, 2, 2, 6, 2, 4, 3, 5, 1, 5, 5, 3, 5, 6, 0}
{43, 78, 50, 7, 55, 1, 42, 5, 36, 25, 69, 61, 33, 39, 3, 1, 68, 66, 5, 5, 26}
27
Returns: 74.6842952606572
8
{7, 3, 7, 7, 6, 2, 5, 3, 0, 7, 4, 4, 3, 4, 1, 1, 2, 6, 0, 6, 2, 7, 3, 2, 1, 0, 3, 7}
{5, 0, 6, 3, 0, 1, 4, 2, 1, 0, 6, 7, 6, 0, 4, 3, 4, 1, 2, 5, 5, 1, 4, 6, 5, 5, 5, 2}
{10, 20, 20, 20, 30, 20, 30, 10, 10, 30, 10, 30, 10, 30, 20, 30, 10, 30, 10, 10, 10, 30, 30, 30, 10, 30, 30, 20}
25
Returns: 77.06753206830626
8
{0, 0, 1, 7, 2, 2, 0, 6, 7, 3, 7, 1, 5, 2, 2, 6, 4, 2, 0, 1, 1, 3, 5, 0, 1, 3, 3, 5}
{6, 5, 5, 2, 6, 5, 1, 4, 0, 2, 5, 6, 4, 0, 4, 7, 7, 1, 4, 7, 4, 4, 3, 3, 3, 6, 7, 6}
{1, 47, 7, 6, 6, 10, 5, 6, 7, 5, 3, 7, 4, 15, 2, 1, 1, 3, 53, 1, 27, 26, 8, 7, 2, 13, 1, 17}
23
Returns: 14.401876613002981
8
{1, 7, 0, 1, 5, 0, 2, 4, 2, 4, 4, 3, 6, 6, 3, 2, 3, 0, 7, 5, 2, 7, 0, 7, 6, 0, 6, 4}
{6, 5, 1, 5, 2, 7, 0, 7, 7, 5, 1, 2, 2, 3, 1, 1, 5, 4, 6, 0, 4, 3, 6, 1, 5, 3, 4, 3}
{97, 51, 84, 56, 79, 65, 69, 10, 48, 74, 10, 94, 4, 95, 41, 98, 74, 34, 89, 37, 59, 21, 25, 96, 76, 29, 26, 66}
43
Returns: 224.9383001919783
9
{8, 7, 2, 2, 1, 6, 2, 7, 3, 0, 5, 1, 4, 4, 0, 1, 6, 1, 2, 1, 7, 1, 6, 6, 3, 7, 0, 3, 3, 4, 5, 3, 5, 6, 2, 6}
{3, 2, 8, 5, 6, 8, 0, 5, 5, 8, 8, 0, 7, 8, 5, 8, 7, 7, 6, 4, 0, 3, 4, 0, 7, 8, 4, 4, 0, 2, 4, 2, 1, 5, 1, 3}
{20, 10, 20, 30, 30, 10, 10, 30, 30, 20, 10, 30, 10, 10, 10, 20, 30, 20, 10, 30, 20, 30, 10, 30, 10, 30, 10, 20, 20, 30, 30, 20, 20, 30, 10, 20}
30
Returns: 90.52614809240424
9
{6, 7, 7, 5, 4, 6, 6, 3, 7, 4, 1, 2, 3, 0, 1, 5, 5, 1, 4, 6, 2, 6, 7, 8, 4, 4, 6, 0, 0, 3, 2, 1, 6, 1, 4, 5}
{1, 4, 5, 4, 6, 7, 5, 8, 2, 8, 3, 3, 5, 2, 7, 1, 0, 0, 2, 8, 5, 0, 3, 7, 0, 1, 2, 7, 8, 0, 8, 2, 3, 8, 3, 8}
{13, 6, 2, 29, 2, 11, 4, 3, 2, 7, 49, 5, 14, 21, 4, 1, 17, 5, 2, 11, 29, 21, 4, 2, 31, 3, 1, 12, 25, 7, 24, 2, 2, 12, 12, 6}
49
Returns: 30.94406372886261
9
{0, 3, 1, 6, 3, 0, 1, 0, 4, 7, 4, 7, 5, 0, 7, 8, 7, 6, 1, 6, 8, 2, 3, 5, 6, 2, 8, 3, 8, 3, 4, 2, 5, 8, 7, 1}
{4, 4, 8, 3, 5, 7, 0, 5, 8, 4, 6, 5, 6, 6, 1, 2, 3, 2, 2, 1, 3, 5, 2, 8, 7, 0, 7, 1, 0, 0, 1, 4, 4, 6, 2, 5}
{77, 55, 70, 40, 93, 28, 4, 55, 34, 70, 80, 18, 87, 67, 98, 98, 64, 62, 30, 71, 66, 51, 24, 7, 46, 30, 89, 26, 90, 63, 5, 60, 31, 7, 76, 63}
7
Returns: 129.0709955527986
9
{}
{}
{}
47
Returns: 0.0
2
{}
{}
{}
78
Returns: 0.0
2
{1}
{0}
{15}
46
Returns: 8.100000000000001
2
{}
{}
{}
26
Returns: 0.0
3
{0, 1}
{1, 2}
{20, 10}
63
Returns: 11.1
3
{}
{}
{}
86
Returns: 0.0
3
{2}
{0}
{92}
47
Returns: 48.760000000000005
4
{3, 2}
{0, 1}
{30, 10}
99
Returns: 0.40000000000000036
4
{1, 1}
{3, 0}
{46, 13}
88
Returns: 7.08
4
{0, 2, 2, 3, 1, 3}
{1, 0, 1, 0, 3, 2}
{22, 10, 66, 56, 98, 78}
49
Returns: 120.81057110780401
5
{4, 1, 2, 4, 0, 1, 3, 4, 2}
{1, 3, 3, 2, 1, 2, 4, 0, 0}
{30, 10, 10, 10, 10, 20, 20, 30, 10}
94
Returns: 8.958241292548891
5
{0, 1}
{2, 2}
{15, 36}
55
Returns: 22.95
5
{0, 3, 4, 1, 2, 3, 1, 0, 0}
{4, 2, 3, 3, 1, 0, 4, 2, 1}
{65, 37, 22, 73, 60, 3, 97, 9, 77}
77
Returns: 94.10487357839162
6
{5, 4, 5, 0, 5, 2, 2, 1, 4, 3, 3, 5, 1, 3}
{0, 1, 2, 3, 1, 1, 0, 3, 0, 5, 4, 4, 0, 2}
{10, 30, 30, 20, 20, 30, 10, 30, 30, 10, 30, 30, 30, 30}
96
Returns: 13.56744643213438
6
{4, 0, 3, 3, 3, 1, 2, 0, 1, 3, 1, 4, 4, 4}
{2, 5, 1, 2, 0, 5, 5, 2, 2, 5, 0, 0, 3, 5}
{3, 30, 30, 4, 1, 56, 2, 35, 31, 14, 15, 1, 16, 3}
62
Returns: 56.911754695442596
6
{4, 3, 0, 5, 4, 0, 2, 4, 1}
{3, 0, 5, 1, 0, 1, 3, 1, 3}
{51, 54, 56, 41, 86, 94, 80, 61, 71}
63
Returns: 194.12688174517484
7
{3, 4, 1, 6, 4, 2, 0, 1, 1}
{6, 5, 6, 4, 2, 5, 5, 2, 5}
{20, 30, 10, 20, 30, 10, 10, 30, 30}
47
Returns: 86.0311881064478
7
{1, 6, 5, 6, 1, 3}
{0, 2, 0, 3, 2, 5}
{14, 13, 1, 4, 1, 6}
8
Returns: 27.39102998118401
7
{4, 0, 6, 2, 1, 1, 4, 6, 1, 6, 5, 4, 2}
{1, 3, 0, 5, 0, 2, 2, 2, 3, 5, 1, 5, 0}
{43, 78, 50, 7, 55, 1, 5, 36, 33, 39, 3, 5, 26}
35
Returns: 131.3978202177086
8
{7, 3, 7, 5, 3, 0, 2, 6, 7, 3, 2, 1, 0, 3, 7}
{5, 0, 3, 4, 2, 1, 4, 5, 1, 4, 6, 5, 5, 5, 2}
{10, 20, 20, 30, 10, 10, 10, 10, 30, 30, 30, 10, 30, 30, 20}
67
Returns: 87.12174684883809
8
{0, 7, 2, 2, 3, 1, 2, 6, 2, 3, 5, 3}
{6, 2, 6, 5, 2, 6, 4, 7, 1, 4, 3, 6}
{1, 6, 6, 10, 5, 7, 2, 1, 3, 26, 8, 13}
6
Returns: 28.200012099750023
8
{1, 7, 0, 1, 5, 0, 2, 4, 2, 4, 3, 6, 6, 3, 2, 3, 0, 7, 5, 2, 7, 0, 7, 6, 0, 6, 4}
{6, 5, 1, 5, 2, 7, 0, 7, 7, 5, 2, 2, 3, 1, 1, 5, 4, 6, 0, 4, 3, 6, 1, 5, 3, 4, 3}
{97, 51, 84, 56, 79, 65, 69, 10, 48, 74, 94, 4, 95, 41, 98, 74, 34, 89, 37, 59, 21, 25, 96, 76, 29, 26, 66}
52
Returns: 282.3584708751751
9
{8, 7, 2, 2, 1, 6, 2, 7, 3, 4, 0, 6, 2, 1, 1, 6, 6, 3, 7, 0, 3, 4, 5}
{3, 2, 8, 5, 6, 8, 0, 5, 5, 7, 5, 7, 6, 4, 3, 4, 0, 7, 8, 4, 4, 2, 4}
{20, 10, 20, 30, 30, 10, 10, 30, 30, 10, 10, 30, 10, 30, 30, 10, 30, 10, 30, 10, 20, 30, 30}
43
Returns: 126.83604908708156
9
{6, 7, 7, 5, 4, 6, 7, 4, 2, 0, 1, 5, 1, 6, 2, 6, 7, 8, 4, 0, 3, 2, 1, 6, 1, 4, 5}
{1, 4, 5, 4, 6, 7, 2, 8, 3, 2, 7, 1, 0, 8, 5, 0, 3, 7, 1, 8, 0, 8, 2, 3, 8, 3, 8}
{13, 6, 2, 29, 2, 11, 2, 7, 5, 21, 4, 1, 5, 11, 29, 21, 4, 2, 3, 25, 7, 24, 2, 2, 12, 12, 6}
14
Returns: 21.67042103106959
9
{3, 1, 4, 4, 7, 5, 6, 6, 2, 2, 3, 8, 7, 1}
{4, 0, 8, 6, 5, 6, 2, 1, 5, 0, 1, 6, 2, 5}
{55, 4, 34, 80, 18, 87, 62, 71, 51, 30, 26, 7, 76, 63}
27
Returns: 283.6478210628876
9
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7 }
{1, 2, 3, 4, 5, 6, 7, 8, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 6, 7, 8, 7, 8, 8 }
{57, 19, 85, 31, 25, 87, 21, 98, 75, 31, 85, 71, 98, 57, 12, 87, 57, 32, 98, 17, 34, 61, 56, 43, 18, 72, 43, 87, 59, 87, 32, 32, 13, 21, 72, 89 }
1
Returns: 156.86201359989866