bin_search.cpp

// notes for binary search lecture
// binary search is also used to search configurations with the following
// properties where we find the first True
// F F F F .... F (T) T T T ... T 
// Apply binary search: to check that given the answer, is the configuration valid

/*
Example question: Aggressive cows (SPOJ)
N stalls on a straight line, C cows, no two cows can be tied to one stall.
Find the largest minimum distance of two cows of an assignment.

Example case:
Stalls: [1, ..., 5, ...., 10], 2 cows 
Best assignment: cow 1 -> stall 1 
                 cow 2 -> stall 10

Soln: 
check function: given largest min distance, is it possible to allocate for c
cows
*/
// core code 
bool check (const vector <int> & stalls, int c, int dist) {
  int next = 0, cnt = 0;
  for (int i = 0; i < stalls.size(); ++i) {
    if (stalls[i] >= next + dist) {
      cnt++;
      next = stalls[i] + dist;
    }
  }
  return cnt >= c;
}

/* 
Problem 2: Painters partition https://www.interviewbit.com/problems/painters-partition-problem/
Task: paint all N boards [C0, C1, C2, C3 … CN-1]. 
There are A painters available and each of them takes B units of time to 
paint 1 unit of board.

Calculate and return minimum time required to paint all boards under the 
constraints that any painter will only paint contiguous sections of board.
*/

/*
key idea: time needed to complete the task is dependent on the slowest painter.
check function: given the slowest possible time t per person, check if it's 
possible to complete all tasks within A person limit.
*/
bool check (int A, const vector <int> & C, int t) {
  // assume each person takes t time
  int i = 0;
  int x = t;
  int cnt = 1;
  while (i < C.size()) {
    if (cnt > A) return false;
    if (C[i] <= x) {
      // use the same person
      x -= C[i];
      // moves on to the next task
      i++;
    } else {
      // adds another person
      // refills time
      x = t;
      cnt++;
    }
  }
  return cnt <= A;
}

/*
Problem 3: allocate books

N number of books are given. 
The ith book has Pi number of pages. 
You have to allocate books to M number of students so that maximum number of 
pages alloted to a student is minimum. A book will be allocated to exactly one 
student. Each student has to be allocated at least one book. 
*/

// key idea: 
// Each student has page limit P, check that allocation scheme requires <= M
// students 
bool check (const vector <int> & books, int P, int M) {
  int x = P;
  int cnt = 0;
  int i = 0;
  while ( i < books.size()) {
    if (cnt > M) return false;
    if (books[i] <= P) {
      x -= books[i];
      i++;
    } else {
      x = P;
      cnt++;
    }
  }
  return true;
}

/*
Problem 4: delivery and pickup
*/

/*
Problem 5: odd and even subsequence
https://codeforces.com/contest/1370/problem/D?f0a28=1

key idea:
use b search to limit the cost, and greedily construct a qualifying subsequence
E.g. constructing an even sequence with cost c 
for all even index elements, onboard only if the value is < c; for odd index
elements we don't care.
check that with this cost c, we can construct a sequence with required length
*/

bool check (const vector <int> & v, int flag, int c, int len) {
  int i = 0;
  int cnt = 0;
  for (; i < v.size(); ++i) {
    if (!flag) {
      // onboard 
      cnt++;
      // use bit to track odd or even index
      flag ^= 1;
    } else {
      if (v[i] <= c) {
        cnt++;
        flag ^= 1;
      }
    }
  }
  return cnt >= len;
}