Base Stations (APCS 2017-03 Expert)

To support the trend toward informatization and digitalization, a mayor wants to provide wireless network service at some service points in the city, so the mayor asks a telecommunications company to build wireless base stations. One telecommunications company is responsible for N service points. These N service points are located on a straight avenue, and their positions (coordinates) are represented by the distances P[i] from one end of the avenue, where i=0 to N-1. Because of equipment customization and maintenance, every base station must have the same service range. After a base station is built, every service point whose distance from this base station is at most R (called the radius of the base station) can use the wireless network service. That is, each base station can serve a range of D=2R (called the diameter of the base station). The telecommunications company now wants to compute the minimum diameter required so that, if K base stations are built, every service point can be served.

The location of a base station does not have to be a service point, and the best construction location may not be unique. In this problem, you only need to find the minimum diameter. The following is an example with N=5, where the five service-point coordinates are 1, 2, 5, 7, and 8.

0    1    2    3    4    5    6    7    8    9
     ^    ^              ^         ^    ^

If K=1, the minimum diameter is 7. The base station can be built at coordinate 4.5, and the distance from every point to the base station is within radius 3.5. If K=2, the minimum diameter is 3: one base station serves the points at coordinates 1 and 2, while the other base station serves the other three points. When K=3, a diameter of 1 is sufficient.

Input Format

The input has two lines. The first line contains two positive integers N and K, separated by a single space. The second line contains N nonnegative integers P[0], P[1], ..., P[N-1], representing the positions of the N service points. These positions are separated by single spaces. Note that these N positions are not guaranteed to be distinct and are not guaranteed to be sorted. In this problem, K<N, and all coordinates are integers. Therefore, the minimum diameter is necessarily an integer not less than 1.

Output Format

Output the minimum diameter. Do not output any extra words or spaces, and end with a newline.

Sample Input 1

5 2
5 1 2 8 7

Sample Output 1

3

Sample Input 2

5 1
7 5 1 2 8

Sample Output 2

7

Scoring

The input contains several test cases. The time limit for each test case is 2 seconds. Points are awarded according to the number of correctly passed test cases:

Subtask 1 is worth 10 points: the coordinate range is at most 100, and 1 <= K <= 2, K < N <= 10.

Subtask 2 is worth 20 points: the coordinate range is at most 1000, and 1 <= K < N <= 100.

Subtask 3 is worth 20 points: the coordinate range is at most 1000000000, and 1 <= K < N <= 500.

Subtask 4 is worth 50 points: the coordinate range is at most 1000000000, and 1 <= K < N <= 50000.

Source

APCS implementation contest, March 4, 2017, problem 4, "Base Stations". See the official APCS past-problem PDF and ZeroJudge c575.