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

okay, letâ€™s start with the sample test case, shall we?

test case 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 the 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;
long long int prev;
prev = ar[0];
for(i = 1 ; i < n ; i++)
{
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 Solution , you can check this out. I loved this problem, especially how cleverly you can use binary search to reduce the complexity.

7 Likes

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;
}
```

5 Likes

in the else part of bfs, i get AC with last=mid; and WA with last=mid-1;

Can someone explain why?

Do not mention the topcoder tutorial

2 Likes

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

1 Like

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

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

1 Like

For Eg:

In your code, if mid returns true, then there can be possiblity, any element before mid also returns true, and we have to return minimum value of x so it can be before mid too, so how you can discard half array?

2 Likes

- Capture the inputs in a vector. Sort the vector. O(nlogn). The vector will have a maximum of 100K elements.
- The absolute maxima of minimum possible distance is V[n-1] - V[0]/(number of cows -1). The minima is 1, all cows occupy adjacent barns.
- Start with absolute maxima and binary search till minima.
- If a minimum distance m is to work:

a. First cow C1 at V[0]

b. Second cow C2 greater than or equal to C1 + m

c. Third cow C3 greater than or equal to C2 + m

d. If we are unable to accommodate all cows, this case has failed. Record this case. Move on to a smaller case in a binary search fashion. - The largest minimum distance that works and the smallest maximum distance that doesnâ€™t work; binary search through them again.
- It will take log(n) attempts to find the right minimum distance in worst case; and each attempt will require n checks in worst case. Thus, this whole process is O(nlogn).
- The overall complexity is O(nlogn).

you saved my day bro.

1 Like

please help me resolve the nzec error

link to the solution

i think last = mid would give WA.

N and C should be on the same line separated by spaces.