I cannot understand how binary search will solve the problem.

Problem statement is here

Need Help! Thanks

I cannot understand how binary search will solve the problem.

Problem statement is here

Need Help! Thanks

Do not mention the topcoder tutorial

okay,letâ€™s start with sample testcase,shall we?

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[0];
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

```
[1],you can check this out. I loved this problem,especially how cleverly you can use binary search to reduce the complexity.
[1]: http://ideone.com/EMdzlP
```

5 Likes

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

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[0];
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?

The last part of this article is really helpful. https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/