FoxesOfTheRoundTable
SRM 662 · 2015-06-30 · by cgy4ever
Problem Statement
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
Constraints
- h will contain between 3 and 50 elements, inclusive.
- Each element in h will be between 1 and 1,000, inclusive.
Statement by TopCoder, Inc. — view the original on the archive.
{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.
{123,456,789}
Returns: {0, 1, 2 }
Whatever we do, the result will always be 789-123.
{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.
{1,2,3,4,8,12,13,14 }
Returns: {0, 1, 2, 3, 5, 6, 7, 4 }
{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 }
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoxesOfTheRoundTable with a public method vector<int> minimalDifference(vector<int> h) · 56 test cases · 2 s / 256 MB per case