Discrete Binary Search ( SPOJ AGGRESSIVE COWS)


We all know the standard Binary Search and it's working, let's explore some non-trivial applications of Binary Search and see the Real Power of Binary Search in this post.

 Discrete Binary Search : - 

 Before proceeding any further I would request you all to read the famous SPOJ problem AGGRCOW. And try to think in terms of standard binary search on how can it be solved.

 If you got the solution, bingo you know what Discrete Binary Search is and can directly proceed to solve a similar question at the end of this post. If not, let's first learn what is Discrete Binary Search.

 Basically, assume that
  • You have a function f(x) which is monotonically increasing (decreasing) on the interval [a, b].
  • f(a) < C < f(b)
  • You want to find x such that f(x) = C.
Then you can use binary search to find x. Essentially, you half the possible interval for the variable x each time.
For the AGGRCOW question let's check for the test case,
1
5 3
1 
2
4
8
9
So, we can keep the cows at 1,2,8,4,9th position and we have to find the largest minimum distance between two cows. Its clear that minimum distance is 0,i.e, all cows in the same stall or a[n-1] (2 cows at 1st and last position).

Now that we have got our upper and lower limits, we have to find the answer, which exist between them.

But the question arises, why binary search? 

1.   It is very clear that, for a value 'x', if it is not possible to keep all the cows in the stalls with the minimum distance between any two cows as 'x', then it will not be possible for all y > x , and hence answer<x. This is the point which gives entry to binary search in the scene!

2.   The constraints given are such that O(nlogn) will only suffice. Generally problems where we are asked to find "maximum of minimum" or "minimum of maximum" with such constraints we consider checking for binary search atleast once. 

Now, we will do binary search for answer, with i as upper and j as lower limit, mid is the middle element. For each mid we will see if it is possible to fit all the cows in stalls with mid as the minimum distance between any two cows. Further we can decide if we have to search for the answer in the upper or lower half of the mid!

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

int n,c;
int func(int num,int a[])
{
    int cows=1,pos=a[0];
    for (int i=1; i<n; i++)
    {
        if (a[i]-pos>=num)
        {
            pos=a[i];
            cows++;
            if (cows==c)
                return 1;
        }
    }
    return 0;
}

int bs(int a[])
{
    int lo=0,high=a[n-1],max=-1;
    while (lo<high)
    {
        int mid=(lo+high)/2;
        if (func(mid,a)==1)
        {
            lo=mid+1;
        }
        else
            high=mid;
    }
    return max;
}

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d %d",&n,&c);
        int a[n];
        for (int i=0; i<n; i++)
            cin>>a[i]
        sort(a,a+n);
        int k=bs(a);
        printf("%d\n",k);
    }
    return 0;
}


Let's Practice some more questions.

Question 1 : HMAPPY

Solution:


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

#define ll long long int

ll maxi(ll a,ll b){
 return a>b?a:b;
}

ll a[100005],b[100005];

bool poss(ll ans,ll k,ll n){
 for(int i=0;i<n;i++){
  if(a[i]==0 || b[i]==0)
   continue;
  ll balloo = a[i]-(ans/b[i]);
  k-=maxi(0,balloo);
 }
 if(k>=0)
  return 1;
 return 0;
}

int main(){
 ll n,m,sum=0;
 cin>>n>>m;
 for(int i=0;i<n;i++){
  cin>>a[i];
  sum+=a[i];
 }
 for(int i=0;i<n;i++)
  cin>>b[i];
 if(sum<=m){
  cout<<0<<endl;
  return 0;
 }
 ll low = 0;
 ll high = 1e18,ans=0;
 while(low<high){
  ans = (low+high)/2;
  if(poss(ans,m,n)){
   high = ans;
  }
  else
   low = ans+1;
 }
 cout<<low<<endl;

}


Question 2 : Bhallaladeva

 Solution:

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

#define ll long long int

int main(){
 ll n,q,k;
 cin>>n;
 ll a[n];
 for(int i=0;i<n;i++){
  cin>>a[i];
 }
 sort(a,a+n);
 for(int i=1;i<n;i++)
  a[i]+=a[i-1];
 cin>>q;
 while(q--){
  cin>>k;
  ll low = 0;
  ll high = n,ans=n;
  while(low<high){
   ans = (low+high)/2;
   if(n<=((k+1)*ans)){
    high = ans;
   }
   else
    low = ans+1;
  }
  cout<<a[low-1]<<endl;
 }
 
}



Practice Questions:


  1. Link to Problem
  2. Link to Problem


If you find any problem that can be solved with Binary search share them on the comments section so we can add them to this list.

Comments

Post a Comment

Popular posts from this blog

Lazy Propagation - Too lazy to update all at a time

Image
Sometimes problems will ask you to update an interval from  l to r , instead of a single element. One solution is to update all the elements one by one. Complexity of this approach will be  O(N)  per operation since where are  N  elements in the array and updating a single element will take  O(logN)  time. To avoid multiple call to update function, we can modify the update function to work on an interval. For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we need to update this node and all descendants of this node. With Lazy propagation, we update only node with value 27 and postpone updates to its children by storing this update information in separate nodes called lazy nodes or values. We create an array lazy[] which represents lazy node. Size of lazy[] is same as array that represents segment tree, which is tree[] in below code. The idea is to initialize
Read more

Combinatorial Game Theory

Image
Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints. These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find. First, we will look at the basic division of positions to winning and losing . Question:  Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner. Approach:  As we can see positions 1, 3 and 4 are winning positions since the
Read more

Bit Manipulation Problems

We may face many Interview Questions which can ask us to find the Sum of XOR of all pairs of the array OR  Sum of XOR of all subsets   Generally, the constraints for these questions are very high with the value of each array element to be as large as 10^18. So that is a catch to use Bit manipulation method to solve the questions. We will be discussing some of these questions in this post.   Question  1:  Sum of XOR of all possible subsets   Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all   the elements of the subsets.   Input                                                Output  3                                                       28  1 5 6   Explanation:  The most important clue for solving these questions is to find a pattern  with respect to the                property of XOR .  1 = 001 5 = 101 6 = 110 1 ^ 5 = 100 1 ^ 6 = 111 5 ^ 6 = 011 1^5^6 = 010 Total number of subs
Read more