ChainCity
SRM 718 · 2017-05-20 · by lg5293
Problem Statement
Chain City consists of n buildings on a straight line.
You are given the
Citizens can travel along the straight line 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 line, 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 Chain City can be defined as the maximum of all values d(X,Y). Your task is to minimize the diameter of Chain 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|+1, inclusive.
{3,5,4}
2
Returns: 4
The city is shown in the following picture: The blue points labeled A, B, C, D are the buildings. The two red points show one optimal placement of the two teleporters. For this placement of teleporters we have d(A,B) = 3, d(A,C) = 4, d(A,D) = 4, d(B,C) = 3, d(B,D) = 3, and d(C,D) = 4. The maximum of these values, and thus the diameter of Chain City, is 4. It can be shown that this solution is optimal.
{3,5,4}
3
Returns: 3
The buildings are in the same locations but now we may build three teleporters. One optimal solution is to build them at the same locations as the buildings B, C, and D.
{3,5,4}
4
Returns: 0
The only optimal solution for this test case is to build the four teleporters at the locations of the four buildings.
{1,1, 100, 1,1,1, 100, 1, 100, 1,1,1}
4
Returns: 3
As dist has 12 elements, there are 13 buildings. Let's call them A through M, in order. As we can see, the buildings form four "clusters": A+B+C, D+E+F+G, H+I, and J+K+L+M are four groups of buildings that are close to each other. One optimal placement of teleporters is to place the first one at building B, the second one halfway between E and F, the third one at building H, and the fourth one halfway between K and L.
{3,1,4,1,5,9,2,6,5,3,5}
4
Returns: 8
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChainCity with a public method int findMin(vector<int> dist, int k) · 128 test cases · 2 s / 256 MB per case