Connection Status:
Competition Arena > EagleInZoo

EagleInZoo

TCO14 Round 1B · 2014-03-26 · by tozangezan

TCO14 Round 1B · 2014-03-26 · by tozangezan · Dynamic Programming, Graph Theory
Class Name: EagleInZoo
Return Type: double
Method Name: calc
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

John, Gogo, and Brus came to the zoo today. The most interesting thing in the zoo was the eagle cage.

There was a big tree in the cage. For the purpose of this problem, the tree is a connected graph with N vertices and N-1 edges. The vertices are numbered 0 through N-1, with 0 being the root of the tree. You are given the description of the tree in a int[] parent with N-1 elements. For each i between 1 and N, inclusive, the vertex number parent[i-1] is the parent of the vertex number i. The root vertex 0 has no parent.

You are also given an int K. There are K eagles in the cage. The eagles like to sit on vertices of the tree. Initially, the tree is empty. Then, one after another, each of the eagles makes one attempt to sit on the tree. When attempting to sit on the tree, each eagle follows the algorithm described below.

An eagle who tries to sit on the tree starts by flying to the root vertex. Then, the eagle repeats the following steps until the algorithm terminates:
  1. If the eagle is at an empty vertex, the eagle sits there and the algorithm terminates.
  2. If the eagle is at a vertex where another eagle sits, and the vertex has no children, the current eagle gives up and flies away from the tree. The algorithm terminates.
  3. If the eagle is at a vertex where another eagle sits, and the vertex has one or more children, the current eagle chooses one of the children uniformly at random, and flies to that vertex.


Return the probability that the last eagle (i.e., the K-th eagle who attempts to sit on the tree) will actually sit on the tree.

Notes

  • Vertex Y is a child of vertex X if and only if vertex X is the parent of vertex Y.
  • The constraints guarantee that parent describes a valid tree.

Constraints

  • parent will contain between 1 and 50 elements, inclusive.
  • For each i, element i of parent will be between 0 and i, inclusive.
  • K will be between 1 and 100, inclusive.
Examples
0)
{0,0}
2
Returns: 1.0

The first eagle will start at the root vertex. It will find that the vertex is empty, and it will sit there. The second eagle will also start at the root vertex, but the vertex is already occupied. Vertex 0 has two children: vertices 1 and 2. The second eagle will pick one of them uniformly at random, fly to that vertex, and sit there. Thus, the second eagle will always sit on the tree, hence the probability we want to compute is 1.

1)
{0,0}
3
Returns: 0.5

There are four equally likely ways how the process can look like: First eagle sits at 0. Second eagle flies from 0 to 1 and sits there. Third eagle flies from 0 to 1, finds it occupied and flies away from the tree. First eagle sits at 0. Second eagle flies from 0 to 1 and sits there. Third eagle flies from 0 to 2 and sits there. First eagle sits at 0. Second eagle flies from 0 to 2 and sits there. Third eagle flies from 0 to 1 and sits there. First eagle sits at 0. Second eagle flies from 0 to 2 and sits there. Third eagle flies from 0 to 2, finds it occupied and flies away from the tree. Thus, the probability that the third eagle will sit on the tree is 2/4.

2)
{0,1,0,3}
4
Returns: 0.75
3)
{0,0,1,1,2,4,4,4,5,5,6,6}
20
Returns: 0.14595168754091617
4)
{0,1,2,3,2,1,1,7,0,9,10,11,12,13,14,15,16,17,18,14,9}
24
Returns: 0.3272154791654077
5)
{0,1,2,3,4,5,6,7,8,9,10}
50
Returns: 0.0

For this particular tree, the 50-th eagle will certainly have no place to sit.

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

Coding Area

Language: C++17 · define a public class EagleInZoo with a public method double calc(vector<int> parent, int K) · 68 test cases · 2 s / 256 MB per case

Submitting as anonymous