Milestones | Topcoder Archive

Problem Statement

A straight road goes from city A to city B. The length of the road is d miles. There are n milestones along the road, located at distance p[0], p[1], ..., p[n-1] from city A.

You must keep exactly k milestones and remove the others. You would like to do this in such a way that the maximal distance between two adjacent milestones, or a city and the closest milestone, is as small as possible.

Return the minimal possible maximal distance.

Definition

Class:: Milestones
Method:: maxDistance
Parameters:: int, int[], int
Returns:: int
Method signature:: int maxDistance(int d, int[] p, int k)
(be sure your method is public)

Constraints

d will be between 1 and 100,000, inclusive.
p will contain between 1 and 50 elements, inclusive.
Each element in p will be between 1 and d - 1, inclusive.
Elements of p will form a strictly ascending sequence.
k will be between 1 and the number of elements in p, inclusive.

Examples

```
10
```
```
{4,5}
```
```
1
```
```
Returns: 5
```
You must keep one of the milestones. If you keep milestone 0, the distance between city A and the milestone will be 4, and the distance between the milestone and city B will be 6. The maximal distance in this case is 6. If you keep milestone 1, the distances are 5 and 5, respectively, and the maximal distance is 5. The second option is better, so the answer is 5.
```
7
```
```
{1,2,3,4,5,6}
```
```
2
```
```
Returns: 3
```
For example, you can keep milestones at 2 and 5.
```
30
```
```
{7,15,23}
```
```
2
```
```
Returns: 15
```
```
26416
```
```
{12654}
```
```
1
```
```
Returns: 13762
```

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)2024, Topcoder, Inc. All rights reserved.