SPOJ - Problem AGGRCOW - Aggressive cows

general
,
3

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
4

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

5

Do not mention the topcoder tutorial :slight_smile:

3 Likes
6

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

1 Like
7

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
8

Thanks for the information !!

9

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

1 Like
10

The last part of this article is really helpful. Topcoder

3 Likes
11

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?

12
4 Likes
13
  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
14

you saved my day bro.

1 Like
15

please help me resolve the nzec error

link to the solution

16

@vijju123 what???

17

i think last = mid would give WA.

18

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

19

i have tried explaining here, ask me for any doubts

1 Like
20

@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;
}
21

I have the same doubt. Did you find the answer?

22

Lets take 5 stalls s1->s5, sorted according to their positions.
We define dist(s[i]) as the minimum dist from s[i] to its nearest two stalls.
We first choose the first two stalls which are s1,s5.
To choose the 3rd stall we use binary search and lets assume it turns out to be s3, which makes s1,s5 as its nearest two stalls.
The next two stalls-> s2,s4 are found out using priority queue and binary search, but as soon as we choose s2, s4 the dist(s3) has changed,its no longer what we assumed it to be, now it needs to recalculated using s2,s4 as the nearest two stalls which is not done by the given algorithm.
That’s why its fails!!