Phidias

Problem Statement Summary

Given a rectangular marble slab of size $W \times H$ ($W, H \le 600$) and $N$ desired piece sizes $(w_i, h_i)$, cut the slab by making full-width or full-height cuts (each cut traverses the entire current piece). Minimize the total wasted area (area not covered by any desired piece).

Solution: 2D DP on Rectangle Dimensions

Recurrence

Every cut splits a rectangle into two sub-rectangles. Define $\mathrm{dp}[a][b]$ = minimum waste when optimally cutting a rectangle of size $a \times b$.

\[ \mathrm{dp}[a][b] = \min\Bigl( \min_{\substack{w \in \mathcal{W} \\ 0 < w < a}} \bigl(\mathrm{dp}[w][b] + \mathrm{dp}[a{-}w][b]\bigr),\; \min_{\substack{h \in \mathcal{H} \\ 0 < h < b}} \bigl(\mathrm{dp}[a][h] + \mathrm{dp}[a][b{-}h]\bigr) \Bigr) \] where $\mathcal{W}$ and $\mathcal{H}$ are the sets of widths and heights appearing among the desired pieces.

Base cases: $\mathrm{dp}[a][b] = a \cdot b$ (all waste) unless $(a, b)$ matches a desired piece, in which case $\mathrm{dp}[a][b] = 0$.

Lemma (Cut position restriction).

It suffices to cut only at positions in $\mathcal{W}$ (for vertical cuts) or $\mathcal{H}$ (for horizontal cuts). Cutting at any other position cannot produce a desired piece boundary, so it cannot reduce waste below what these cuts achieve.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int dp[601][601];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int W, H, N;
    cin >> W >> H >> N;

    vector<int> pw(N), ph(N);
    set<int> ws, hs;
    set<pair<int,int>> pieces;

    for (int i = 0; i < N; i++) {
        cin >> pw[i] >> ph[i];
        ws.insert(pw[i]);
        hs.insert(ph[i]);
        pieces.insert({pw[i], ph[i]});
    }

    for (int a = 1; a <= W; a++) {
        for (int b = 1; b <= H; b++) {
            dp[a][b] = a * b; // worst case: all waste

            if (pieces.count({a, b})) {
                dp[a][b] = 0;
                continue;
            }

            // Vertical cuts at widths from desired pieces
            for (int w : ws) {
                if (w >= a) break;
                dp[a][b] = min(dp[a][b], dp[w][b] + dp[a - w][b]);
            }

            // Horizontal cuts at heights from desired pieces
            for (int h : hs) {
                if (h >= b) break;
                dp[a][b] = min(dp[a][b], dp[a][h] + dp[a][b - h]);
            }
        }
    }

    cout << dp[W][H] << "\n";
    return 0;
}

Complexity Analysis

• Time: $O(W \cdot H \cdot N)$. For each of the $W \times H$ states, we try at most $|\mathcal{W}| + |\mathcal{H}| \le 2N$ cut positions.

• Space: $O(W \cdot H)$.

• With $W, H \le 600$ and $N \le 600$, the total work is at most $600 \times 600 \times 1200 \approx 4.3 \times 10^8$, which is tight but feasible. The break when the cut position exceeds the current dimension prunes many iterations in practice.