An × chessboard is to be cut into its · unit squares

Question

An × chessboard is to be cut into its · unit squares. At each step, you can make either one horizontal cut or one vertical cut. The first cut will split the board into two sub-boards; after that each cut splits one remaining sub-board into two. The cost of a cut equals the number of unit squares remaining in the smaller of the two resulting sub-boards. For example, a horizontal cut on a 2 × 3 board results in two 1 × 3 sub-boards and costs 3, whereas a vertical cut results in sub-boards of dimensions 2 × 1 and 2 × 2 and costs 2. Costs are additive: the cost of a sequence of cuts equals the sum of their individual costs. Describe an algorithm to compute the minimum total cost of reducing the × board into its unit squares. Prove its correctness and show your analysis of its time complexity.

My solution goes as follows: 1. I follow the greedy approach of checking for the highest between m (row) and n (column) and making a cut. 2. If m is higher I make a vertical cut and other a horizontal cut. 3. This gives me the lowest cut cost in every step. 4. I follow divide and conquer and recursively follow the approach until I have m x n = 1 x 1

This seems to be working but what I am struggling with is to derive the time complexity and proving the correctness of my algorithm.

My expression of time complexity is T(mn) = 2 T(mn/2) + theta(n).

Can someone advice me how I can do this?

Answer 1

The minimum cost is (n-1)*m+(m-1)*n. You can obtain by making m horizontal cuts paying for every one n-1 and n vertical cuts paying for every one m-1. That is O(1) algorithm.

To cut off a one unit square you need to pay at least 2 for it in (n-1)*(m-1) cases, at least 1 in (n-1)+(m-1), and one unit square you can get for free. This bounds overall price from below:

2*(n-1)*(m-1)+1*(n-1)+(m-1)+0*1 = 2*n*m-n-m = (n-1)*m+(m-1)*n

Answer 2

Here is a dynamic programming approach which works in O (m * n * (m + n)).

For each possible size w * h of a sub-rectangle, compute the cost f (w, h) of cutting it into individual squares. Choose the first cut: w * h is cut either into a * h and b * h, or into w * c and w * d. The cost of cutting into a * h and b * h is min (a, b) * h + f (a, h) + f (b, h). The cost of cutting into w * c and w * d is w * min (c, d) + f (w, c) + f (w, d). Putting all that together, we have

f (w, h) = min of
                min {for every a such that 0 < a < w}
                    (let b = w - a)
                    min (a, b) * h + f (a, h) + f (b, h)
           and
                min {for every c such that 0 < c < h}
                    (let d = h - c)
                    w * min (c, d) + f (w, c) + f (w, d)

The base is f (1, 1) = 0.

We can store all f (w, h) as a two-dimensional array and calculate them bottom-up in two loops, like this:

for w = 1, 2, ..., m:
    for h = 1, 2, ..., n:
        calculate f[w][h] by the formula above in O (w + h)

Or write a recursive function with memoization.

Any of the two approaches will work in O (m * n * (m + n)): we have to calculate m * n values, and each one is calculated as a minimum of O (m + n) values.

---

If the greedy approach actually works (I don't know), it would do so in O (log m + log n). By intuitive argument, for example, if m = 17 and n = 23, then the following rectangles must be considered:

17 * 23
17 * 11 and 17 * 12
 8 * 11 and  8 * 12 and  9 * 11 and  9 * 12
 8 *  5 and  8 *  6 and  9 *  5 and  9 *  6
 4 *  5 and  4 *  6 and  5 *  5 and  5 *  6
 4 *  2 and  4 *  3 and  5 *  2 and  5 *  3
 2 *  2 and  2 *  3 and  3 *  2 and  3 *  3
 1 *  1 and  1 *  2 and  2 *  1 and  2 *  2
 1 *  1 again

As we can see, the rectangles will be of the form (m / 2^x) * (n / 2^y), where x and y are between 0 and log_2 (m + n), and the rounding can go either way.