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
2
1
Returns: 1.0