Statistics

Problem Statement for "TheGameDAG"

Problem Statement

A game development company has created a new strategy game. The game is divided into N missions numbered from 1 to N. The order of completing the missions is not linear; there might be several missions which can be attempted at the same time. Some missions' completion is a prerequisite for attempting other missions. More specifically, a directed acyclic graph with N vertices (further referred to as a DAG) is associated with the game. Each arc (i, j) in this DAG means that the mission i is a prerequisite of mission j and thus mission j cannot be attempted before mission i is completed. Note that this DAG may or may not contain redundant arcs; for example if there are arcs (1, 2) and (2, 3) in the DAG, it is clear that mission 3 cannot be attempted before mission 1 is completed, however the DAG may or may not contain arc (1, 3).

Manao is the alpha-tester of this game. The DAG of the game was generated uniformly at random from the set of all DAGs with N vertices, and then Manao played the game and completed the missions in the order given in the int[] P. He used the following strategy for choosing the next mission to attempt: whenever there were several missions with their prerequisites fulfilled, he chose one of them uniformly at random and completed it.

Manao wonders what was the DAG of the game he played. Given two vertices A and B, compute the probability that the edge (A, B) was present in the game's DAG.

Definition

Class:
TheGameDAG
Method:
getProbability
Parameters:
int[], int, int
Returns:
double
Method signature:
double getProbability(int[] P, int A, int B)
(be sure your method is public)

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • P will contain between 2 and 9 elements, inclusive.
  • P will contain each number from 1 to N exactly once, where N is the number of elements in P.
  • A will be between 1 and the number of elements in P, inclusive.
  • B will be between 1 and the number of elements in P, inclusive.
  • A and B will be distinct.

Examples

  1. {2, 1}

    2

    1

    Returns: 0.6666666666666666

    There are three DAGs composed of 2 vertices: an empty DAG, a DAG with arc 1->2 and a DAG with arc 2->1. For the empty DAG, Manao would complete mission 2 before mission 1 with probability 0.5. For the DAG with arc 1->2, he could not complete mission 2 before mission 1. For the DAG with arc 2->1, Manao would complete missions in the given order with probability 1.0. Thus, the arc 2->1 was present in the DAG of Manao's game with probability 1.0 / (0.5 + 1.0) = 0.(6).

  2. {1, 2, 3}

    3

    1

    Returns: 0.0

    The DAG cannot contain the arc 3->1, because mission 1 was finished before mission 3.

  3. {1, 2, 3}

    1

    3

    Returns: 0.54

  4. {1, 4, 3, 6, 5, 2}

    3

    5

    Returns: 0.5569267034827158

  5. {2,1}

    2

    1

    Returns: 0.6666666666666666

  6. {1,2}

    1

    2

    Returns: 0.6666666666666666

  7. {3,1,2}

    3

    2

    Returns: 0.54

  8. {1,2,3}

    1

    2

    Returns: 0.6600000000000001

  9. {1,3,2}

    1

    3

    Returns: 0.6600000000000001

  10. {1,2,3,4}

    2

    4

    Returns: 0.5524861878453039

  11. {1,3,4,2}

    3

    4

    Returns: 0.7145488029465928

  12. {4,2,3,1}

    4

    1

    Returns: 0.5107427869858809

  13. {1,3,4,2}

    1

    3

    Returns: 0.6580724370779619

  14. {3,4,5,2,1}

    4

    5

    Returns: 0.7129765604544471

  15. {2,5,1,4,3}

    2

    1

    Returns: 0.5402583776358579

  16. {1,4,3,2,5}

    3

    5

    Returns: 0.5563334585567432

  17. {3,2,4,5,1}

    4

    5

    Returns: 0.7318739114101293

  18. {2,5,3,4,1}

    3

    1

    Returns: 0.5563334585567432

  19. {5,2,3,1,6,4}

    2

    1

    Returns: 0.553106441186657

  20. {5,4,2,3,6,1}

    5

    2

    Returns: 0.5402721572172052

  21. {2,1,3,5,4,6}

    1

    5

    Returns: 0.553106441186657

  22. {3,1,5,4,6,2}

    3

    5

    Returns: 0.5402721572172052

  23. {4,2,6,5,3,1}

    3

    1

    Returns: 0.7433488747728086

  24. {6,4,2,5,3,1}

    4

    1

    Returns: 0.5038826272692807

  25. {3,6,2,5,1,4,7}

    6

    4

    Returns: 0.5039734963230288

  26. {1,7,2,6,5,4,3}

    2

    5

    Returns: 0.5570886678083862

  27. {6,7,3,2,5,1,4}

    3

    5

    Returns: 0.5570886678083862

  28. {1,4,2,5,7,6,3}

    7

    6

    Returns: 0.7388813775073392

  29. {5,1,6,4,7,2,3}

    4

    2

    Returns: 0.558138209515078

  30. {7,4,2,3,6,5,1}

    6

    5

    Returns: 0.7388813775073392

  31. {3,1,5,7,2,6,4}

    7

    6

    Returns: 0.558138209515078

  32. {1,5,4,7,2,6,3}

    1

    5

    Returns: 0.6572651730125498

  33. {3,6,8,7,2,1,5,4}

    7

    1

    Returns: 0.5583100138120185

  34. {8,3,4,2,1,6,5,7}

    3

    6

    Returns: 0.5039998951189696

  35. {2,5,7,4,1,3,6,8}

    1

    3

    Returns: 0.7376056053109797

  36. {4,7,1,8,5,2,3,6}

    7

    8

    Returns: 0.553156194521575

  37. {2,1,5,3,8,7,6,4}

    1

    8

    Returns: 0.5144246468538924

  38. {2,3,5,7,1,6,4,8}

    3

    7

    Returns: 0.553156194521575

  39. {4,3,1,6,8,2,7,5}

    4

    2

    Returns: 0.5008591536375631

  40. {1,6,5,2,7,3,4,8}

    5

    2

    Returns: 0.729972919957497

  41. {7,6,2,8,3,5,1,4}

    5

    4

    Returns: 0.557981291348968

  42. {2,1,3,7,5,8,4,6}

    2

    5

    Returns: 0.5030708691724579

  43. {6,3,8,9,1,4,2,7,5}

    8

    2

    Returns: 0.5042850167690017

  44. {5,7,9,1,8,3,6,4,2}

    4

    2

    Returns: 0.7440196935583328

  45. {9,7,6,3,5,8,4,1,2}

    3

    8

    Returns: 0.5583605057671166

  46. {6,7,9,8,1,2,4,5,3}

    6

    8

    Returns: 0.5110263432184605

  47. {6,3,5,9,8,2,7,4,1}

    6

    1

    Returns: 0.5000184835943282

  48. {4,7,9,5,6,2,1,3,8}

    2

    3

    Returns: 0.5586212536309283

  49. {4,8,5,2,3,7,6,9,1}

    2

    7

    Returns: 0.5583605057671166

  50. {1,9,4,8,7,3,5,2,6}

    7

    6

    Returns: 0.5042689825639031

  51. {8,3,9,5,7,1,6,2,4}

    8

    2

    Returns: 0.5000673829563853

  52. {6,5,2,1,7,8,9,3,4}

    5

    7

    Returns: 0.514431873620261

  53. {4,1,7,2,5,9,8,3,6}

    8

    3

    Returns: 0.7395370159239041

  54. {7,9,4,3,2,6,1,5,8}

    6

    1

    Returns: 0.738114805272144

  55. {1,2,9,3,6,5,8,4,7}

    1

    3

    Returns: 0.5110263432184605

  56. {5,4,2,7,6,8,9,1,3}

    4

    8

    Returns: 0.5040078124952025

  57. {6,4,3,9,5,1,2,8,7}

    9

    7

    Returns: 0.5011858860560741

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: