Statistics

Problem Statement for "OneEntrance"

Problem Statement

There are N rooms in Maki's new house. The rooms are numbered from 0 to N-1. Some pairs of rooms are connected by bidirectional passages. The passages have the topology of a tree. That is, there are exactly N-1 of them and it is possible to go from any room to any other room by following some sequence of passages.

You are given two int[]s a and b that describe the passages. For each valid i, there is a passage that connects the rooms a[i] and b[i]. You are also given an int s. The house has exactly one entrance from the outside, and the entrance leads to the room s.

Niko is helping Maki move into the new house. Maki has exactly N pieces of furniture. The pieces are numbered from 0 to N-1. Niko will carry them into the house in this order. Each piece of furniture must be placed into a different room. Maki does not care which piece goes where, each of the N! permutations is allowed.

However, not all of those N! permutations are actually possible. This is because the furniture is large. As soon as a room contains a piece of furniture, it is impossible to move other pieces through this room. Thus, Niko must place the furniture carefully. Formally, she can place a new piece of furniture into the room x if and only if all rooms on the (unique) path between s and x, including s and x, are still empty. Niko is smart and she will always place the furniture in such a way that she never gets stuck. Thus, at the end each of Maki's rooms will contain exactly one piece of furniture.

Calculate and return the number of ways how the furniture can be arranged in Maki's house at the end.

Definition

Class:
OneEntrance
Method:
count
Parameters:
int[], int[], int
Returns:
int
Method signature:
int count(int[] a, int[] b, int s)
(be sure your method is public)

Constraints

  • N will be between 1 and 9, inclusive.
  • a and b will contain exactly N-1 elements each.
  • Each element of a and b will be between 0 and N-1, inclusive.
  • The graph described by a and b will be a tree.
  • s will be between 0 and N-1, inclusive.

Examples

  1. {0, 1, 2}

    {1, 2, 3}

    0

    Returns: 1

    There is only one solution: Niko must fill the rooms in the order {3,2,1,0}. Thus, piece number 0 will end in room 3, piece number 1 in room 2, and so on.

  2. {0, 1, 2}

    {1, 2, 3}

    2

    Returns: 3

    In this case Niko can choose one of three orders: {3,0,1,2}, {0,3,1,2}, or {0,1,3,2}. Note that the room with the entrance (in this case, room 2) always gets the last piece of furniture.

  3. {0, 0, 0, 0}

    {1, 2, 3, 4}

    0

    Returns: 24

  4. {7, 4, 1, 0, 1, 1, 6, 0}

    {6, 6, 2, 5, 0, 3, 8, 4}

    4

    Returns: 896

  5. {}

    {}

    0

    Returns: 1

    Maki's new house has only one room.

  6. {6,8,0,7,4,4,1,3}

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

    3

    Returns: 640

  7. {6,1,8,2,0,6,3,1}

    {0,6,6,5,7,5,4,3}

    0

    Returns: 480

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

    {0,8,7,6,0,0,1,3}

    0

    Returns: 2520

  9. {4,2,6,6,2,0,8,7}

    {2,5,1,7,3,2,7,3}

    0

    Returns: 126

  10. {2,8,8,4,8,6,1,8}

    {3,0,4,5,2,7,8,7}

    0

    Returns: 630

  11. {6,6,7,7,6,8,4,5}

    {2,0,3,6,1,2,8,7}

    6

    Returns: 2240

  12. {0,4,4,7,3,3,4,5}

    {3,6,1,8,7,2,3,7}

    5

    Returns: 280

  13. {2,3,4,1,8,6,1,1}

    {8,5,5,4,0,4,8,7}

    0

    Returns: 105

  14. {7,6,2,1,1,2,4,1}

    {1,3,0,8,4,6,5,0}

    1

    Returns: 840

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

    {3,8,8,7,5,2,6,8}

    1

    Returns: 84

  16. {2,0,1,6,7,0,5,1}

    {8,7,3,4,4,2,4,6}

    3

    Returns: 5

  17. {7,0,1,2,6,5,0,5}

    {4,6,8,8,5,8,4,3}

    8

    Returns: 280

  18. {6,3,6,4,6,5,1,8}

    {2,6,0,7,4,7,6,7}

    5

    Returns: 168

  19. {6,3,0,8,8,1,0,4}

    {1,1,5,3,2,7,8,2}

    2

    Returns: 240

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

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

    0

    Returns: 560

  21. {4,1,5,0,5,7,8,1}

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

    5

    Returns: 192

  22. {1,3,2,0,0,6,8,0}

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

    5

    Returns: 336

  23. {7,3,6,2,3,4,2,6}

    {1,2,3,1,4,5,8,0}

    5

    Returns: 45

  24. {8,6,4,2,5,0,7,3}

    {4,0,0,4,0,1,8,7}

    1

    Returns: 168

  25. {7,8,0,4,7,4,1,3}

    {5,1,7,6,4,8,2,2}

    1

    Returns: 224

  26. {8,1,0,3,3,3,7,0}

    {5,5,5,8,4,7,2,6}

    8

    Returns: 630

  27. {5,4,6,6,0,2,4,7}

    {0,6,8,3,6,8,1,0}

    0

    Returns: 1680

  28. {6,6,2,1,7,0,8,1}

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

    2

    Returns: 2520

  29. {7,4,6,8,3,2,5,8}

    {2,1,5,1,5,0,8,0}

    8

    Returns: 1120

  30. {5,6,3,3,5,0,8,1}

    {6,8,2,4,0,7,3,5}

    8

    Returns: 336

  31. {5,1,6,1,3,2,1,8}

    {1,4,5,0,4,4,7,3}

    6

    Returns: 90

  32. {6,6,0,6,4,6,3,8}

    {7,1,5,5,6,8,6,2}

    5

    Returns: 2880

  33. {8,8,7,2,7,8,5,1}

    {3,6,5,5,0,7,1,4}

    4

    Returns: 48

  34. {8,0,5,8,1,5,1,1}

    {4,7,4,3,0,6,4,2}

    4

    Returns: 1260

  35. {6,0,7,0,4,5,6,2}

    {5,3,1,1,3,8,1,1}

    6

    Returns: 560

  36. {0,7,7,4,2,6,1,4}

    {7,8,5,8,5,8,7,3}

    7

    Returns: 2520

  37. {8,2,6,0,7,3,5,1}

    {0,4,8,4,2,0,3,0}

    3

    Returns: 480

  38. {3,8,8,6,5,2,8,7}

    {7,0,6,1,4,4,2,2}

    3

    Returns: 45

  39. {2,4,1,8,5,6,3,2}

    {0,2,0,7,8,8,7,6}

    2

    Returns: 504

  40. {0,6,5,4,7,8,0,6}

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

    3

    Returns: 288

  41. {0,1,3,3,6,3,0,6}

    {4,4,2,7,3,8,2,5}

    6

    Returns: 240

  42. {4,2,0,8,4,3,8,1}

    {7,1,3,6,8,4,5,6}

    1

    Returns: 120

  43. {0,8,0,1,0,3,3,5}

    {2,1,7,6,4,7,5,8}

    6

    Returns: 2

  44. {8,1,4,6,4,7,6,2}

    {3,4,3,3,5,0,0,5}

    4

    Returns: 672

  45. {4,8,2,8,0,4,5,3}

    {1,6,1,2,1,7,2,8}

    5

    Returns: 210

  46. {6,4,6,6,6,6,2,0}

    {1,5,8,3,5,7,8,8}

    8

    Returns: 3360

  47. {7,7,5,8,0,5,2,2}

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

    6

    Returns: 24

  48. {4,0,0,6,1,1,0,6}

    {3,8,7,5,0,3,2,0}

    2

    Returns: 420

  49. {2,8,2,4,4,3,5,4}

    {7,2,4,6,1,4,2,0}

    6

    Returns: 1260

  50. {6,6,5,2,4,7,3,6}

    {5,8,1,8,8,8,8,0}

    0

    Returns: 504

  51. {1,8,3,1,6,4,3,7}

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

    5

    Returns: 480

  52. {7,8,2,6,3,0,2,8}

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

    0

    Returns: 1260

  53. {5,6,7,4,6,8,3,8}

    {1,4,4,2,1,6,8,0}

    4

    Returns: 1120

  54. {7,0,3,6,5,6,7,7}

    {1,1,7,4,8,1,5,2}

    3

    Returns: 315

  55. {3,0,7,0,5,8,1,5}

    {1,7,2,1,6,4,4,1}

    0

    Returns: 840

  56. {4,6,3,6,1,2}

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

    3

    Returns: 1

  57. {1,3,1,0}

    {4,4,2,2}

    3

    Returns: 1

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

    {3,0,4,3,4,1}

    0

    Returns: 90

  59. {0,3,1}

    {1,1,2}

    1

    Returns: 6

  60. {0,4,3,4,3}

    {5,2,4,0,1}

    0

    Returns: 15

  61. {3,2,3}

    {2,1,0}

    1

    Returns: 1

  62. {4,2,3,4,3}

    {0,4,2,5,1}

    0

    Returns: 4

  63. {1}

    {0}

    1

    Returns: 1

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

    {5,5,4,4,3}

    2

    Returns: 1

  65. {0,3,2,1}

    {4,0,3,4}

    4

    Returns: 4

  66. {0,3,2}

    {3,1,1}

    1

    Returns: 3

  67. {6,4,3,1,4,0}

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

    5

    Returns: 15

  68. {4,2,3,1}

    {0,3,4,4}

    4

    Returns: 12

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

    {0,4,5,0,0}

    5

    Returns: 30

  70. {1,0,0,4,1,6}

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

    4

    Returns: 15

  71. {2,2,0}

    {1,0,3}

    0

    Returns: 3

  72. {0,1,2}

    {1,3,0}

    0

    Returns: 3

  73. {3,3,3,3,4,5}

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

    5

    Returns: 90

  74. {2,2,1}

    {3,0,3}

    1

    Returns: 1

  75. {1,1,0}

    {2,3,2}

    2

    Returns: 3

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

    {2,3,4,4,1,3}

    0

    Returns: 4

  77. {1,0,4,1}

    {3,3,1,2}

    1

    Returns: 12

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

    {3,0,4,4,4,4}

    6

    Returns: 60

  79. {2,0,2}

    {3,2,1}

    3

    Returns: 2

  80. {4,2,1,1,0}

    {1,3,3,5,3}

    4

    Returns: 8

  81. {6,3,6,2,5,1}

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

    5

    Returns: 24

  82. {0,1}

    {2,2}

    0

    Returns: 1

  83. {4,3,1,2}

    {3,0,0,0}

    0

    Returns: 12

  84. {1,0,3,4}

    {4,2,4,2}

    1

    Returns: 3

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

    {0,5,4,0,3}

    2

    Returns: 15

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

    {1,4,3,2,5}

    5

    Returns: 15

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

    {6,6,0,0,2,4}

    6

    Returns: 20

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

    {5,4,4,5,0}

    5

    Returns: 20

  89. {3,4,2,1,2}

    {5,5,0,5,4}

    1

    Returns: 4

  90. {0,1,0,3,4}

    {5,2,2,4,1}

    1

    Returns: 10

  91. {1,4,1,2}

    {0,0,3,1}

    3

    Returns: 3

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

    {1,4,3,2,0}

    2

    Returns: 15

  93. {5,0,5,3,4}

    {1,5,4,1,2}

    1

    Returns: 15

  94. {1,2,3}

    {0,0,2}

    1

    Returns: 1

  95. {3,0,2}

    {2,1,1}

    2

    Returns: 3

  96. {4,5,5,2,0,0}

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

    2

    Returns: 30

  97. {0,2,3}

    {1,1,1}

    3

    Returns: 2

  98. {1,5,4,0,4}

    {4,3,5,5,2}

    4

    Returns: 40

  99. {0,0}

    {1,2}

    1

    Returns: 1

  100. {2,0}

    {1,1}

    2

    Returns: 1

  101. {0,0,0,0,0,0,0,0}

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

    0

    Returns: 40320

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

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

    4

    Returns: 70

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

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

    8

    Returns: 1

  104. {7, 4, 1, 0, 1, 1, 6, 0 }

    {6, 6, 2, 5, 0, 3, 8, 4 }

    4

    Returns: 896

  105. {0, 1, 2 }

    {1, 2, 3 }

    2

    Returns: 3

  106. {0, 0, 0, 3, 3, 3, 3, 6 }

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

    0

    Returns: 3360

  107. {0, 1, 2 }

    {1, 2, 3 }

    1

    Returns: 3

  108. {0, 0, 1, 1 }

    {1, 2, 3, 4 }

    0

    Returns: 8

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: