Statistics

Problem Statement for "DistancePermutation"

Problem Statement

Limak has a tree with N vertices that are numbered 0 through N-1. He wants to find a treasure that is hidden in one random vertex. Each vertex is equally likely to contain the treasure.

Every vertex contains a detector that Limak can use to get the distance to the vertex with the hidden treasure.

Limak is going to use the detectors in a random order (each of N! orders is equally likely), and he will stop immediately when he is sure where the treasure is. Can you find the expected value of the number of used detectors?

You are given the int[] parent of length N-1 that describes the tree. For every i between 1 and N-1 inclusive, vertices i and parent[i-1] are connected by an edge.

Let X denote the expected value of the number of detectors Limak will use. It can be proved that X*N*(N!) is an integer. Find and return (X*N*(N!)) modulo 1,000,000,007.

Definition

Class:
DistancePermutation
Method:
solve
Parameters:
int[]
Returns:
int
Method signature:
int solve(int[] parent)
(be sure your method is public)

Notes

  • The distance between two vertices is the number of edges on the shortest path between them.

Constraints

  • N will be between 1 and 50, inclusive.
  • parent will contain exactly N-1 elements.
  • For every valid i, parent[i] will be between 0 and i, inclusive.

Examples

  1. {0}

    Returns: 4

    The tree consists of two vertices connected by an edge. It's always enough to use one detector. If it displays the distance 0, the treasure is in our current vertex. If it displays the distance 1, the treasure is in the other vertex. The expected value of the number of detectors used is 1 and multiplying it by N*(N!) gives the answer 4.

  2. {0,0}

    Returns: 22

    There are three vertices and the edges are 0-1 and 0-2. If Limak first uses a detector in vertex 1 or vertex 2, the displayed distance will be 0, 1 or 2, and Limak will immediately determine where the treasure is. If the first used detector is in vertex 0 and it displays distance 0, the treasure must be in this vertex. But if the distance is 1, Limak needs one more detector to say which of the other two vertices contains the treasure. Using two detectors is necessary only if Limak first uses a detector in vertex 0 and the treasure is in vertex 1 or vertex 2. The probability of that is 1/3 * 2/3 = 2/9. The expected value of the number of used detectors is 7/9 * 1 + 2/9 * 2 = 11/9. The answer is 11/9 * 3 * (3!) = 22.

  3. {0,1}

    Returns: 22

  4. {0,0,0}

    Returns: 174

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

    Returns: 61008

  6. {}

    Returns: 0

  7. {0,1,2}

    Returns: 120

  8. {0,0,2,0,1,2,2}

    Returns: 863280

  9. {0,0,0,0,0,0,0,0,0,0}

    Returns: 391379186

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

    Returns: 587860494

  11. {0,0,2,2,4,2,5,6,2,6,2,9,12,7,4,12,12,15}

    Returns: 472356442

  12. {0,0,2,2,3,2,3,2,0,4,1,8,2,2,11,4,14,13,0,15,18,6,17,6}

    Returns: 488505245

  13. {0,1,1,3,2,2,3,3,3,3,9,9,3,0,14,2,7,16,17,19,4,12,1,6,16,13,20,13,26,2,2,13,22,15,33,32,15,11,22}

    Returns: 531683434

  14. {0,0,0,3,1,2,2,2,2,9,3,10,5,5,6,12,2,16,11,5,14,14,21,12,19,10,17,11,11,14,27,31,20,22,23,19,35,3,1,33,9,23,40,33,36,1,10,0}

    Returns: 489808532

  15. {0,0,1,2,0,0,5,0,1,3,7,3,12,8,9,8,12,9,14,2,19,8,3,19,12,2,11,23,6,26,21,14,13,7,21,31,1,37,35,0,19,22,3,19,12,25,22,28,41}

    Returns: 367451031

  16. {0,1,1,2,0,5,0,7,7,1,1,5,1,8,5,1,8,10,18,12,4,20,18,13,6,5,26,13,2,0,23,9,13,19,8,28,34,13,7,26,0,35,10,26,36,7,16,37,37}

    Returns: 371610884

  17. {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}

    Returns: 374381031

  18. {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 576995391

  19. {0,1,2,3,4,5,6,7,7,9,9,10,12,13,13,15,15,17,18,18,20,21,22,22,24,23,24,27,26,28,28,31,32,32,34,34,36,35,38,39,39,38,39,41,43,45,43,45,46}

    Returns: 115355001

  20. {0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,0,1,1,0,1,0,1,1,1,1,1,2,1,0,2,1,2,0,2,0,3,1,0,2,3,0,2,3,0,0,3,3}

    Returns: 957080348

  21. {0,0,0,1,0,1,2,2,1,3,1,1,0,3,2,0,2,5,3,2,4,0,2,6,5,5,0,3,2,7,3,5,1,8,2,1,7,11,6,11,8,9,6,9,11,8,12,9}

    Returns: 161805272

  22. {0,1,2,2,3,4,6,6,7,9,8,11,12,10,12,13,16,13,14,15,20,18,19,19,23,19,26,20,22,24,29,22,25,33,30,26,30,30,35,32,32,34,29,31,44,33,40,38}

    Returns: 430169954

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

    Returns: 16375689

  24. {0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}

    Returns: 684561486

  25. {0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46}

    Returns: 211519335

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

    Returns: 544123157

  27. {0, 1, 2, 2, 0, 3, 1, 3, 7, 3, 0, 11, 4, 9, 5, 12, 8, 4, 1, 11, 1, 12, 7, 8, 23, 22, 10, 0, 15, 15, 29, 31, 31, 11, 20, 12, 2, 2, 20, 20, 39, 35, 17, 9, 37, 9, 30, 10, 25 }

    Returns: 794129072

  28. {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 }

    Returns: 374381031

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: