Problem Statement
Time limit: 3 seconds.
You are going to build an undirected graph. You will start with N isolated vertices. Then, you will repeatedly select a pair of distinct vertices uniformly at random and add an edge that connects them.
Eventually, you will end up with a connected graph (in which some pairs of vertices are very likely to be connected by more than one direct edge). At that point the construction terminates.
Given N and S, calculate the probability that at some point during this process the graph will have a connected component with exactly S vertices.
Definition
- Class:
- Component
- Method:
- solve
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double solve(int N, int S)
- (be sure your method is public)
Notes
- A return value with an absolute error at most 1e-9 will be accepted as correct.
Constraints
- N will be between 2 and 50, inclusive.
- S will be between 1 and N, inclusive.
- N*S will not exceed 250.
Examples
10
2
Returns: 1.0
As soon as you add the first edge, you will have a component of size exactly 2, so it's sure that it will happen.
5
5
Returns: 1.0
The whole graph will eventually become connected with probability 1.
4
3
Returns: 0.7999999999999999
Sometimes there will be a component of size 3, other times there will be two components of size 2 that then get connected together into a component of size 4. Suppose the four vertices of your graph are A, B, C, D, and the first edge added is A-B. Now consider the following five edges: A-C, A-D, B-C, B-D, and C-D. There will be a component of size 3 if and only if C-D is not the first of these five edges to be added. And, by symmetry, the probability of that is 80%.
6
4
Returns: 0.7042957042957044
50
3
Returns: 0.9999055261684817
50
4
Returns: 0.9911642258618711
50
5
Returns: 0.9464651317141425
47
5
Returns: 0.9373818897529145
41
6
Returns: 0.8202616547288251
41
5
Returns: 0.9144277837433784
36
6
Returns: 0.7871780338576284
35
6
Returns: 0.7799329073752814
47
1
Returns: 1.0
47
2
Returns: 1.0
2
1
Returns: 1.0
35
7
Returns: 0.683810153963222
31
8
Returns: 0.577960118512861
27
9
Returns: 0.500473702182091
26
7
Returns: 0.6147663667051386
25
10
Returns: 0.45846797558954555
22
11
Returns: 0.43964863480098454
20
12
Returns: 0.44988855369642416
19
13
Returns: 0.485346893774155
17
14
Returns: 0.615507648354439
16
15
Returns: 0.8144691974604868
15
15
Returns: 1.0
15
14
Returns: 0.8053703010917366
15
13
Returns: 0.6800991708243264
15
11
Returns: 0.5368849028660777
15
6
Returns: 0.6022932245350884
15
3
Returns: 0.9559909453987911
14
7
Returns: 0.5433115670527969