TheGameDAG | Topcoder Archive

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

```
{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).
```
{1, 2, 3}
```
```
3
```
```
1
```
```
Returns: 0.0
```
The DAG cannot contain the arc 3->1, because mission 1 was finished before mission 3.
```
{1, 2, 3}
```
```
1
```
```
3
```
```
Returns: 0.54
```

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

Returns: 0.5569267034827158

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.