JOIN
Get Time

   Problem Statement  

 Problem Statement for CircleCity

Problem Statement

    

Circle City consists of n buildings on a circle You are given the int[] dist with n elements. The elements of dist are the distances between adjacent buildings, in clockwise order around the circle.

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.)

 

Definition

    
Class:CircleCity
Method:findMin
Parameters:int[], int
Returns:int
Method signature:int findMin(int[] dist, int k)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{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.
1)
    
{3,5,4}
3
Returns: 0
We can build the three teleporters right at the three buildings.
2)
    
{1,2,3,4,5,6,5,4,3,2,1}
5
Returns: 5
3)
    
{1, 100, 1,1,1, 100, 1, 100, 1,1,1, 100, 1}
4
Returns: 3
4)
    
{3,1,4,1,5,9,2,6,5,3,5,8,9,7}
6
Returns: 8
5)
    
{
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000
}
7
Returns: 9000000

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 718 Round 1 - Division I, Level Two