When stuck inside because of the snow, what else is there to do but bake and code? I made these brownies here. They are amazingly moist, but I'll probably cut down on the sugar next time I make them.

On the algorithms side, I finally got to the Platinum Division on the USA Computing Olympiad. It's primarily for high school students, but I find it fun to participate anyway.

One of the competition's problems employs clever usage of binary search that I want to write about. Basically, there are times when the solution is very hard to compute, but it is not too costly to verify. If the solution is numerical and bounded, we can guess solutions with binary search. I've actually been quite familiar with this strategy for a year now, but somehow I missed it in this particular problem. Here, we use a two-dimensional binary search. Thankfully, I got enough points to get promoted to the next division anyway, anyway.

Angry Cows

Here's the problem statement:

Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots a cow with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line; the cow lands with sufficient force to detonate the hay bales in close proximity to her landing site, which in turn might set of a chain reaction that causes additional hay bales to explode. The goal is to use a single cow to start a chain reaction that detonates all the hay bales. There are $N$ hay bales located at distinct integer positions $x_1,x_2,\ldots,x_N$ on the number line. If a cow is launched with power $R$ landing at position $x$, this will causes a blast of "radius $R$", engulfing all hay bales within the range $x−R \ldots x+R$. These hay bales then themselves explode (all simultaneously), each with a blast radius of $R−1$. Any not-yet-exploded bales caught in these blasts then all explode (all simultaneously) with blast radius $R−2$, and so on.

Please determine the minimum amount of power $R$ with which a single cow may be launched so that, if it lands at an appropriate location, it will cause subsequent detonation of every single hay bale in the scene.

INPUT FORMAT (file angry.in):

The first line of input contains $R$ ($2 \leq N \leq 50,000$). The remaining $N$ lines all contain integers $x_1 \ldots x_N$ (each in the range $0 \ldots 1,000,000,000$).

OUTPUT FORMAT (file angry.out):

Please output the minimum power $R$ with which a cow must be launched in order to detonate all the hay bales. Answers should be rounded and printed to exactly $1$ decimal point.

So, if we assume the hay bales are sorted $x_1 \leq \cdots \leq x_N$. The minimum blast radius must be at most $(x_N - x_1)/2$ since we can just launch such a cow at the midpoint and destroy all the hay bales without the chain reaction. It's also worth noting that if the optimal blast radius is $R^*,$ then $2R^* \in \mathbb{Z}$, that is, twice the optimal blast radius is an integer. Since all the hay bales are located at integer coordinates, adding less than $0.5$ to the radius will never encompass another hay bale. Finally, the last observation is that we should fire the cow so that the very left of the blast lines up exactly with a hay bale since we would not gain anything by having the hay bale strictly inside the blast radius.

Let $L$ be the index of the leftmost hay bale hit by the initial blast. Thus, we could brute force by trying all $2R^* \in \{0,1,\ldots,x_N-x_1\}$ and $L \in \{1,2,\ldots,N\}$. To check if such values work, we can simulate the chain reaction which takes $O(N)$ time. Thus, brute force would take $O\left(N^2(x_N - x_1)\right)$ time. This is where binary search comes in.

During the contest, it was obvious to me that we should do a binary search to find $2R^*$ considering that $x_N - x_1$ could be as large as $10^9$. However, this is not fast enough, as that only gets us $O\left(N^2\log(x_N-x_1)\right)$ time, and $N^2$ can be as large as $2.5 \times 10^9$. After sleeping on it, I made the key insight that we can binary search on the index of the leftmost hay bale, too, so now we have $O\left(N\log(N)\log(x_N-x_1)\right)$ time, which is adequate.

To make this explicit, here's the code:

import java.io.*;
import java.util.*;

public class angry {

    /* check that all the hay bales to the left of idx explode 
     * if we throw cow of power T/2 at hayBales[idx] + T/2
     */
    public static boolean leftExplodes(int idx, int T, int[] hayBales) {
        double currentFloor = hayBales[idx];
        double currentR = T/2.0;
        int left; // leftmost exploded bale
        for (left = idx; left >= 0 && hayBales[left] >= currentFloor; --left) {
            if (left == 0 || hayBales[left - 1] >= currentFloor) continue;
            currentR -= 1.0;
            currentFloor = hayBales[left] - currentR;
        }
        return left == -1;
    }

    public static boolean isDiameterPossible(int T, int[] hayBales) {
        int N = hayBales.length;
        int leftMin = 0; // inclusive
        int leftMax = N; // exclusive         
        int leftIdx = leftMin + (leftMax - leftMin)/2;
        while (leftMin < leftMax) { // find smallest left such that this doesn't work
            if (leftExplodes(leftIdx, T, hayBales)) {
                leftMin = leftIdx + 1;
            } else {
                leftMax = leftIdx;
            }
            leftIdx = leftMin + (leftMax - leftMin)/2;            
        }        
        --leftIdx; // this works
        // now check that the right explodes
        double currentCeiling = hayBales[leftIdx] + T;
        double currentR = T/2.0;
        int right;
        for (right = leftIdx; right < N && hayBales[right] <= currentCeiling; ++right) {
            if (right == N - 1 || hayBales[right + 1] <= currentCeiling)  continue;
            currentR -= 1.0;
            currentCeiling = hayBales[right] + currentR;
        }        
        return right == N;        
    }        

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("angry.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("angry.out")));
        int N = Integer.parseInt(in.readLine());
        int[] hayBales = new int[N];
        for (int n = 0; n < N; ++n) hayBales[n] = Integer.parseInt(in.readLine());
        Arrays.sort(hayBales);

        // search for T = 2R
        int minT = 0; int maxT = hayBales[N - 1] - hayBales[0];
        int T = minT + (maxT - minT)/2;       
        while (minT < maxT) { // find smallest T that works
            if (isDiameterPossible(T, hayBales)) {
                maxT = T;
            } else {
                minT = T + 1;
            }
            T = minT + (maxT - minT)/2;
        }
        out.printf("%.1f\n", T/2.0);
        in.close();
        out.close();
    }

}