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
satylogin: 2016-03-26 19:53:55

must try...... loved this question

avulasaiharish: 2016-03-05 12:36:27

gud one!!!

ankur jaiswal: 2016-02-08 16:58:24

yes giriprasad kemburu he can put; infact its one of the solutions

ankurverma1994: 2016-02-03 16:00:32

Weak Test Cases
1
2 2
5 10
Answer should be 5 but 4 is also accepted. I think for C=2 there is no test case present in test file

codesmiler: 2016-01-25 19:10:39

Excellent Problem,looks hard but it is easy just read the topcoder binary search tutorial and solve this one

manas0008: 2016-01-25 11:23:11

It's definitely not as easy as it seems to be.Try to relate it with the example given in Topcoder binary search tutorial.Try the following testcases for confirmation.
input:
6
10 3
1 2 9 8 4 4 8 9 2 1
5 3
1 2 8 4 9
20 3
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
3 3
0 1000000000 500000000
20 4
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
20 5
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
output:
3
3
9
500000000
6
4

ibrahim5253: 2016-01-24 13:37:51

Really nice one and awesome tutorial on Topcoder

Devashish Mathur: 2016-01-21 06:42:05

Great Question..

try2catch: 2016-01-17 10:03:18

F*** -_- [2WA]- forgot to loop for test cases.
Awesome concept - made me understand the actual use of binary search - Simple Implementation
Must read - Topcoder Tutorial.

Junaid: 2015-12-23 19:49:23

I would say this is the best problem I have done on SPOJ till now..I took a whole day just to solve this one....but finally AC in one go...my 44th..:P...All THANKS to topcoder.....:)...highly recommended problem..


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