[The Essence of Binary Search] Aggressive Cows

Ahh, a long and tiring day nears close, and boy have I learned a lot today!

Today we are going to talk about binary search, and more importantly how to sniff out binary search problems where the binary search part is absolutely not obvious. At least to me. Here is today's one lone problem I've tried today. I legit spent about 6 hours exploring this problem and the concepts related to it.

Aggressive Cows on SPOJ

Binary Search. And interesting and fast (O(logn)) method to look for values in a binary tree or a sorted array. But it is so much more than that. Let's dive into some mathematics:

At its core, what is Binary Search? At each step, we check the truth value of a statement (most of the time it is "is the value >= the number to be searched?"), and depending on that value, we decide whether we have found our element, or we go left, or right in our journey to hunt down the searched value.

What we do with binary search is find the maximum value which satisfies our statement. 

(since maximum value >= x is x provided x exists in the array, we use this to search for x)

So essentially,

"Binary search converts an optimisation problem to a decision problem"

Our proposition is true for all cases before the answer, and false after it. So our array essentially turns into a TF sequence like this:

TTTTTTFFFFFFFFFFFF

Let us refer to this type of sequence as a TF sequence from now on.

And the mission of binary search is to find the last T.

Therefore the functionality of binary search can be modified to find the least (or conversely the greatest) element which fulfills a proposition P, which has to generate a sequence of T's followed by a sequence of F (or conversely, a sequence of F followed by a sequence of T).

This idea is so powerful, that we can exploit this in a LOT of seemingly O(n²) solutions to solve it in O(nlogn).

Let us define our proposition 

P_x(k) : "It is possible to arrange x cows in the barn such that distance between them is at least k"

Before using this, we must prove that P_x(k) yields a TF sequence.

Proof:

If P_x(k) is true, we have a situation like this:

COW.....k.....COW

Just shift that cow one step closer. COW.....(k-1).....COW

Therefore P_x(k) --> P_x(k - 1)

But the same need not be true for P_x(k + 1) because if k = n and x = 2, both cows occupy the very ends, and  P_x(n + 1) is not possible as the barn is not that long.

We have established, that if we find a valid P_x(k₀), P_x(k) is also valid for all the k <= k_0, 

Therefore, P_x(k) generates a TF sequence over k = 1 to n.

Now, we could do this:

Evaluate the truth value of P_x(k) for each k, and obtain the TF array, then find the last T. That would be O(n). Totally, it would be O(n²), as we evaluating P_x(k) as k goes from 1 to n.

But why do that?

If P_x(k) yields a TF array, we can use binary search to find the last T. 

We evaluate P_x(k) only at THAT k which is required by binary search to obtain the answer.

Barn in the example testcase:     

 0   1    2    3    4    5   6   7   8   9

And we have a set of k's for which we want to find the greatest k for which P_x(k) is true:

k = {1, 2, 3... 9}

define start = 0, end = 9. (n = 9, x = 3)

We find mid = k = floor( (start + end)/2 ). We check if P_x(k) is valid for that k (=mid).

If we get T, we can look further to the right, as there may be more T's there.

If we hit F, there DEFINITELY isn't any T to the right, so we go left.

start = 0, end = size of the barn (last index in barn array)

while (start < end):

    if (checkP_x(mid))

        start = mid + 1 

    else

        end = mid

¹Figure out what you would return when this loop finishes executing!

Now how to check P_x(mid)?

Again, we use greedy approach to do this:

 checkP_x(k):

    Put the first cow in first stall.

    Move along the barn until you find a stall which is at least k

    If you find one:

        Put a cow there

    Repeat until a) there are no cows left -> return true

                        b) the barn ends with cows still remaining -> return false

 Ok now we know all the pieces of the puzzle!

Answer to question 1: would return start - 1, as start would become the first F, so decrement it by 1 to get the last T

Now, its time for some code:

#include <iostream>
#include <vector>
#include <algorithm>

bool checkMyK(int k, int cows, std::vector<int>& barn) {
	int currentPos = 1;
	int prevCowPos = 0;
	int numCowsPlaced = 1;
	while (currentPos < barn.size()) {
		if (barn[currentPos] - barn[prevCowPos] >= k) {
			numCowsPlaced++;
			if (numCowsPlaced == cows) {
				return true;
			}
			prevCowPos = currentPos;
		}
		currentPos++;
	}
	return false;
}

int modifiedBinarySearch(std::vector<int>& barn, int cows) {
	int start = 0, end = barn[barn.size() - 1];

	while (start < end) {
		int mid = (start + end) / 2;
		if (checkMyK(mid, cows, barn)) {
			start = mid + 1;
		}
		else {
			end = mid;
		}

		//std::cout << start << " " << end << "\n";
	}

	return start - 1;
}

int main() {
	int t;
	std::cin >> t;

	while (t--) {
		int n, cows;
		std::vector<int> barn;
		std::cin >> n >> cows;

		while (n--) {
			int val;
			std::cin >> val;
			barn.push_back(val);
		}

		std::sort(barn.begin(), barn.end());

		std::cout << modifiedBinarySearch(barn, cows) << "\n";
	}
}

More reading material and references:

https://www.topcoder.com/community/competitive-programming/tutorials/binary-search/

https://discuss.codechef.com/t/spoj-problem-aggrcow-aggressive-cows/11971/12