# SPOJ - Problem AGGRCOW - Aggressive cows

I cannot understand how binary search will solve the problem.

Problem statement is here

Need Help! Thanks Do not mention the topcoder tutorial testcase is

`1 5 3 1 2 8 4 9`

So,we can keep the cows at 1,2,8,4 and 9th position. Now we’ve to find the largest minimum distance between 2 cows.
It’s clear that minimum distance can be 0 (all cows in same stall) or a[n-1] (2 cows at 1st and last position).

So binary search starts with l=0 and r=a[n-1] and we’ve to find the maximum distance. For that we’ll just create e function(fnc) which returns 1 if that is the desired distance else 0. So what do we write in this function? Let’s see.

``````    int fnc(int x)
{
int i,temp;
temp=1;
lld prev;
prev=ar;
fu(i,1,n)
{
if(ar[i]-prev >= x)
{
temp++;
if(temp==c)
return 1;
prev=ar[i];
}
}
return 0;
}
``````

So what it’ll do? It’ll just check whether the difference between current stall and previous stall is at least x or not and if yes it’ll increase the temp(No of cows). If temp==c,it means we can store all the cows with the difference x(mid). So we return 1,else 0.

We’ll be doing the binary search for finding the best possible maximum difference.

Hope this helps :).
Here’s my sample

``````
,you can check this out. I loved this problem,especially how cleverly you can use binary search to reduce the complexity.

: http://ideone.com/EMdzlP``````
5 Likes

on line 137, why is it given l=0 and not l=a?

1 Like

My solution goes here…

`````` #include <bits/stdc++.h>
using namespace std;
int n,c;
int func(int num,int array[])
{
int cows=1,pos=array;
for (int i=1; i<n; i++)
{
if (array[i]-pos>=num)
{
pos=array[i];
cows++;
if (cows==c)
return 1;
}
}
return 0;
}
int bs(int array[])
{
int ini=0,last=array[n-1],max=-1;
while (last>ini)
{
//cout<<last<<" "<<ini<<endl;
int mid=(ini+last)/2;
if (func(mid,array)==1)
{
//cout<<mid<<endl;
if (mid>max)
max=mid;
ini=mid+1;
}
else
last=mid;
}
return max;
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%d %d",&n,&c);
int array[n];
for (int i=0; i<n; i++)
scanf("%d",&array[i]);
sort(array,array+n);
//cout<<" dfsa \n";
int k=bs(array);
printf("%d\n",k);
}
return 0;
}
``````
3 Likes

Copy paste the entire code, then select it and then click “Enter Code.”

Also make sure that “<” operator is followed by a space. Meaning, “<3” should be made “< 3”. That will help you. 2 Likes

Thanks for the information !!

Please give a simple explanation of this, I have read various tutorials on this problem but no help!

1 Like

in the else part of bfs, i get AC with last=mid; and WA with last=mid-1;
Can someone explain why?