Connection Status:
Competition Arena > TeamPhoto

TeamPhoto

SRM 167 · 2003-10-14 · by dgoodman

SRM 167 · 2003-10-14 · by dgoodman · Advanced Math, Sorting
Class Name: TeamPhoto
Return Type: int
Method Name: minDiff
Arg Types: (vector<int>)
Problem Statement

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.

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)
{10,100,30,22,23,24,25,26,27,28,29,30,31,32}
Returns: 110
3)
{100,30,10,22,23,24,25,26,27,28,29,30,31,32}
Returns: 164
4)
{30,10,100,22,23,24,25,26,27,28,29,30,31,32}
Returns: 94
5)
{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

Submissions are judged against all 93 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TeamPhoto with a public method int minDiff(vector<int> height) · 93 test cases · 2 s / 256 MB per case

Submitting as anonymous