Picking Up Chicks

The problem, simply

This is a Google Code Jam problem. n chicks stand on a narrow road at positions x[0] < x[1] < ..., all running toward a barn at position b. Chick i runs at speed v[i]. A chick cannot pass the chick in front of it; it has to slow down and walk behind it.

You may pick up a slow chick and put it down just behind the faster chick, which lets the fast one pass. That is one swap, and it takes no time. You need at least k chicks in the barn within t seconds. Give back the fewest swaps, or say it is impossible.

A story to remember it

Picture it

Examples

Way 1: the simple way

First mark which chicks are fast enough alone: chick i can make it if x[i] + v[i] * t >= b. Slow chicks are never worth saving. Then try every group of k fast chicks. A chosen chick needs one swap for every slow chick in front of it, so add those up and keep the smallest total.

class Solution {
    private long best;

    // returns the fewest swaps, or -1 for IMPOSSIBLE; chicks are sorted by position
    public long minSwaps(int k, int b, int t, int[] x, int[] v) {
        int n = x.length;
        boolean[] fast = new boolean[n];
        for (int i = 0; i < n; i++) fast[i] = x[i] + (long) v[i] * t >= b;
        best = Long.MAX_VALUE;
        choose(0, k, fast, new boolean[n]);
        return best == Long.MAX_VALUE ? -1 : best;
    }

    private void choose(int i, int left, boolean[] fast, boolean[] picked) {
        if (left == 0) {
            long swaps = 0;
            for (int c = 0; c < fast.length; c++) {
                if (!picked[c]) continue;
                for (int d = c + 1; d < fast.length; d++) {
                    if (!fast[d]) swaps++;           // a slow chick in front of a saved chick
                }
            }
            best = Math.min(best, swaps);
            return;
        }
        if (i == fast.length) return;
        if (fast[i]) {
            picked[i] = true;
            choose(i + 1, left - 1, fast, picked);
            picked[i] = false;
        }
        choose(i + 1, left, fast, picked);
    }
}

How long it takes: up to 2^n groups, and each one is counted in O(n^2), so O(2^n * n^2). Extra room: the flags and the recursion, O(n).

Way 2: the clever way

Two facts make this easy.

• A fast chick only needs swaps for slow chicks in front of it. If a fast chick is stuck behind another fast chick, the one in front arrives in time, so the one behind does too.
• A fast chick closer to the barn never has more slow chicks in front of it than a fast chick further back. So the cheapest k chicks to save are the k fast chicks closest to the barn.

So walk from the barn end backward. Count the slow chicks you pass. Each fast chick you meet costs that count in swaps. Stop after k saved chicks.

class Solution {
    // returns the fewest swaps, or -1 for IMPOSSIBLE; chicks are sorted by position
    public long minSwaps(int k, int b, int t, int[] x, int[] v) {
        int saved = 0, slowAhead = 0;
        long swaps = 0;
        for (int i = x.length - 1; i >= 0 && saved < k; i--) {
            if (x[i] + (long) v[i] * t >= b) {   // fast enough on an empty road
                swaps += slowAhead;               // hop over every slow chick in front
                saved++;
            } else {
                slowAhead++;                      // blocks every fast chick behind it
            }
        }
        return saved == k ? swaps : -1;
    }
}

How long it takes: one walk, O(n). Extra room: three counters, O(1).

Watch out for

• Stop as soon as k chicks are saved. Slow chicks further back do not matter.
• v[i] * t can be large. Compute it as a long.
• A chick that lands exactly on the barn at time t counts, so the check is >=.
• k = 0 needs 0 swaps.

What interviewers ask next

• Why is one swap per slow chick enough and also needed? A fast chick arrives by t and the slow one in front arrives after t, so the fast one must catch it before the barn and must be lifted past it exactly once.
• Why closest fast chicks first? The count of slow chicks in front only grows as you walk back, so any other choice of k fast chicks costs at least as much.
• What if chicks are not given in road order? Sort them by position first, which makes it O(n log n).
• What if each swap had a different price? The greedy breaks. You would need dynamic programming over the chicks from the barn end.

Remember this

Grown-up words: the narrow road is a single lane where order is kept, "can make it alone" is a reachability check x + v * t >= b, the walk from the barn end is a reverse scan, and charging each chick the slow chicks ahead is counting inversions with a running counter.