Statistics

Problem Statement for "VampireTree"

Problem Statement

You are a genealogist specializing in family trees of vampires. Vampire family trees differ from human family trees. In particular, vampires are "born" in a different way. The only way to create a new vampire is that an existing vampire turns a living human into a new vampire. Whenever this happens, we say that the older vampire is the master and the newly created vampire is the servant of that master.

Given a particular family of vampires, the distance between two vampires is the smallest number of steps along the family tree we need to make in order to get from one vampire to the other. Formally, in each step you can move from the current vampire to any of its servants, or to its master (if it has one). Note that for each vampire V the distance between V and V is zero.

You are now studying one particular family of vampires. These vampires have all been created from a single vampire: the True Ancestor. This special vampire has no master. You know that there are n vampires in the family, and you have numbered them 0 through n-1 (in no particular order).

You do not know the master/servant relationships between the vampires in the family. The only information you have is a int[] num with n elements. For each valid i, the following statement is true: "If vampire i is the True Ancestor, he has exactly num[i] servants. Otherwise, he has exactly (num[i] - 1) servants."

Consider all valid family trees that are consistent with this information. If there are no such trees, return -1. Otherwise, find and return the maximum distance between any two vampires in any of those family trees. (In other words, for each of the corresponding trees determine the maximum distance, and return the maximum of those maximums.)

Definition

Class:
VampireTree
Method:
maxDistance
Parameters:
int[]
Returns:
int
Method signature:
int maxDistance(int[] num)
(be sure your method is public)

Constraints

  • num will contain between 2 and 20 elements, inclusive.
  • Each element of num will be between 1 and n-1, inclusive.

Examples

  1. {1, 2, 1}

    Returns: 2

    One possible solution is that vampire 1 is the True Ancestor, and vampires 0 and 2 are its servants.

  2. {2, 2, 2}

    Returns: -1

    At least two of the vampires must have two servants, but there needs to be at least 5 vampires for such a situation to happen (excluding the True Ancestor).

  3. {1, 1, 1, 1, 4}

    Returns: 2

  4. {1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}

    Returns: -1

  5. {1,1}

    Returns: 1

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

    Returns: -1

  7. {1,1,1}

    Returns: -1

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

    Returns: -1

  9. {14,18,2,3,5,8,18,5,15,2,17,14,7,17,7,3,2,9,1,15}

    Returns: -1

  10. {9,12,7,12,11,1,5,10,2,3,2,14,13,7,2}

    Returns: -1

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

    Returns: 12

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

    Returns: 11

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

    Returns: 7

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

    Returns: 7

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

    Returns: 4

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

    Returns: 7

  17. {1,3,1,1,2,3,2,1,2}

    Returns: 6

  18. {1,1,2,3,1,2,3,1,2,3,2,3,2,2,1,1,2}

    Returns: 12

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

    Returns: 12

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

    Returns: 10

  21. {1,2,2,1}

    Returns: 3

  22. {3,1,1,2,2,2,1,2}

    Returns: 6

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

    Returns: 11

  24. {1,1,3,1}

    Returns: 2

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

    Returns: 10

  26. {1,1,2}

    Returns: 2

  27. {2,1,1}

    Returns: 2

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

    Returns: 10

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

    Returns: 7

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

    Returns: 14

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

    Returns: 11

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

    Returns: 12

  33. {4,5,2,2,1,1,2,1,2,3,2,2,1,1,2,1,2,1,1}

    Returns: 12

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

    Returns: 13

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

    Returns: 11

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

    Returns: 12

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

    Returns: 13

  38. {3,2,1,1,3,1,2,1,3,1,3,2,1,2,3,1,3,1}

    Returns: 11

  39. {2,2,1,2,1,1,2,1,3,2,2,1,2,3,2,2,1,3,3,2}

    Returns: 15

  40. {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1}

    Returns: 19

  41. {19,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 2

  42. {3,5,4,2,2,3,3,1,1,3,1,2,1,1,1,1,1,1,1,1}

    Returns: 10

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

    Returns: 10

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

    Returns: 10

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

    Returns: 10

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

    Returns: 10

  47. {1, 1 }

    Returns: 1

  48. {2, 2, 2, 2, 2, 2, 2, 1, 1 }

    Returns: 8

  49. {1, 1, 1, 1, 1 }

    Returns: -1

  50. {1, 2, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 2, 1 }

    Returns: 11

  51. {7, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 9

  52. {1, 2, 2 }

    Returns: -1

  53. {1, 1, 2, 2, 2 }

    Returns: 4

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

    Returns: 10

  55. {19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 2

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

    Returns: 8

  57. {1, 1, 1, 1, 2 }

    Returns: -1

  58. {1, 2, 1, 1, 2, 1, 2 }

    Returns: -1

  59. {1, 1, 2, 2 }

    Returns: 3

  60. {1, 1, 1 }

    Returns: -1

  61. {4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 6

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

    Returns: 14

  63. {1, 1, 2, 2, 2, 2 }

    Returns: 5

  64. {2, 2, 1 }

    Returns: -1

  65. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 19 }

    Returns: 2

  66. {4, 2, 2, 2, 1, 1, 1, 1 }

    Returns: 5

  67. {1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4 }

    Returns: 11

  68. {3, 3, 3, 1, 1, 1, 1, 1 }

    Returns: 4

  69. {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2 }

    Returns: 19

  70. {1, 2, 2, 2, 1 }

    Returns: 4

  71. {3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 8

  72. {2, 1, 1, 1 }

    Returns: -1

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: