| Submit | All submissions | Best solutions | Back to list |
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.
| 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 |
hide comments
|
||||||||||||||
|
2025-03-28 19:34:14
@geek_abhi Question - Why are we always picking the first position in the sorted array? Answer - The first value in the sorted array is the leftmost stall possible. So the distance between the first value will be maximum wrt any stall [idx], where idx > 0. So imagine, [2 3 5 6 8......] as an array and min distance is 4. if you choose '3' you will have to place the next cow at 8. But if you choose '2' you can place the next cow at '6' , saving you 1 position. I understand your question tho, obv it is not required to choose the first idx and there will be ample amount of arrangements that are possible(will fit with the given criteria of AT LEAST min distance X) even if you don't start with the first value in the array. But I think it isn't always possible to figure out an arrangement in every case if you start with any index other than 0th, given you have to find the arrangement in O(N) TIME. Starting with first value will ALWAYS give you one of many arrangements possible, as it is the leftmost/smallest value possible. NOTE - You don't have to count the number of arrangements or find any optimal arrangement (such as every adjacent cow is at a min distance = X, instead of at least x). You need one arrangement to figure out if it is possible with the current min distance 'X' |
||||||||||||||
|
2025-03-28 19:10:53
Here's a tip for people finding the problem statement confusing. You can read it in 2 ways - 1) Can I place C cows into N stalls, given the minimum distance between any 2 cows should at least be 'X'. 2) Does an arrangement exist, given C cows and N stalls, such that the minimum distance between any cow is at least 'X'. NOTE - Don't focus on how many different arrangements are possible, you just need to find out 1 arrangement with the given min 'X'. You have to maximise the value of 'X', till it becomes impossible to place all the cows. As the minimum distance increase, you will need more stalls to place ALL the cows. |
||||||||||||||
|
2025-03-05 18:01:12
I wish I never come back to this platform |
||||||||||||||
|
2025-02-20 15:07:56
had to refer to some video, but a cool problem!! |
||||||||||||||
|
2025-02-20 06:20:33
WORST |
||||||||||||||
|
2025-01-29 08:49:43
use binary search on the answer as it is monotonic and try to figure out the logic if a particular value can be answer or not |
||||||||||||||
|
2025-01-13 18:49:24
very bad site ever |
||||||||||||||
|
2024-12-27 07:21:40
the platform seriously needs to be updated, like I cannot even see problem while writing the code. Maybe it was intentional anyways, nice problem |
||||||||||||||
|
2024-08-27 14:58:02
This platform is pretty shit. |
||||||||||||||
|
2024-07-23 13:56:31
Nice problem! |
||||||||||||||
RSS