TopCoder problem "TeamPhoto" used in SRM 167 (Division I Level Two)



Problem Statement

    It's time to line up for the team photo. We want all the team members, plus the head coach and the two assistant coaches to be in the photo. We want the head coach in the middle and the two assistant coaches on the two ends. But we don't want to have much disparity in heights between adjacent people.

Let's line up to minimize the sum of the absolute height differences of adjacent people. If there is an even number of people, the coach can go in either center position. Create a class TeamPhoto that contains method minDiff that takes int[] height, the heights of all the people, and returns the minimum possible sum of adjacent absolute height differences.

height lists the coach first, then the two assistant coaches, then the team members.

 

Definition

    
Class:TeamPhoto
Method:minDiff
Parameters:int[]
Returns:int
Method signature:int minDiff(int[] height)
(be sure your method is public)
    
 

Constraints

-height has between 5 and 50 elements inclusive
-each element of height is between 10 and 100 inclusive
 

Examples

0)
    
{80,82,81,50,90,65}
Returns: 79
The coach has a height of 80 and must be in one of the two middle positions, with the assistant coaches (82 and 81) on the two ends. The best lineup is 81,65,50,80,90,82 with the minDiff calculated as |81-65| + |65-50| + |50-80| + |80-90| + |90-82| = 79. There are other ways to achieve this minDiff.
1)
    
{70,82,91,50,50,50,50,50,50}
Returns: 113
Line up in the order 82,50,50,50,70,50,50,50,91
2)
    
{13, 17, 11, 12, 10}
Returns: 10
One optimal way to line up is 17, 12, 13, 10, 11 making the sum of the absolute differences 5 + 1 + 3 + 1 = 10

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4640&pm=1614

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Advanced Math, Sorting