Statistics

Problem Statement for "TheBrickTowerMediumDivTwo"

Problem Statement

John and Brus just built some towers using toy bricks. They now have n towers numbered 0 through n-1. For each i, the height of the i-th tower (0-based index) is given in heights[i].

John and Brus want to arrange their towers into a line. That is, the bottoms of the towers will all stand on the same line. John and Brus don't like it when a tower falls down and knocks over another tower while falling. To avoid this, they have to put their towers sufficiently far apart. More precisely, the distance between any two neighboring towers must be at least equal to the maximum of their heights. John and Brus would like to minimize the distance between the first and the last tower in the line.

You are given the int[] heights. Return a int[] containing exactly n elements: the order in which the towers should be placed on the line. For each i, the i-th element of the return value should be the number of the tower that will be placed i-th on the line. If there is a tie (multiple solutions give the same minimal distance), return the lexicographically smallest order.

Definition

Class:
TheBrickTowerMediumDivTwo
Method:
find
Parameters:
int[]
Returns:
int[]
Method signature:
int[] find(int[] heights)
(be sure your method is public)

Notes

  • A int[] A is lexicographically smaller than a int[] B if it contains a smaller element at the first position where these int[]s differ.

Constraints

  • heights will contain between 1 and 7 elements, inclusive.
  • Each element of heights will be between 1 and 47 inclusive.

Examples

  1. {4, 7, 5}

    Returns: {0, 2, 1 }

    There are six possible orderings, but only four of them have optimal distance 12 between the first and the last towers: {0, 2, 1} {1, 0, 2} {1, 2, 0} {2, 0, 1} Among these orderings {0, 2, 1} is the lexicographically smallest one.

  2. {4, 4, 4, 4, 4, 4, 4}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

    Towers may have equal heights.

  3. {2, 3, 3, 2}

    Returns: {0, 3, 1, 2 }

    Towers of height 2 have to be neighboring in the optimal ordering.

  4. {13, 32, 38, 25, 43, 47, 6}

    Returns: {0, 6, 3, 1, 2, 4, 5 }

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

    Returns: {0, 1, 4, 5, 2, 6, 3 }

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

    Returns: {0, 4, 5, 1, 6, 2, 3 }

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

    Returns: {0, 1, 2, 3, 6, 5, 4 }

  8. {3, 13, 28, 32, 24, 18, 23}

    Returns: {0, 1, 5, 6, 4, 2, 3 }

  9. {30, 19, 8, 13, 25, 1}

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

  10. {4, 23, 38, 20}

    Returns: {0, 3, 1, 2 }

  11. {30}

    Returns: {0 }

  12. {10, 16, 47, 8}

    Returns: {0, 3, 1, 2 }

  13. {13, 32, 38, 25, 43, 47, 6}

    Returns: {0, 6, 3, 1, 2, 4, 5 }

  14. {21, 10, 43, 43, 37, 30}

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

  15. {19, 37, 37, 33, 42, 36, 27}

    Returns: {0, 6, 3, 5, 1, 2, 4 }

  16. {10, 10, 46, 4}

    Returns: {0, 1, 3, 2 }

  17. {44, 6}

    Returns: {0, 1 }

  18. {44, 20, 19, 37, 14, 31, 29}

    Returns: {0, 1, 2, 4, 6, 5, 3 }

  19. {1, 2, 3, 4, 5, 6, 7}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

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

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  21. {3, 13, 28, 32, 24, 18, 23}

    Returns: {0, 1, 5, 6, 4, 2, 3 }

  22. {25, 30, 8, 32, 13, 1, 19}

    Returns: {0, 2, 5, 4, 6, 1, 3 }

  23. {16, 35, 35, 22, 29, 10, 24}

    Returns: {0, 5, 3, 6, 4, 1, 2 }

  24. {45, 17, 33, 41, 17, 12, 17}

    Returns: {0, 1, 4, 5, 6, 2, 3 }

  25. {40, 29, 31, 24, 13, 12, 3}

    Returns: {0, 1, 3, 4, 5, 6, 2 }

  26. {40, 12, 22, 15, 21, 22, 17}

    Returns: {0, 1, 3, 6, 4, 2, 5 }

  27. {31, 25, 34, 40, 38, 28, 37}

    Returns: {0, 1, 5, 2, 6, 4, 3 }

  28. {30, 27, 34, 25, 32, 11, 13}

    Returns: {0, 1, 3, 5, 6, 4, 2 }

  29. {27, 25, 16, 36, 11, 46, 15}

    Returns: {0, 1, 2, 4, 6, 3, 5 }

  30. {16, 37, 3, 21, 16, 44, 18}

    Returns: {0, 2, 4, 6, 3, 1, 5 }

  31. {47, 47, 47, 47, 47, 47, 47}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  32. {46, 44, 44, 46, 46, 45, 47}

    Returns: {0, 1, 2, 5, 3, 4, 6 }

  33. {47, 47, 45, 44, 47, 44, 44}

    Returns: {0, 1, 2, 3, 5, 6, 4 }

  34. {44, 44, 46, 45, 47, 44, 47}

    Returns: {0, 1, 5, 3, 2, 4, 6 }

  35. {44, 46, 46, 46, 45, 47, 44}

    Returns: {0, 6, 4, 1, 2, 3, 5 }

  36. {8, 8, 8, 8, 8, 9, 9}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  37. {9, 8, 9, 9, 9, 8}

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

  38. {9, 9, 8, 9}

    Returns: {0, 1, 2, 3 }

  39. {9, 9, 9, 9}

    Returns: {0, 1, 2, 3 }

  40. {8, 8, 9, 9, 8, 9, 9}

    Returns: {0, 1, 4, 2, 3, 5, 6 }

  41. {24}

    Returns: {0 }

  42. {13}

    Returns: {0 }

  43. {24, 18}

    Returns: {0, 1 }

  44. {30, 45}

    Returns: {0, 1 }

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

    Returns: {0, 1, 2, 3, 4, 5, 6 }

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

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

  47. {2, 2, 2, 3, 2, 3}

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

  48. {13, 32, 38, 25, 43, 47, 6 }

    Returns: {0, 6, 3, 1, 2, 4, 5 }

  49. {4, 7, 5 }

    Returns: {0, 2, 1 }

  50. {20, 47, 10, 47, 30, 47, 1 }

    Returns: {0, 2, 6, 4, 1, 3, 5 }

  51. {43, 42, 44, 42, 44, 43, 42 }

    Returns: {0, 1, 3, 6, 5, 2, 4 }

  52. {3, 2, 1 }

    Returns: {0, 1, 2 }

  53. {2, 3, 3, 2 }

    Returns: {0, 3, 1, 2 }

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

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

  55. {3, 4, 2, 1 }

    Returns: {0, 2, 3, 1 }

  56. {4, 3, 3 }

    Returns: {0, 1, 2 }

  57. {7, 6, 5, 4, 3, 2, 1 }

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  58. {8, 5, 3, 4, 8, 5, 9 }

    Returns: {0, 1, 2, 3, 5, 4, 6 }

  59. {39, 44, 30, 19, 45, 40, 10 }

    Returns: {0, 2, 3, 6, 5, 1, 4 }

  60. {2, 2, 1 }

    Returns: {0, 1, 2 }

  61. {13, 32, 38, 8, 43, 47, 6 }

    Returns: {0, 3, 6, 1, 2, 4, 5 }

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

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  63. {22, 32, 12, 25, 43, 47, 6 }

    Returns: {0, 2, 6, 3, 1, 4, 5 }

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

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  65. {5, 4, 3, 2 }

    Returns: {0, 1, 2, 3 }

  66. {1 }

    Returns: {0 }

  67. {13, 6, 25, 32, 38, 43, 47 }

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  68. {7, 5, 4 }

    Returns: {0, 1, 2 }

  69. {4, 2, 3, 10, 46, 46, 12 }

    Returns: {0, 1, 2, 3, 6, 4, 5 }

  70. {3, 2, 1, 4 }

    Returns: {0, 1, 2, 3 }

  71. {15, 14, 13, 12, 11, 10, 7 }

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  72. {8, 5, 6, 7, 9, 10 }

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

  73. {14, 12, 6, 12, 31, 42 }

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

  74. {5 }

    Returns: {0 }

  75. {4, 3, 1, 2 }

    Returns: {0, 1, 2, 3 }

  76. {45, 43, 25, 17, 5, 4 }

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

  77. {4, 3, 2, 1 }

    Returns: {0, 1, 2, 3 }

  78. {4, 7, 5, 2, 9, 1 }

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

  79. {47, 46, 46 }

    Returns: {0, 1, 2 }

  80. {39, 40, 38, 41 }

    Returns: {0, 2, 1, 3 }

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

    Returns: {0, 1, 2, 3, 4 }

  82. {30 }

    Returns: {0 }

  83. {7, 5, 3 }

    Returns: {0, 1, 2 }

  84. {38, 25, 13, 6, 32, 43, 46 }

    Returns: {0, 1, 2, 3, 4, 5, 6 }

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

    Returns: {0, 3, 4, 2, 1 }

  86. {3, 3, 2, 2 }

    Returns: {0, 1, 2, 3 }

  87. {4 }

    Returns: {0 }

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

    Returns: {0, 1, 2, 3, 4 }

  89. {13, 6, 6, 13 }

    Returns: {0, 1, 2, 3 }

  90. {3, 3, 2 }

    Returns: {0, 1, 2 }

  91. {4, 7, 5, 1, 1, 1 }

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

  92. {40, 1, 40, 1 }

    Returns: {0, 1, 3, 2 }

  93. {9, 7, 2, 2, 2 }

    Returns: {0, 1, 2, 3, 4 }

  94. {32, 13, 38, 25, 43, 47, 6 }

    Returns: {0, 1, 6, 3, 2, 4, 5 }

  95. {23, 34, 12, 1, 5, 7, 18 }

    Returns: {0, 2, 3, 4, 5, 6, 1 }

  96. {4, 4, 3, 3, 2, 2 }

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

  97. {5, 5, 4, 5, 6, 1, 7 }

    Returns: {0, 1, 2, 5, 3, 4, 6 }

  98. {13, 32, 38, 25, 43, 6, 6 }

    Returns: {0, 5, 6, 3, 1, 2, 4 }

  99. {10, 12, 11, 6, 5, 5, 5 }

    Returns: {0, 3, 4, 5, 6, 2, 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: