 # What Is Wrong Here?

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;
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;
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. 