I'm trying to understand the problem of AGGRCOW - Aggressive cows in Spoj. But how this output has come, I don't get it. First I thought maybe the distance between them like for this input:
Input: 5 3 1 2 4 8 9Ouput: 3
first we put, cow1 in position arr[0], then we put cow2 in arr[2]. We don't put cow2 in arr1 because then there will be no distance between them (2-1=1). Distance of cow2 and cow1 is 3 units now. So for that we put cow2 in arr[2]. And finally we put cow3 in arr[3] as distance between cow3 and cow2 is here 4. And then we compare this 3<4. This outputs 3.
But when I tried to apply same logic for this input:
Input: 6 3 2 3 4 5 8 9Ouput: 3
In my logic it should be 2. As if we keep cow1 in arr[0] and cow2 in arr[2] then distance is 4-2=2. And it's minimum. But when I want to see what should be the actual value by googling I found out that it is 3. I dont understand how it is 3. Why not 2? I just want the explanation of this problem, not the code.
The problem is that you are given N stall locations, a0 through aN-1. You must fill C of those, but so that the separation between the filled stall numbers is as high as possible. The output is the separation fulfilled by all filled stalls. That is, if you output 3, it means your solution says "I can fill in the stalls so that the distance between any two filled stalls is at least 3".
If you think about it, you really are looking at the minimum distance between any two filled stalls, and you are trying to maximize it, without compromising the distance to any other filled stalls. Thus: largest minimum distance.
The input is of form
N C
a0 a1 ... aN-2 aN-1
The second example is
6 3
2 3 4 5 8 9
meaning there are 6 stalls: 2, 3, 4, 5, 8, and 9, and three of them need to be filled, maintaining maximum separation between stall numbers.
The optimum solution is to use stalls 2, 5, and 9. The separations are then 5-2 = 3 and 9-5 = 4, and the result is the smallest of them, 3.