CP and Interview Pack: Binary Search on the Answer, LIS and the Bug Gallery

SPOJ, an online judge with a large archive of contest problems, has a classic called AGGRCOW, "Aggressive cows". Farmer John's barn has N stalls along a line, and his C cows fight when they stand close. He wants the smallest distance between any two cows to be as large as possible. Bob tries every distance from the largest down, and each try walks all the stalls. Amara notices something better: if the cows fit 3 apart, they also fit 2 apart. A yes that turns into a no only once is a sorted strip, and a sorted strip can be halved.