CHOCOLA - Chocolate

The problem, simply

A chocolate bar is a grid of squares. Between the rows there are r straight lines, and between the columns there are c straight lines. Each line has a price: rowCut[i] for a line that runs across, colCut[j] for a line that runs down.

You break the bar into single squares. Each snap breaks one piece along one line. The price of a snap is the line's price, so cutting the same line in 3 different pieces costs 3 times its price. Give back the least total price. (This is SPOJ CHOCOLA, also known as "minimum cost to cut a board into squares".)

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order of cuts. Keep track of how many strips each direction has so far, because that decides the price of the next cut.

1. Across strips start at 1, down strips start at 1.
2. A line across costs price * (down strips) and adds one across strip. A line down costs price * (across strips) and adds one down strip.
3. Try every order and keep the cheapest total.

class Solution {
    private long best;

    public long minCost(int[] rowCut, int[] colCut) {
        best = Long.MAX_VALUE;
        go(rowCut, colCut, new boolean[rowCut.length], new boolean[colCut.length], 1, 1, 0, 0);
        return best;
    }

    // across = strips made by lines across, down = strips made by lines down
    private void go(int[] rc, int[] cc, boolean[] usedR, boolean[] usedC,
                    int across, int down, int done, long cost) {
        if (done == rc.length + cc.length) { best = Math.min(best, cost); return; }
        for (int i = 0; i < rc.length; i++) {
            if (usedR[i]) continue;
            usedR[i] = true;          // a line across is cut once in every down strip
            go(rc, cc, usedR, usedC, across + 1, down, done + 1, cost + (long) rc[i] * down);
            usedR[i] = false;
        }
        for (int j = 0; j < cc.length; j++) {
            if (usedC[j]) continue;
            usedC[j] = true;          // a line down is cut once in every across strip
            go(rc, cc, usedR, usedC, across, down + 1, done + 1, cost + (long) cc[j] * across);
            usedC[j] = false;
        }
    }
}

How long it takes: (r + c)! orders, each step O(r + c) to scan, so O((r+c)! * (r+c)). Extra room: the used flags and the recursion, O(r + c).

Way 2: the clever way

Expensive lines first.

1. Sort the across prices and the down prices, biggest first.
2. Keep across = 1 and down = 1 strip counts.
3. Repeatedly take the bigger of the two next prices. A line across costs price * down and makes across one bigger. A line down costs price * across and makes down one bigger.
4. When one list runs out, finish the other.

Why? Every line is cut eventually, and its price gets multiplied by how many pieces it crosses. That number only grows over time. Swapping two neighboring cuts so the pricier one goes first never costs more. So sorted order, biggest first, is best.

class Solution {
    public long minCost(int[] rowCut, int[] colCut) {
        int[] rc = rowCut.clone(), cc = colCut.clone();
        Arrays.sort(rc);
        Arrays.sort(cc);
        int i = rc.length - 1, j = cc.length - 1;   // walk both from the biggest price
        long across = 1, down = 1, cost = 0;

        while (i >= 0 || j >= 0) {
            boolean takeRow = j < 0 || (i >= 0 && rc[i] >= cc[j]);
            if (takeRow) {
                cost += rc[i--] * down;      // a line across crosses every down strip
                across++;
            } else {
                cost += cc[j--] * across;    // a line down crosses every across strip
                down++;
            }
        }
        return cost;
    }
}

How long it takes: two sorts, O(r log r + c log c), then one merge walk. Extra room: the sorted copies, O(r + c).

Watch out for

• Ties between an across price and a down price can be taken in either order. Both give the same total.
• The total can be large: up to about 1000 lines, each up to 1000, times up to 1000 pieces. Use long.
• Strip counts start at 1, not 0. One whole bar is one strip in each direction.
• On SPOJ, the input gives m and n and then m - 1 and n - 1 prices. Read them in the right order.

What interviewers ask next

• Prove that sorting is right. Take two cuts next to each other in some order, the cheaper one first. Swapping them makes the pricier one cross fewer or equal pieces and the cheaper one cross more or equal. The change in cost is never positive.
• What if a snap may only break one piece along a part of a line, instead of the whole line? That is the same thing here, because every part of every line must be cut in the end.
• Minimum cost to cut a stick at given points, where each cut costs the current stick length (LeetCode 1547)? That one is not greedy. It needs interval dynamic programming.
• Can you skip sorting? If prices are small, counting sort makes it O(r + c + maxPrice).

Remember this

Grown-up words: grooves are cut lines, strips are the segments between cuts, picking the biggest price each time is a greedy merge of two sorted lists, and the swapping proof is an exchange argument.