Component
SRM 843 · 2023-01-03 · by misof
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.
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.
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
Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Component with a public method double solve(int N, int S) · 32 test cases · 2 s / 256 MB per case