AGGRCOW - Aggressive cows


Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1 ... xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

t – the number of test cases, then t test cases follows.
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

For each test case output one integer: the largest minimum distance.

Example

Input:

1
5 3
1
2
8
4
9

Output:

3

Output details:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8,
resulting in a minimum distance of 3.


hide comments
sid_somani: 2017-06-30 20:29:14

Nice BS question. If not getting an idea, I suggest you to read the quora thread on this question.

addy1397: 2017-06-29 20:34:50

Last edit: 2017-06-29 20:35:02
shubham_1234: 2017-06-29 12:50:09

Nice bs to practice
AC in One go

tusharuppal: 2017-06-23 15:38:18

nice qn to practice binary search...
just don"t think complex..
ac in 2nd go ;-)

satvik007: 2017-06-14 06:48:19

my algorithms runs with complexity O(c*(log n)^2). Although I am getting ac with that. I want to know if this problem can be solved better than that.

sanny_1: 2017-06-13 09:58:26

Really very good problem to understand binary search!!! Thanks Topcoder and Codechef....

sunidhi: 2017-06-08 21:37:16

i cant understand the question.don't want to know the logic .just explain the question with more test cases.

leafbebop: 2017-05-31 15:32:47

Note for golang: There is a binary search func available in standard lib sort.

arvind002: 2017-05-26 18:09:02

_/\_..I took around 5-6 hours just to solve this one.

Last edit: 2017-05-26 18:12:26
prashant_351: 2017-05-26 15:14:45

Great problem ! Must read topcoder tutorial on binary search before attempting this.

Last edit: 2017-05-26 15:15:34

Added by:Roman Sol
Date:2005-02-16
Time limit:2s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:USACO February 2005 Gold Division