Statistics

Problem Statement for "FoxesOfTheRoundTable"

Problem Statement

There are n foxes, numbered 0 through n-1. You are given a int[] h with n elements. The elements of h are the heights of those foxes. Your task is to arrange all foxes around a round table.

Given an arrangement of foxes, let D be the largest height difference between adjacent foxes. For example, suppose that four foxes with heights { 10, 30, 20, 40 } sit around the table in this order. The height differences are |10-30|=20, |30-20|=10, |20-40|=20, and |40-10|=30. (Note that the last fox is also adjacent to the first one, as this is a round table.) Then, the value D is max(20,10,20,30) = 30.

Find an arrangement of the given foxes for which the value D is as small as possible. Return a permutation of foxes that describes your arrangement. I.e., return a int[] with n elements: the numbers of foxes in order around the table. If there are multiple optimal solutions, you may return any of them.

Definition

Class:
FoxesOfTheRoundTable
Method:
minimalDifference
Parameters:
int[]
Returns:
int[]
Method signature:
int[] minimalDifference(int[] h)
(be sure your method is public)

Constraints

  • h will contain between 3 and 50 elements, inclusive.
  • Each element in h will be between 1 and 1,000, inclusive.

Examples

  1. {1,99,50,50}

    Returns: {0, 3, 1, 2 }

    In the optimal solution the foxes with heights 1 and 99 mustn't be adjacent. Hence, the heights of foxes have to be 1, 50, 99, 50, in this cyclic order, and the optimal value of D is 49. One permutation that produces this order of foxes is 0, 3, 1, 2.

  2. {123,456,789}

    Returns: {0, 1, 2 }

    Whatever we do, the result will always be 789-123.

  3. {10,30,40,50,60}

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

    The permutation {0, 1, 4, 3, 2 } specifies that the heights of foxes are in the following order: 10, 30, 60, 50, 40.

  4. {1,2,3,4,8,12,13,14 }

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

  5. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 }

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

  6. {923,710,408,75,205,194,73,869,895,522,149,720,946,934,754,65,766,73,300,949,593,8,369,583}

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

  7. {345,391,624,121,488,28,132,306,744,62,682,688,680,845,276,481,611,30,465,343,325,337,999,813,579,613,292,354,50,386,679,645,106,199,379,650,684,133,84,939,426,732,60,267,439,669,1000,167}

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

  8. {97,649,523,427,15,109}

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

  9. {159,439,724,82,906,127,88,308,793,7,506,855,533,754,501,572,716,333,838,892,724,256,146,48,544,262,665,568}

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

  10. {888,241,64,927,398,342,57,881,528,753,972,2,522,575,109,462,839,259,69,99,87,222,111,243,492,78,680,385,969,125,297,576}

    Returns: {11, 2, 25, 19, 22, 21, 23, 30, 27, 15, 12, 13, 26, 16, 0, 28, 10, 3, 7, 9, 31, 8, 24, 4, 5, 17, 1, 29, 14, 20, 18, 6 }

  11. {948,510,1000,158,639,364,274,576,186,311,886,320,812,737}

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

  12. {492,795,794,190,990,953,684,759,801,742,422,609,395,229,300,760,396,251,285,888,766,893,213,507,956,658,539,59,280,306,597,937,408,516,251,62,177,350,306,911,847,872,563,542}

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

  13. {490,235,23,887,640,883,528,910,234,482,277,543,65,554,490,155,223,680,395,772,455,696}

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

  14. {121,581,969,149,552,598,605,561,771,195,588,557,70,530,785,440,919,102,581,480,303,536,698,267,104,278,970,167,328,874,66,15,773,822,265,119,857,512,38,466,41,248,449,594,584,497,919,31,529,943}

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

  15. {515,692,590,69,598,696,492,892,318,75,200,511,610,422,98,618,742,269,364,260,409,133,794,736,29,22,46,430,63,651,55,129,56,191,979,209,579,603}

    Returns: {25, 26, 32, 3, 14, 21, 10, 19, 8, 20, 27, 11, 36, 4, 12, 29, 5, 16, 7, 34, 22, 23, 1, 15, 37, 2, 0, 6, 13, 18, 17, 35, 33, 31, 9, 28, 30, 24 }

  16. {396,416,38,550,936}

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

  17. {532,208,53,138,546,68,193,357,728,824}

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

  18. {799,607,144,908,182,302,510,859,741,608,312,344,889,208,754,499,229,32,438,622,242}

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

  19. {265,424,699,168,999,667,240,609}

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

  20. {201,577,980,383,163,621,673,458,977,179,934,428,217,98,1000,873,121,564,362,839,903,744,724,923,652,320,480,694}

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

  21. {32,737,257,146,1,109,356,985,268,61,597,589,18,490,95,947,892,642,529,711,967,123,889,261,106,472,920,258,99,777,384,259,598,712,899,286,751,753}

    Returns: {4, 0, 14, 24, 21, 2, 31, 8, 6, 25, 18, 10, 17, 33, 36, 29, 16, 26, 20, 7, 15, 34, 22, 37, 1, 19, 32, 11, 13, 30, 35, 23, 27, 3, 5, 28, 9, 12 }

  22. {80,595,241,166,630,106,387,474}

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

  23. {544,903,769,83,180,972,189,927,824,7,536,128,170,917,461,888,154,773,971,237,941,393,829,670,961,326,486,868,331,690,955,63,981,494,953,119,220,749,961,812,353,532,593,912,406,9,246,315,571,568}

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

  24. {447,489,836,82,661,848,836,652,671,780,559,325,72,253,768,218}

    Returns: {12, 15, 11, 1, 7, 8, 9, 6, 5, 2, 14, 4, 10, 0, 13, 3 }

  25. {607,925,896}

    Returns: {0, 1, 2 }

  26. {198,884,229,928,110,191,521,756,539,155,238,892,980,611,572,404,86,698,72,7,46,641,61,259,222,717,11,699,596,156,375,508,751,850,124,26,396,159,697,267,168,692,866,220,575,806,995,467}

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

  27. {481,466,373,457,608,805,592,177,972,628,700,645,428,176,990,292,780,804,653,110,329,411,728,387,51,250,607,631,532,744,170,9,160,867,399,613,157,892,256,758,574,606,811,784,210,770}

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

  28. {685,506,271,856,302,907,465,395,12,977,887,829,711,389,369,977,727,120,850,318,313,544,354,649,189,970,96,74,942,769,326,494,681,965,676,749,58,896}

    Returns: {8, 27, 17, 2, 20, 30, 14, 7, 31, 21, 34, 0, 16, 29, 18, 10, 5, 33, 9, 15, 25, 28, 37, 3, 11, 35, 12, 32, 23, 1, 6, 13, 22, 19, 4, 24, 26, 36 }

  29. {45,979,317,280,495,717,306,121,640,324,848,535,890,399,976,384,620,350,248,258}

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

  30. {623,159,403,716,921,733,412,43,666,550,430,364,111,400,782,579,451,931,173,287,698,545,123,12,141,990,333,233,240,370,564,53,762,156,25,54,94,561,182,50,456,918}

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

  31. {561,281,890,751,587,751,471,631,334,167,747,357,874,620,145,18,537,676,6,335,81,569,633,144,844,77,842,770,378,186,767,321}

    Returns: {18, 25, 23, 9, 1, 8, 11, 6, 0, 4, 7, 17, 3, 30, 26, 12, 2, 24, 27, 5, 10, 22, 13, 21, 16, 28, 19, 31, 29, 14, 20, 15 }

  32. {321,858,629,389,194,159,758,109,867,933,757,806,348,490,413,258,898,396,362,188,754,646,873,942,337,607,736,3,194,961,319,750,343,321,936,227,859,946,50,156,592,223,460,663,877,633,192}

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

  33. {498,261,590,342,230,114,251,349}

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

  34. {297,953,733,710,86,481,398,883,862,198,867,28,649,92,772,716,610,841,436}

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

  35. {437,954,716,420,657,434,879,181}

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

  36. {14,351,372,992,140,208,7,284,102,468,597,314,25,679,251,500,771,395,273,262,892,183,384,23,692,987,727,815,926,736,527,1}

    Returns: {31, 0, 12, 4, 5, 19, 7, 1, 22, 9, 30, 13, 26, 16, 20, 25, 3, 28, 27, 29, 24, 10, 15, 17, 2, 11, 18, 14, 21, 8, 23, 6 }

  37. {613,907,179,490,901}

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

  38. {633, 675, 555, 98, 853, 461, 399, 808, 544, 567, 91, 991, 681, 155, 374, 904, 606, 119, 346, 126, 154, 153, 11, 598, 899, 817, 728, 795, 335, 21, 172, 967, 47, 727, 416, 251, 539, 815, 411, 82, 381, 501, 424, 414, 656, 798, 317, 261, 916, 662 }

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

  39. {1, 2, 3, 4, 8, 12, 13, 14, 22, 30, 38, 46, 54, 62, 70, 78, 86, 92, 100, 108, 116, 124, 132, 140, 148, 156, 164, 22, 30, 38, 46, 54, 62, 70, 78, 86, 92, 100, 108, 116, 124, 132, 140, 148, 156, 164, 172 }

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

  40. {11, 15, 29, 31, 4, 15, 4, 74, 21, 22, 14, 25, 23, 11, 61, 53, 12, 23 }

    Returns: {4, 0, 16, 1, 8, 12, 11, 3, 14, 7, 15, 2, 17, 9, 5, 10, 13, 6 }

  41. {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, 49, 50 }

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

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

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

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

    Returns: {0, 2, 4, 6, 8, 10, 11, 9, 7, 5, 3, 1 }

  44. {10, 20, 25, 5 }

    Returns: {3, 1, 2, 0 }

  45. {468, 335, 501, 170, 725, 479, 359, 963, 465, 706, 146, 282, 828, 962, 492, 996, 943, 828, 437, 392, 605, 903, 154, 293, 383, 422, 717, 719, 896, 448, 727, 772, 539, 870, 913, 668, 300, 36, 895, 704, 812, 323, 334, 674 }

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

  46. {250, 74, 659, 931 }

    Returns: {1, 2, 3, 0 }

  47. {137, 601, 235, 30, 1, 261, 62, 530, 625, 273, 401, 570, 614, 187, 476, 366, 658, 245, 148, 14, 177, 675, 452, 388, 219, 433, 644, 318, 693, 206, 335, 90, 582, 559, 106, 494, 722, 47, 418, 707, 354, 300, 118, 543, 513, 75, 160, 289, 376, 464 }

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

  48. {724, 742, 530, 779, 317, 36, 191 }

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

  49. {163, 263, 711, 396, 345, 12, 611, 189, 117, 529, 190, 59, 241, 269, 862, 813, 853, 189, 153, 451, 41, 766, 370, 773, 339, 820, 309, 459, 3, 97, 482, 412, 962, 153, 661, 559, 738, 341, 342 }

    Returns: {28, 20, 29, 18, 0, 17, 12, 13, 24, 38, 22, 31, 27, 9, 6, 2, 21, 15, 16, 32, 14, 25, 23, 36, 34, 35, 30, 19, 3, 4, 37, 26, 1, 10, 7, 33, 8, 11, 5 }

  50. {289, 224, 387, 659, 225, 573, 489, 761, 678 }

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

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

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

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

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

  53. {990, 597, 749, 536, 760, 658, 274, 777, 114, 894, 447, 487, 827, 859, 296, 299, 12, 169, 440, 845, 592, 647, 307, 613, 202, 495, 63, 789, 994, 338, 527, 731, 667, 253, 51, 107, 204, 916, 416, 432, 353, 243, 911, 331, 605, 452, 685, 548, 606, 834 }

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

  54. {52, 64, 86, 34 }

    Returns: {3, 1, 2, 0 }

  55. {24, 85, 55, 57, 41, 67, 77, 32, 9, 45, 40, 27 }

    Returns: {8, 11, 10, 9, 3, 6, 1, 5, 2, 4, 7, 0 }

  56. {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 4, 2 }

    Returns: {0, 1, 2, 4, 6, 8, 9, 7, 5, 3, 10, 11 }

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: