RandomGraph | Topcoder Archive

Problem Statement

Consider a random undirected graph on n vertices. The vertices are numbered 0 through n-1. For each i and j such that 0 <= i < j <= n-1, the graph contains the edge i-j with probability p/1000. The probabilities that different edges are present in the graph are all mutually independent.

You are given the ints n and p. Calculate and return the probability that the random graph generated using the above procedure contains at least one connected component with 4 or more vertices.

Definition

Class:: RandomGraph
Method:: probability
Parameters:: int, int
Returns:: double
Method signature:: double probability(int n, int p)
(be sure your method is public)

Notes

Your return value must have an absolute or relative error less than 1e-9.
A connected component is a maximal set S of vertices such that you can get from any vertex in S to any other vertex in S by following a sequence of edges. For example, if a graph with n=5 contains edges 0-2, 2-4, and 1-3, its connected components are {0,2,4} and {1,3}.

Constraints

n will be between 2 and 50, inclusive.
p will be between 0 and 1000, inclusive.

Examples

```
7
```
```
0
```
```
Returns: 0.0
```
The probability of each edge is 0. Therefore, this graph will always have 7 isolated vertices = 7 connected components, each with just a single vertex.
```
3
```
```
620
```
```
Returns: 0.0
```
This graph only has 3 vertices, so it is impossible to have a connected component with at least 4 vertices.
```
4
```
```
500
```
```
Returns: 0.59375
```
There are 64 different graphs on 4 labeled vertices. As p=500, each of these 64 graphs is equally likely to be generated by our procedure. A graph on 4 vertices has a connected component with 4 or more vertices if and only if the entire graph is connected. Out of our 64 possible graphs, 38 are connected. Therefore, the probability we are looking for is 38/64.
```
8
```
```
100
```
```
Returns: 0.33566851611343496
```
In this case, some of the good graphs have two connected components, each with 4 vertices.
```
15
```
```
50
```
```
Returns: 0.5686761670525845
```
```
50
```
```
10
```
```
Returns: 0.7494276522159893
```
```
50
```
```
1000
```
```
Returns: 1.0
```

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)2024, Topcoder, Inc. All rights reserved.