Statistics

Problem Statement for "EagleInZoo"

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.

Definition

Class:
EagleInZoo
Method:
calc
Parameters:
int[], int
Returns:
double
Method signature:
double calc(int[] parent, int K)
(be sure your method is public)

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

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

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

  3. {0,1,0,3}

    4

    Returns: 0.75

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

    20

    Returns: 0.14595168754091617

  5. {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

  6. {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.

  7. {0,1,2,3,4,4,6,4,3,9,9,2,12,13,14,15,16,16,16,19,20,21,21,21,15,25,26,27,25,25,15,14,32,13,34,12,2,37,1,0,0}

    58

    Returns: 0.1052714062207359

  8. {0,0,2,3,4,5,6,7,6,9,10,4,0,13,14,15,14,13,18,19,20,21,22,23,22,25,21,21,28,20}

    7

    Returns: 0.7036420824759945

  9. {0,1,1,3}

    20

    Returns: 7.2479248046875E-5

  10. {0,1,2,3,4,4,6,7,6,9,4,3,0,0}

    96

    Returns: 0.029121983544255357

  11. {0,0,2,3,0,5}

    57

    Returns: 2.9550837998309543E-8

  12. {0,1,2,2,4,5,4,4,8,2}

    62

    Returns: 0.002968153779120004

  13. {0,1,2,3,4,5,6,6,8,9,10,11,11,13,9,15,8,17,18,19,20,21,21,20,24,17,26,27,27,26,30,8,2,33,33,35,0,0,38,39,40,40,42,43,43,45,42,38,0}

    58

    Returns: 0.16535624471407717

  14. {0,1,2,2,4,1,6,7,0,9,10,10,12,13,14,15,16,14,10,9,20,21,20,23,24,23,26,27,26}

    22

    Returns: 0.42712730685153477

  15. {0,1,1,3,0,5,6,7,8,8,10,11,12,13,13,13,13,11,18,7,20,0,22,23,23,22,22,0}

    39

    Returns: 0.1674162758354731

  16. {0,1,2,3,4,5,6,5,5,3,10,3,3,13,13,15,16,16,18,15,20,21,22,22,24,25,26,26,28,25,15,31,15,33,13,2,0,37,37,39,39}

    2

    Returns: 1.0

  17. {0,1,2,3,4,5,6,7,7,9,6,11,12,13,13,15,16,13,5,19,20,21,22,23,24,21,26,26,28,28,21,4,32,3,2,1,36,1,0,0,40,40}

    28

    Returns: 0.12130607451764344

  18. {0,1,2,3,4,5,5,7,7,4,10}

    49

    Returns: 0.002139217887667877

  19. {0,0,2,2,2,5}

    42

    Returns: 0.001785991821932218

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

    95

    Returns: 0.002589690881719664

  21. {0,1,2,3,4,5,6,7,8,7,4,11,12,11,11,1,16,16,18,18,20,18,22}

    59

    Returns: 0.0331289319273807

  22. {0,1,2,1,4,5,6,7,5,5,10,11,12,13,11,5,16,17,18,19,19,19,22,16,16,1,26,26,28,29}

    93

    Returns: 0.06362426128920899

  23. {0,0,2,3,4,5,3,7,8,9,10,11,12,12,14,10,16,16,18,8,20,7,22,23,24,24,2,0,28,29,30,29,32,28,0}

    34

    Returns: 0.20228528747031832

  24. {0,1,2,3,4,5,6,7,7,3,2,11,12,13,14,15,15,14,18,19,20,21,22,20,19,14,26,27,28,29,28,31,28,12,34,35,36,37,35,2}

    40

    Returns: 0.3263540124443032

  25. {0,1,2,3,4,5,6,5,8,8,10,11,12,13,13,11,5,5,18,19,20,21,22,23,4,25,1,27,28}

    33

    Returns: 0.1790967560179286

  26. {0,1,2,3,2,5,6,7,8,9,10,11,8,7,14,15,15,14,6,19,20}

    75

    Returns: 0.05921567391904919

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

    30

    Returns: 0.0

  28. {0,1,0,3,4,5,6,7,3,0,10,10,12,12,14}

    3

    Returns: 1.0

  29. {0,1,2,3,1,0,6,7,8,9,10,11,12,13,11,15,16,17,18,19,20,21,21,21,24,25,11,9,28,29,8,8,32,32,34,35,36,37,38,39,37,34,32,8,44,44}

    54

    Returns: 0.1598860447263894

  30. {0,1,2,3,4,5,6,7,8,8,10,10,12,13,7,15,15,7,5}

    14

    Returns: 0.4223108278544024

  31. {0,1,2,3,1,5,1,7,8,9,10,10,12,13,14,13,7,17,18,1,20,1,0,23,0,25,26,26,26,25,30,31,32,33,31,31,36,37,38,37,40}

    43

    Returns: 0.28337237311442853

  32. {0,1,1,3,4,5,5,7,8,9,10,8,12,13,14,7,16,17,18,19,18,21,7,23,24,25,26,26,4,4}

    67

    Returns: 0.08393923359475255

  33. {0,1,2,1,4,5,6,7,8,9,10,11,9,7,14,15,16,17,18,7,20,21,20,6,24,25,6,5,28,28,30,31,30,28,5,35,36}

    35

    Returns: 0.22510335390387837

  34. {0,1,2,3,4,2,6,7,6,9,10,11,6,13,14,15,13,13,18,19,20,20,22,2,1,25,26,27,28,29,30,31,29,26,34,35,36,37,36,35,40,41,41,34,25}

    35

    Returns: 0.3473128147872441

  35. {0,1,2,1,4,5,6,7,8,9,7,6,5,4,14,15,16,14,18,14,1,21,0,23,24,25,26,27,28,27,25,31,32,32,34,35,34,37,24,23,0}

    85

    Returns: 0.13626700668476346

  36. {0,1,2,3,4,5,6,5,8,9,10,10,12,9,14,15,5,17,18,19,19,21,4,3,2,25,1}

    54

    Returns: 0.06775129598212615

  37. {0,1}

    42

    Returns: 0.0

  38. {0,1,2,3,4,2,6,7,0,9,10,10,12,10,14,15,16,17,18,19,19,21,22,23,24,23,26,23,23,21,19,17,32,16,34,35,36,16,38,38,40,41,15,14,0,45,46,45,48,48}

    86

    Returns: 0.03708159456191915

  39. {0,1,2,3,4,5,5,5,2,2,10}

    46

    Returns: 0.007992159359363584

  40. {0,0,2,2,4,5,5,4,8,8,10,11,12,12,14,15,15,17,12,11,8}

    24

    Returns: 0.1753468099359878

  41. {0,1,2,1,1,5,6,7,8,9,8,11,8,6,6,15,16,16,5,19}

    45

    Returns: 0.10867490386202548

  42. {0,1,1,3,4,5,6,7,8,9,10,9,12,12,7,15,7,17,0}

    27

    Returns: 0.23514256945631984

  43. {0,1,0,0,4,5,6,7,0,9,10}

    23

    Returns: 0.1158373249916167

  44. {0,1,2,3,3,2,6,1,8,9,10,9,12,0,14,15}

    55

    Returns: 0.021234425469527633

  45. {0,1,2,0,4,5,6,6,8,9,9,11,6,6,14,15,16,17,16,19,19,21,15,15,15,14,6,6,6,4,30,31,32,32}

    65

    Returns: 0.08727290176655848

  46. {0,1,2,3,4,5,6,3,8,9,10,11,12,11,9,15,2,17,18,19,20,20,0}

    10

    Returns: 0.5017603896558285

  47. {0,1,2,3,4,5,5,2,1,9,10,11,12,13,14,13,16,12,12,11,20,0}

    58

    Returns: 0.09672959642886864

  48. {0,1,1,1,4,5,6,7,8,9,10,10,10,10,14,15,16,17,16,19,20,7,22,6,24,24,26,27,28,29,30,27,32,32,34,26,36,36,38,39,40,41,42,42,42,45,46,4,4}

    66

    Returns: 0.09296381764990953

  49. {0,1,2,3,4}

    59

    Returns: 0.0

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

    85

    Returns: 7.936403372854712E-5

  51. {0,1,2,3,4,3,2,7,7,2,10,10,2,0}

    67

    Returns: 0.02222406199759509

  52. {0,0,2,3,4,5,5,7,7,3,10,10,12,13,14,12,3,2}

    34

    Returns: 0.14441649076842836

  53. {0,0,2,3,4,4,6,7,3,9,10,11,12,13,14,15,16,17,18,15,20,20,22,23,20,25,26,27,27,26,26,31,32,31,31,31,25,11,38,39,3,41,42,43,41}

    3

    Returns: 0.75

  54. {0,1,2,1}

    10

    Returns: 0.03515625

  55. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    100

    Returns: 0.13808783412614872

  56. {0, 0, 1, 1, 2, 4, 4, 4, 5, 5, 6, 6 }

    20

    Returns: 0.14595168754091617

  57. {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24 }

    100

    Returns: 0.089127757873776

  58. {0, 0, 1, 1, 0, 4, 3, 6, 3, 3, 0, 0, 2, 2, 4, 0, 12, 2, 3, 17, 8, 13, 7, 5, 15, 7, 5, 2, 20, 16, 4, 9, 16, 11, 7, 1, 30, 36, 24, 4, 22, 37, 15, 39, 34, 15, 34, 1, 34, 8 }

    58

    Returns: 0.19029268069134986

  59. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    50

    Returns: 0.0

  60. {0, 0 }

    3

    Returns: 0.5

  61. {0, 0, 1, 1, 2, 4, 4, 4, 5, 5, 5, 6 }

    20

    Returns: 0.1676582362275291

  62. {0, 1, 0, 3, 4, 4, 0, 5, 5, 7, 4, 6, 3, 5, 3, 10, 11, 3, 8, 11, 12, 0, 18, 17, 23, 12, 15, 5, 25, 15, 27, 28, 24, 26, 33, 29, 2, 16, 32, 30, 37, 11, 3, 11, 31, 27, 17, 28, 24, 31 }

    100

    Returns: 0.10301436774600216

  63. {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

  64. {0, 0, 1, 2, 2, 4, 4, 4, 5, 5, 8, 9 }

    20

    Returns: 0.22020939326074163

  65. {0 }

    1

    Returns: 1.0

  66. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    100

    Returns: 0.0836473792103422

  67. {0, 1, 1, 0, 4, 4, 5, 6, 7, 4, 7, 5, 11, 13, 1, 11, 3, 8, 1, 16, 9, 18, 15, 9, 17, 6, 6, 12, 27, 5, 22, 30, 20, 12, 14, 4, 26, 3, 31, 14, 3, 39, 18, 17, 33, 18, 7, 31, 29, 18 }

    100

    Returns: 0.11117249727091198

  68. {0, 1, 0, 3 }

    4

    Returns: 0.75

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: