Here’s the link to the problem https://www.spoj.com/problems/AGGRCOW/

And here is my code:-

```
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
bool f(long long x, long long c, const vector<long long>& d)
{
long long cnt = 1;
for(long long i=1; i<d.size() && cnt < c; i++)
{
if(d[i]-d[i-1] >= x) cnt++;
}
if(cnt == c) return true;
else return false;
}
int main()
{
int t;
cin >> t;
while(t--)
{
long long n, c;
cin >> n >> c;
vector<long long> d(n);
rep(i,0,n) cin >> d[i];
sort(d.begin(), d.end());
long long low = 0, high = d[n-1]-d[0];
while(low <= high)
{
long long mid = low + (high-low)/2;
if(f(mid,c,d)) low = mid+1;
else high = mid-1;
}
cout << low << "\n";
}
return 0;
}
```

I have tried the sample test case given with the problem and I get the correct output. To double check I picked up someone else’s code (here from Discuss itself) and tried matching my output for a test case with 1000 stalls and 648 cows, and again I got the correct answer. But on submitting my code I am getting WA. Please help me in figuring out the flaw in the code.

In the function f, you should compare it with the last barn that has a cow, not the last barn.

I’m not too sure about your binary search either, I changed it into a format that makes sense to me.

##
Corrected code

```
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
bool f(long long x, long long c, const vector<long long>& d)
{
long long cnt = 1;
for(long long i=1, j=0; i<d.size() && cnt < c; i++)
{
if(d[i]-d[j] >= x){ //With the last barn we use
cnt++;
j=i;
}
}
if(cnt == c) return true;
else return false;
}
int main()
{
int t;
cin >> t;
while(t--)
{
long long n, c;
cin >> n >> c;
vector<long long> d(n);
rep(i,0,n) cin >> d[i];
sort(d.begin(), d.end());
long long low = 0, high = d[n-1]-d[0];
while(low < high)//There is more than one possible value
{
long long mid = low + (high-low + 1)/2;
//High is a stricter condition, gives mid-1, so we add 1.
if(f(mid,c,d)){
low = mid;
//We can get at least this much
}
else{
high = mid-1;
//This is too much
}
}
cout << low << "\n";
}
return 0;
}
```

Some doubts. Why is “low < high” not “low <= high”, why have you added 1 while calculating mid, and why “low = mid” and not “low = mid-1”?

Let’s say the answer is `4`

and `low=0`

and `high=5`

Your binary search goes through the following states.

```
low | high | mid
0 5 2
3 5 4
5 5 5
5 4 4
```

Low ended up being 5 which is incorrect.

Though I guess making a new variable `ans`

and writing `ans=min(low, high)`

would also work. or you could do `low=mid+1;ans=mid;`

and then use `ans`

.

As for why my binary search is correct -

Let’s say it is possible to have a distance of x. Then the range of the answer is [x,\infty) because x itself is possible, and something larger may also be possible. Therefore if `mid`

is possible, `low=mid`

. Let’s say a distance of y is not possible. Then the range of the answer is [0, y) because the answer must be strictly less than y. That’s why if `mid`

is not possible , `high=mid-1`

.

The +1 is just because you need to go towards the stricter condition, the one that gives `high=mid-1`

or `low=mid+1`

. If it was `low=mid+1`

and `high=mid`

you don’t do +1.

When `low==high`

then There is only one possible value left for the answer, so we have to break.

This is how my binary search goes through the values.

```
low | high | mid
0 5 3
3 5 4
4 5 5
4 4 4
```

1 Like

Thanks a lot. I finally understood it.