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.
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(n2) solutions to solve it in O(nlogn).
Let us define our proposition
Px(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 Px(k) yields a TF sequence.
Proof:
If Px(k) is true, we have a situation like this:
COW.....k.....COW
Just shift that cow one step closer. COW.....(k-1).....COW
Therefore Px(k) --> Px(k - 1)
But the same need not be true for Px(k + 1) because if k = n and x = 2, both cows occupy the very ends, and Px(n + 1) is not possible as the barn is not that long.
We have established, that if we find a valid Px(k0), Px(k) is also valid for all the k <= k0,
Therefore, Px(k) generates a TF sequence over k = 1 to n.
Now, we could do this:
Evaluate the truth value of Px(k) for each k, and obtain the TF array, then find the last T. That would be O(n). Totally, it would be O(n2), as we evaluating Px(k) as k goes from 1 to n.
But why do that?
If Px(k) yields a TF array, we can use binary search to find the last T.
We evaluate Px(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 Px(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 Px(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 (checkPx(mid))
start = mid + 1
else
end = mid
1Figure out what you would return when this loop finishes executing!
Now how to check Px(mid)?
Again, we use greedy approach to do this:
checkPx(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
