Statistics

Problem Statement for "RandomGraph"

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

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

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

  3. 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.

  4. 8

    100

    Returns: 0.33566851611343496

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

  5. 15

    50

    Returns: 0.5686761670525845

  6. 50

    10

    Returns: 0.7494276522159893

  7. 50

    1000

    Returns: 1.0

  8. 2

    202

    Returns: 0.0

  9. 10

    141

    Returns: 0.8337264488082298

  10. 50

    650

    Returns: 1.0

  11. 7

    454

    Returns: 0.9957913645318551

  12. 36

    101

    Returns: 0.9999999999999996

  13. 23

    564

    Returns: 1.0

  14. 50

    459

    Returns: 1.0

  15. 28

    304

    Returns: 1.0

  16. 4

    127

    Returns: 0.02495710047527988

  17. 19

    851

    Returns: 1.0

  18. 32

    317

    Returns: 1.0

  19. 49

    608

    Returns: 1.0

  20. 18

    294

    Returns: 0.9999999999999881

  21. 35

    531

    Returns: 1.0

  22. 5

    182

    Returns: 0.20624951752202791

  23. 30

    752

    Returns: 1.0

  24. 27

    204

    Returns: 1.0

  25. 23

    163

    Returns: 0.9999999999508394

  26. 11

    635

    Returns: 0.9999999999999999

  27. 25

    82

    Returns: 0.99994799499826

  28. 2

    100

    Returns: 0.0

  29. 48

    55

    Returns: 0.9999999999997464

  30. 36

    629

    Returns: 1.0

  31. 48

    725

    Returns: 1.0

  32. 43

    150

    Returns: 1.0

  33. 3

    145

    Returns: 0.0

  34. 44

    777

    Returns: 1.0

  35. 45

    419

    Returns: 1.0

  36. 20

    416

    Returns: 1.0

  37. 42

    839

    Returns: 1.0

  38. 30

    675

    Returns: 1.0

  39. 41

    62

    Returns: 0.9999999999234339

  40. 41

    665

    Returns: 1.0

  41. 11

    596

    Returns: 0.9999999999999865

  42. 26

    779

    Returns: 1.0

  43. 47

    79

    Returns: 1.0

  44. 44

    316

    Returns: 1.0

  45. 12

    207

    Returns: 0.9980276101036871

  46. 39

    681

    Returns: 1.0

  47. 24

    34

    Returns: 0.8245285655243519

  48. 19

    784

    Returns: 1.0

  49. 34

    795

    Returns: 1.0

  50. 33

    770

    Returns: 1.0

  51. 3

    426

    Returns: 0.0

  52. 23

    314

    Returns: 1.0

  53. 43

    884

    Returns: 1.0

  54. 19

    847

    Returns: 1.0

  55. 34

    404

    Returns: 1.0

  56. 41

    691

    Returns: 1.0

  57. 31

    536

    Returns: 1.0

  58. 17

    754

    Returns: 1.0

  59. 10

    786

    Returns: 1.0

  60. 12

    994

    Returns: 1.0

  61. 33

    698

    Returns: 1.0

  62. 23

    378

    Returns: 1.0

  63. 8

    749

    Returns: 0.999999999942898

  64. 11

    529

    Returns: 0.9999999999901812

  65. 10

    607

    Returns: 0.9999999999950838

  66. 16

    200

    Returns: 0.9999974191252643

  67. 6

    550

    Returns: 0.9930856223520955

  68. 36

    557

    Returns: 1.0

  69. 26

    252

    Returns: 1.0

  70. 28

    277

    Returns: 1.0

  71. 31

    666

    Returns: 1.0

  72. 46

    371

    Returns: 1.0

  73. 34

    41

    Returns: 0.9991163783725384

  74. 46

    417

    Returns: 1.0

  75. 30

    613

    Returns: 1.0

  76. 30

    333

    Returns: 1.0

  77. 37

    382

    Returns: 1.0

  78. 15

    255

    Returns: 0.9999999005381354

  79. 33

    114

    Returns: 0.9999999999999984

  80. 26

    595

    Returns: 1.0

  81. 7

    963

    Returns: 1.0

  82. 3

    498

    Returns: 0.0

  83. 33

    477

    Returns: 1.0

  84. 44

    183

    Returns: 1.0

  85. 32

    471

    Returns: 1.0

  86. 49

    610

    Returns: 1.0

  87. 50

    700

    Returns: 1.0

  88. 50

    543

    Returns: 1.0

  89. 13

    13

    Returns: 0.01833583599028421

  90. 47

    437

    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.
This problem was used for: