Connection Status:
Competition Arena > TheGameDAG

TheGameDAG

TCO13 Semifinal 1 · 2013-02-19 · by gojira_tc

TCO13 Semifinal 1 · 2013-02-19 · by gojira_tc · Brute Force, Graph Theory, Math
Class Name: TheGameDAG
Return Type: double
Method Name: getProbability
Arg Types: (vector<int>, int, int)
Problem Statement

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.

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
0)
{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)
{1, 2, 3}
3
1
Returns: 0.0

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

2)
{1, 2, 3}
1
3
Returns: 0.54
3)
{1, 4, 3, 6, 5, 2}
3
5
Returns: 0.5569267034827158
4)
{2,1}
2
1
Returns: 0.6666666666666666

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

Coding Area

Language: C++17 · define a public class TheGameDAG with a public method double getProbability(vector<int> P, int A, int B) · 57 test cases · 2 s / 256 MB per case

Submitting as anonymous