Spoj-Aggressive cows

After a long time ,i started solving spoj problems.I came across this interesting problem

http://www.spoj.com/problems/AGGRCOW/

Here is the approach

lets have a function

f(x) which will return 1 if gap between the cow stalls can be atleast of length x( i.e. all cows can occupy the stalls which are placed x distance  from ajacent stalls)

or return 0 if the gap between the stalls cannot be of length x

iff(x) ==0 then f(y) is also 0 such that y>x . We should code a function which can check

if x is can be allowed distance between each stall.

Our task is to find the largest minimum distance between the stalls.(i.e largest value of the allowed minimum distance)

How to do that ??

Well,You can always place cows such that the minimum distance is 0, while almost always, you cannot achieve minimum distance = N-1. For each number ‘x’ between 0 and N-1, you can either place the cows with minimum distance = ‘x’ or not.
If you list whether you can place the cows with a given distance ‘x’ you have check one by one
0 – Yes
1 – Yes
2 – Yes
.
.
.
x1 – Yes
x2 – No
x2+1 – No
.
.
.
N-1 – No

Our task is to find x1

This can be done using a simple binary search!

f(0)………………………………………………………..f(N-1) will be like

1 1 1 1 1 1 1 0 0 0 0 0 0…………………………..0 0 0

we have to find the last occuring 1

let

start=0

end=n-1

mid =(start+end)/2

if f(mid)=0 then x1 occurs within start and mid

if f(mid)=1 then x1 occurs within mid+1 and end

Search accordingly using divide and conquer strategy

[gist https://gist.github.com/vishnujayvel/6329080]