Connection Status:
Competition Arena > RandomGraph

RandomGraph

SRM 620 · 2013-12-22 · by cgy4ever

SRM 620 · 2013-12-22 · by cgy4ever · Dynamic Programming
Class Name: RandomGraph
Return Type: double
Method Name: probability
Arg Types: (int, int)
Problem Statement

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.

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
0)
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.

1)
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.

2)
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.

3)
8
100
Returns: 0.33566851611343496

In this case, some of the good graphs have two connected components, each with 4 vertices.

4)
15
50
Returns: 0.5686761670525845

Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RandomGraph with a public method double probability(int n, int p) · 90 test cases · 2 s / 256 MB per case

Submitting as anonymous