SPOJ.com - Problem AGGRCOW

AGGRCOW - Aggressive cows

#binary-search

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:

Output:

Output details:

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	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
	sakshamtomar29: 2021-05-11 13:31:29 Great binary search problem!
	sandhuz: 2021-05-02 22:28:50 I recommend first do book allocation problem and here is its explanation: https://www.youtube.com/watch?v=2JSQIhPcHQg Similar ques here: EASY https://www.spoj.com/problems/EKO/ Once you done it give a try to this one if any difficulties here is link for explanation: https://www.youtube.com/watch?v=SiE1XFhYoaA
	sharan0105: 2021-04-06 21:47:50 I actually saw a solution to solve this problem but this problem just tells you to what extent binary search can be used
	makhan_28: 2021-03-18 06:00:38 The concept which is applied in this problem is mind blowing!! great problem, got to learn so much :)
	winner13: 2021-03-16 20:10:07 good question Last edit: 2021-03-16 20:10:41

Submit solution!

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