Greed

Well I didn't manage to completely solve a SPOJ problem today, what a shame. I managed to think of a method of attack but didn't have the time or motivation to try and code it up or even write pseudo-code. The problem statement can be found here, since I don't want to accidentally leave out any details.

The method I am going to try combines a binary search and greedy algorithm.
First create a sorted array of all the locations of the stalls, then a second array that will keep track of which stalls have cows. Call these arrays A and B respectively. Through out my explanation assume that both arrays are always sorted. Now if you only have 2 cows you place them in the extreme left and right stalls, so add these stalls to B. The general idea is that the best location for cow (N+1) can be built from the best location for cow N. For example, to add the third cow look at the stall that is "half-way " between the 2 stalls with cows. Is the minimum distance at this point less than if you were to move it left or right by one stall? If so add this stall to B. If not do the same thing by looking at the midpoint of the left and right halves (some case work might be able to be applied to minimize this but I haven't thought about it yet). After doing this you can find the best spot for the third cow. To add the 4th cow look at the "interval" between cows 1 and 3, and the interval between cows 3 and 2, and apply the above method.

I haven't really considered the time constraint and input sizes but I might be able to get away with a linear search for the best spot (though I doubt it). I suppose that TopCoder article I read on binary search is coming in handy. Well I probably won't be able to work on this again until Tuesday so hopefully I'll be able to work out any "bugs" before I sit down to code.

*UPDATE: Well I managed to actually write up the code for this earlier than expected. However, there was a change in how I went about doing it. I instead did a binary search on all the possible distances between the stalls, in order to find the largest possible minimum. Basically given a distance and the number of cows I would perform the following operation;

bool(stall, distance, cows) //where they are all the appropriate data type
num=1;
prev=stall[0];
for i from 1 to one less than the number of stalls
. if stall[i]-prev is less than distance do nothing
.else prev=stall[i] and increase num by 1
end for loop
return true if num is at least as big as cows, else return false

This basically tells you the maximum number of cows you can place so that the distance between any 2 is "distance". So if I remember correctly the possible distances between stalls were between 1 and 1 billion. So the above should only needed to be run no more than 30 times.