TopCoder problem "HeightRound" used in SRM 346 (Division I Level Two)



Problem Statement

    

There are several people that will sit around the same table in a circular fashion. Since all these people are very self-conscious about their height, you don't want to sit any short person next to a tall one. To formalize this, we want to minimize the maximum height difference between 2 adjacent persons.

You will be given the heights of the people as a int[]. Return a int[] with the height of each individual in clockwise order of a seating arrangement that follows the above rule. If there are several solutions, return the lexicographically first one.

 

Definition

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

Constraints

-heights will contain between 3 and 50 elements, inclusive.
-Each element of heights will be between 1 and 1000, inclusive.
 

Examples

0)
    
{1,2,3,4}
Returns: {1, 2, 4, 3 }
It's better to separate the tallest and shortest people in the round. All solutions with 1 and 4 separated are equivalent, so we choose the lexicographically first one.
1)
    
{1000,500,1}
Returns: {1, 500, 1000 }
In a round of only 3 persons, everybody is next to everyone else, so we only have to return the lexicographically first representation.
2)
    
{1,3,4,5,7}
Returns: {1, 3, 5, 7, 4 }
3)
    
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7682

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10670&pm=7682

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Dynamic Programming