What Is Wrong Here?

general
,
1

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.

2

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

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”?

4

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
5

Thanks a lot. I finally understood it. :grinning: