0
$\begingroup$

My doubt is related to the given SPOJ problem:

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?

I was able to come up with idea of using Binary Search but struggled with the positioning of the cows. After watching some solutions like this one , almost all of them were placing the first cow at the first stall stating its a greedy approach which works.

I am unable to understand what exactly are we being greedy about as what matters to us is the distance between the cows and not where the cows are placed(i.e we can place 3 cows in the two valid given orders where both give a minimum distance of 2 [1,4,6]and [4,6,10])so what is the necessity of placing the first cow at first position.

Also even if there is some reason behind this approach ,how does it guarantee that for a chosen distance dist if we can't place the given number of cows (the fist cow being placed at first stall)with dist as the minimum distance then there is no other way of placing the cows(the order in which placing starts from any stall) which would satisfy the conditions.

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose the choosen distance is dist. That is, the separation between every cow should be at least dist.

Suppose the stalls are at located at positions: $s_1, \dotsc,s_n$, in sorted order. And suppose there is a feasible solution that places the cows at stalls: $s_{l_{1}}, s_{l_{2}}, \dotsc, s_{l_{C}}$ (in sorted order) such that distance between cows is at least dist

Observation: In the above solution, if $s_{l_{1}} \neq s_1$, then we can always place the cow at location $s_1$; the distance between the cows will only increase. In other words, the solution stays feasible.

Therefore, there always exists a solution where a cow is placed at $s_1$ given dist is feasible.


Now, for the cow at $s_{l_{2}}$ you can shift it to the left till the distance between it and $s_{1}$ does not become less than dist. Use the above observation inductively, to see why this correct. The same logic holds for the subsequent cows. I leave the details to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.