SPOJ - Problem AGGRCOW - Aggressive cows

I cannot understand how binary search will solve the problem.

Problem statement is here

Need Help! Thanks :slight_smile:

1 Like

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.

13 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;
} 
6 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 :slight_smile:

3 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. :slight_smile:

3 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. Topcoder

3 Likes

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?

4 Likes
  1. Capture the inputs in a vector. Sort the vector. O(nlogn). The vector will have a maximum of 100K elements.
  2. 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.
  3. Start with absolute maxima and binary search till minima.
  4. 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.
  5. The largest minimum distance that works and the smallest maximum distance that doesn’t work; binary search through them again.
  6. 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).
  7. The overall complexity is O(nlogn).
3 Likes

you saved my day bro.

1 Like

please help me resolve the nzec error

link to the solution

@vijju123 what???

i think last = mid would give WA.

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

i have tried explaining here, ask me for any doubts

1 Like

@sksama

Hello friends, what is wrong with this solution for AGGRCOW. I am using a combination of binary search and priority queue. I tested the testcases but I am getting WA. Please help!!

#include <bits/stdc++.h>
using namespace std;

pair<long long, long long> bsearch(vector<long long>& v, long long l, long long r, long long midval) {
	long long l1 = l, r1 = r;
	long long pleft = -1, prite = -1;
	while((l <= r)) {
		auto mid = l + (r - l)/2;
		if (v[mid] == midval) {
			return make_pair(min(abs(v[mid] - v[l1]), abs(v[mid] - v[r1])), mid);
		} else {
			if (v[mid] < midval) {
				
			   l = mid + 1;
			   if ((mid+1) >= r1) {
			   	 return make_pair(min(abs(v[mid] - v[l1]), abs(v[mid] - v[r1])), mid);
			   }
			   // return 
			   if (v[mid + 1] == midval) {
			   	 return make_pair(min(abs(v[mid+1] - v[l1]), abs(v[mid+1] - v[r1])), mid+1);
			   }
			   //normal case
			    if (v[mid + 1] > midval) {
			   	  r = mid + 1;
			   	  l = mid;
			   	  break;
			    }
			} else {
				r = mid - 1;
				if ((mid - 1) <= l1) {
   			   	 return make_pair(min(abs(v[mid] - v[l1]), abs(v[mid] - v[r1])), mid);
				}
				if (v[mid - 1] == midval) {
					return make_pair(min(abs(v[mid-1] - v[l1]), abs(v[mid-1] - v[r1])), mid-1);
				}
				// normal case
				if (v[mid - 1] < midval) {
					r = mid;
					l = mid - 1;
					break;
				}
			}
		}
	}
   // cout << midval<< l << r <<endl;
   //auto ll = 0;
   // if (l == r) {
   // 	r = l + 1;
   // 	ll = l - 1;
   // }
   	pleft = min(abs(v[l] - v[l1]), abs(v[r1] - v[l]));
	prite = min(abs(v[r] - v[l1]), abs(v[r] - v[r1]));
//	auto pleftl = min(abs(v[ll] - v[l1]), abs(v[r1] - v[ll]));

	if (l <= l1) {
		pleft = -1;
	} 
	if (r >= r1) {
		prite = -1;
	}
	
	// if (ll <= l1) {
	// 	pleftl = -1;
	// }
	if (pleft > prite) {
		// if (pleftl > pleft) {
		// 	return make_pair(pleftl, l);
		// }
		return make_pair(min(abs(v[l] - v[l1]), abs(v[r1] - v[l])), l);
	} else {
		// if (pleftl > prite) {
		// 	return make_pair(pleftl, l);
		// }
		return make_pair(min(abs(v[r] - v[l1]), abs(v[r] - v[r1])), r);
	}
}

long long midfun(long long l, long long r) {
	return (l + (r - l)/2);
}
int main() {
	long long t;
	cin >> t;
	while(t--) {
	long long n, c;
	cin >> n >> c;
	vector<long long> v;
	for (long long i = 0; i < n; ++i) {
		long long val;
		cin >> val;
		v.push_back(val);
	}
	sort(v.begin(), v.end());

	long long l = 0;
	long long r = n-1;
	c -= 2;
	// pmin, pidx, l, r
	auto cmp = [&](pair<pair<long long, long long>, pair<long long, long long>>& lft, pair<pair<long long, long long>, pair<long long, long long>>& rt) {
	
		return lft.first.first < rt.first.first;
	};
	priority_queue<pair<pair<long long, long long>, pair<long long, long long>>, vector<pair<pair<long long, long long>, pair<long long, long long>>>, decltype(cmp)> pq(cmp);  
	long long pmin;
	long long midval = midfun(v[0], v[n-1]);

	auto res = bsearch(v, 0, n-1, midval);
	pmin = v[n-1] - v[0];
	if (c == 0) {
		cout << pmin << endl;
		continue;
	}
	pq.push(make_pair(res, make_pair(0, n-1)));
	while(c--) {
		auto cur = pq.top();
		pq.pop();
		
		if (c == 0) {
			pmin = cur.first.first;
		}
		long long midval1 = midfun(v[cur.second.first], v[cur.first.second]);
		long long midval2 = midfun(v[cur.first.second], v[cur.second.second]);
  //      cout << midval1 <<cur.second.first <<cur.first.second << midval2 << cur.second.second;
		auto res1 = bsearch(v, cur.second.first, cur.first.second, midval1);
		auto res2 = bsearch(v, cur.first.second, cur.second.second,  midval2);
		pq.push(make_pair(res1, make_pair(cur.second.first, cur.first.second)));
		pq.push(make_pair(res2, make_pair(cur.first.second, cur.second.second)));
//		cout << res1.first <<res1.second <<cur.second.first<<cur.first.second << cur.second.second;
		
	}
	cout << pmin <<endl;
	// your code here
	}
	return 0;
}