SPOJ - Problem AGGRCOW - Aggressive cows

general
,
1

I cannot understand how binary search will solve the problem.

Problem statement is here

Need Help! Thanks :slight_smile:

2

Do not mention the topcoder tutorial :slight_smile:

3

okay,let’s start with sample testcase,shall we?
testcase 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 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;
	lld prev;
	prev=ar[0];
	fu(i,1,n)
	{
		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


[1],you can check this out. I loved this problem,especially how cleverly you can use binary search to reduce the complexity.


  [1]: http://ideone.com/EMdzlP
5 Likes
4

on line 137, why is it given l=0 and not l=a[0]?

1 Like
5

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

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
7

Thanks for the information !!

8

Please give a simple explanation of this, I have read various tutorials on this problem but no help!

1 Like
9

in the else part of bfs, i get AC with last=mid; and WA with last=mid-1;
Can someone explain why?

10

The last part of this article is really helpful. https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/