Connection Status:
Competition Arena > CircleDance

CircleDance

SRM 244 · 2005-05-23 · by logged

SRM 244 · 2005-05-23 · by logged · Greedy
Class Name: CircleDance
Return Type: int
Method Name: arrangeDancers
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Given a group of dancers' heights, arrange a circle formation that minimizes the maximum height difference between each pair of neighboring dancers. Write a class CircleDance with a method arrangeDancers that takes a int[], heights, and returns the maximum height difference between neighboring dancers.

Constraints

  • heights will contain between 3 and 20 elements inclusive.
  • Each element of heights will be between 150 and 210 inclusive.
Examples
0)
{180,183,178,185}
Returns: 5

The dancers may be arranged in a circle like this: 180 / \ 185 178 \ / 183 Their height differences are shown below: 180 (5)/ \(2) 185 178 (2)\ /(5) 183 The maximum difference is 5. Other arrangements may not lead to an optimal solution. For example, the following one has a maximum difference of 7: 180 (3)/ \(2) 183 178 (2)\ /(7) 185

1)
{170,180,190}
Returns: 20

Any arrangement is equivalent to the following one: 180 (10)/ \(10) 170 - 190 (20) So the result is 20.

2)
{180,180,180,180,180}
Returns: 0
3)
{184,165,175,186,192,200,176,192,194,168,205,201}
Returns: 10
4)
{155,192,169,162,174,155,180,184,150,180,192,198,199}
Returns: 14

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

Coding Area

Language: C++17 · define a public class CircleDance with a public method int arrangeDancers(vector<int> heights) · 46 test cases · 2 s / 256 MB per case

Submitting as anonymous