GERGOVIA - Wine trading in Gergovia

The problem, simply

Houses stand in a row on one street. House i has a number a[i]. A positive number means the house wants to buy that many bottles of wine. A negative number means it wants to sell that many. All the numbers add up to 0, so supply matches demand.

Carrying one bottle from a house to its neighbor costs 1 unit of work. Give back the least total work needed so that every house gets exactly what it wants.

A story to remember it

Picture it

Examples

Way 1: the simple way

Think about single bottles. Write down the house of every bottle wanted, from left to right, and the house of every bottle for sale, from left to right. On a line, the best plan sends the first bottle for sale to the first bottle wanted, the second to the second, and so on. Add up the distances.

1. Make a list want with house i written a[i] times when a[i] > 0.
2. Make a list sell with house i written -a[i] times when a[i] < 0.
3. The answer is the sum of |want[k] - sell[k]| over all k.

class Solution {
    public long minWork(int[] a) {
        List<Integer> want = new ArrayList<>(), sell = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            for (int c = 0; c < a[i]; c++) want.add(i);    // one entry per bottle wanted
            for (int c = 0; c < -a[i]; c++) sell.add(i);   // one entry per bottle for sale
        }
        long work = 0;
        for (int k = 0; k < want.size(); k++) {
            work += Math.abs(want.get(k) - sell.get(k));   // k-th seller serves k-th buyer
        }
        return work;
    }
}

How long it takes: one step per bottle, and there can be up to A = 1000 bottles per house, so O(n * A). Extra room: the two bottle lists, O(n * A).

Way 2: the clever way

Look at one road, between house i and house i + 1. Add up the numbers of all houses on the left side: call it carry. If carry is 5, the left side needs 5 more bottles than it has, so at least 5 bottles must cross this road from right to left. If carry is -1, the left side has 1 spare, which must cross to the right. Either way at least |carry| bottles cross, and walking left to right we can make exactly that many cross.

1. Start with carry = 0 and work = 0.
2. For every house except the last: carry += a[i], then work += |carry|.
3. Return work.

class Solution {
    public long minWork(int[] a) {
        long carry = 0, work = 0;
        for (int i = 0; i + 1 < a.length; i++) {
            carry += a[i];               // balance of all houses up to i
            work += Math.abs(carry);     // that many bottles cross the road after house i
        }
        return work;
    }
}

How long it takes: one pass, O(n). Extra room: two numbers, O(1).

Watch out for

• Take the absolute value of carry. Bottles moving left and bottles moving right both cost work.
• The last house does not add a road. Its carry is always 0 because the numbers add up to 0.
• On SPOJ the input has many test cases and ends with n = 0. Read fast.

What interviewers ask next

• Why is |carry| a lower bound for each road? Everything left of the road is short or long by exactly carry bottles, and the only way to fix that is across this road.
• Same idea elsewhere? LeetCode 517 (Super Washing Machines) and "distribute coins in a binary tree" (LeetCode 979) both count how much must flow across each link. In the tree version, the flow across an edge is the subtree's balance.
• The houses form a circle instead of a line? Then one road's flow is free to choose. Subtract the median of the prefix sums from all of them and add up the absolute values.
• Each house can only hold some amount? That turns into a minimum cost flow problem.

Remember this

Grown-up words: the running total is a prefix sum, the roads are edges of a path graph, and counting what must cross each edge is a flow argument that makes the greedy optimal.