I cannot understand how binary search will solve the problem.
Problem statement is here
Need Help! Thanks 
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 
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.
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
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
- Capture the inputs in a vector. Sort the vector. O(nlogn). The vector will have a maximum of 100K elements.
- 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.
- Start with absolute maxima and binary search till minima.
- 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. - The largest minimum distance that works and the smallest maximum distance that doesn’t work; binary search through them again.
- 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).
- 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
i think last = mid would give WA.
N and C should be on the same line separated by spaces.
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;
}