SPOJ - Problem AGGRCOW - Aggressive cows

I cannot understand how binary search will solve the problem.

Problem statement is here

Need Help! Thanks :slight_smile:

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

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

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

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