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
adi123cm: 2021-07-13 09:51:22

Not an easy problem don't worry if you get stuck
this is a very good variation of binary search where we have to binary search through a range of possible correct values and find the optimal one (in this case we need to find the optimal maximum minimum distance)

akshat047: 2021-06-29 18:41:12

I made it ;) never thought of this

nextman: 2021-06-24 18:51:41

@shubh3082 does it matter weather it is 8 or 9

Last edit: 2021-06-24 18:52:20
shubh3082: 2021-06-14 21:54:05

according to the problem we have to maximize the distance between the cows.
therefore the solution for the example should be 1 4 and 9???

astreak: 2021-06-14 17:41:20

Quite an easy problem i don't know why people make so fuss about it.

Last edit: 2021-06-14 17:41:46
rexfx: 2021-06-13 14:50:07

Poorly worded, although a good problem.

If anyone wants some starting point: first learn about binary search then go for advanced binary search.

EKO is also a similar problem

some may consider the paragraph below as a hint so read it only when you have tried understanding/solving the question for while but failed.

If you didnt understand the problem: you gotta maximize the distance between every (adjacent) cow and then finally choose the one which has the minimum value. Example: say you have 3 apples and 10 places to put them ( 1,2,3,4,5,6,7,8,9,10). If you place on 1,3,10 then distance between 1,3 is 2 whereas 3,10 is 7, but this case is not optimal. If you place on 1,5,10 then distance between 1,5 is 4 and 5,10 is 5, this is the max you can get between them simultaneously. Hence, you choose 4 as the ans because this is minimum after maximizing.

Last edit: 2021-06-13 15:00:59
av1choudhary: 2021-05-29 04:40:28

If your code is completely correct in your compiler still getting error in this complier, watch : https://youtu.be/BrhLrMeU5JA

av1choudhary: 2021-05-26 17:21:35

The God Question of Binary Search, if you are stuck or getting error. watch both part of this video
https://youtu.be/DF9VUEEvur8

Last edit: 2021-05-29 04:40:56
mayank2120: 2021-05-26 09:19:31

this problem was fun!!

nigurjar: 2021-05-12 12:01:49

@kimg but questions says "minimum distance between any two of them is as large as possible." so we have to maximise minimum distance. which can come at 5 if put at 9


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