CircleCity
SRM 718 · 2017-05-20 · by lg5293
Problem Statement
Circle City consists of n buildings on a circle
You are given the
Citizens can travel along the circle in both directions. Their speed is one unit of distance per second. You would now like to help them get around the city faster by building k teleporters. Once you do so, it will be possible to travel between any two teleporters in zero time.
For the purpose of this problem, both buildings and teleporters are considered points. Teleporters can be built anywhere on the circle, possibly at non-integer coordinates. A teleporter may share its location with a building.
For any pair of buildings X and Y, let d(X,Y) be the shortest time a person will need to get from X to Y (or vice versa). The diameter of Circle City is defined to be the maximum of all values d(X,Y). Your task is to minimize the diameter of Circle City. Find an optimal way to place the teleporters and compute and return the corresponding value of the diameter. (It can be shown that the optimal diameter will always be an integer.)
Constraints
- dist will contain between 2 and 2,000 elements, inclusive.
- Each element of dist will be between 1 and 10^6, inclusive.
- k will be between 2 and |dist|, inclusive.
{3,5,4}
2
Returns: 3
Here is a picture of the above scenario: The blue dots are the three buildings. The two red circles show one optimal placement of the two teleporters. One teleporter is exactly at the location of building C, the other is between A and B, and its distance from A is 0.6. For this placement of teleporters we have d(A,B) = 3, d(A,C) = 0.6, and d(B,C) = 2.4. Hence, the current diameter is 3. It can be shown that this is optimal.
{3,5,4}
3
Returns: 0
We can build the three teleporters right at the three buildings.
{1,2,3,4,5,6,5,4,3,2,1}
5
Returns: 5
{1, 100, 1,1,1, 100, 1, 100, 1,1,1, 100, 1}
4
Returns: 3
{3,1,4,1,5,9,2,6,5,3,5,8,9,7}
6
Returns: 8
Submissions are judged against all 132 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CircleCity with a public method int findMin(vector<int> dist, int k) · 132 test cases · 2 s / 256 MB per case