Editorial for dpcutrec: Cắt hình chữ nhật

Hiểu bài toán

Bài toán yêu cầu tìm số hình vuông ít nhất có thể cắt được từ một hình chữ nhật kích thước M × N. Máy cắt chỉ cắt theo đường thẳng song song với cạnh hình chữ nhật, mỗi lần cắt chia một hình chữ nhật thành hai phần. Ta cần chia nhỏ hình chữ nhật ban đầu cho đến khi tất cả các phần đều là hình vuông, với số lượng hình vuông là ít nhất.

Đây là bài toán quy hoạch động kinh điển. Với một hình chữ nhật a × b:

• Nếu a = b thì nó đã là hình vuông, cần 1 hình.
• Nếu a ≠ b, ta phải cắt nó. Có hai hướng cắt:
  1. Cắt ngang (song song cạnh a): Chia thành hai hình a' × b và (a-a') × b.
  2. Cắt dọc (song song cạnh b): Chia thành hai hình a × b' và a × (b-b'). Số hình vuông tối thiểu của (a, b) là giá trị nhỏ nhất trong các cách cắt này cộng dồn.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (Top-down với Memoization)

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

int dp[1005][1005];

int main() {
    int a, b;
    cin >> a >> b;

    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            if (i == j) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = 1e9;

                // cắt ngang
                for (int k = 1; k < i; k++) {
                    dp[i][j] = min(dp[i][j],
                                   dp[k][j] + dp[i - k][j]);
                }

                // cắt dọc
                for (int k = 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j],
                                   dp[i][k] + dp[i][j - k]);
                }
            }
        }
    }

    cout << dp[a][b];
    return 0;
}

• Time Complexity: O(MN(M+N)) ~ O(10^9) trong trường hợp xấu nhất (M=N=1000). Tuy nhiên, với dữ liệu thực tế và cách tối ưu hóa vòng lặp (chỉ lặp đến i/2), độ phức tạp giảm đi đáng kể và có thể chấp nhận được.
• Space Complexity: O(M*N) ~ O(10^6) (khoảng 4MB)

Đây là phương pháp quy hoạch động từ dưới xuống (Bottom-up). Chúng ta điền vào bảng dp[i][j] cho tất cả các hình chữ nhật có kích thước từ 1x1 đến MxN.

1. Khởi tạo: Nếu hình chữ nhật là hình vuông (i == j) thì dp[i][j] = 1.
2. Các trường hợp khác: Gán giá trị vô cùng lớn (1e9).
3. Duyệt qua tất cả các vị trí cắt có thể:
   • Cắt ngang: Duyệt k từ 1 đến i-1, thử chia thành hai phần (k, j) và (i-k, j). Cập nhật dp[i][j] = min(dp[i][j], dp[k][j] + dp[i-k][j]).
   • Cắt dọc: Duyệt k từ 1 đến j-1, thử chia thành hai phần (i, k) và (i, j-k). Cập nhật dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j-k]).
4. Kết quả cuối cùng là dp[M][N].

Lưu ý: Code mẫu chỉ lặp k từ 1 đến i-1 (hoặc j-1). Thực tế ta có thể tối ưu bằng cách chỉ lặp đến i/2 (hoặc j/2) vì việc cắt ở vị trí k và i-k là tương đương.

Cách Quy hoạch động với tối ưu hóa lặp

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

int dp[1005][1005];

int main() {
    int m, n;
    cin >> m >> n;

    // Hoán đổi để m là cạnh dài hơn (không bắt buộc nhưng tiện cho vòng lặp)
    // Hoặc đơn giản là lặp theo chiều dài và chiều rộng

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dp[i][j] = 1;
                continue;
            }
            dp[i][j] = 1e9;

            // Tối ưu: Chỉ cần lặp đến i/2 (hoặc j/2)
            // Cắt ngang
            for (int k = 1; k <= i / 2; k++) {
                dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j]);
            }

            // Cắt dọc
            for (int k = 1; k <= j / 2; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k]);
            }
        }
    }

    cout << dp[m][n];
    return 0;
}

• Time Complexity: O(MN(M/2 + N/2)) ~ O(MN(M+N)/2). Chia đôi thời gian so với cách cơ bản.
• Space Complexity: O(M*N)

Đây là phiên bản cải tiến của phương pháp 1. Thay vì duyệt hết tất cả các vị trí cắt (từ 1 đến i-1), ta chỉ cần duyệt đến một nửa (1 đến i/2).

Giả sử cắt một hình a × b ngang thành a1 × b và a2 × b (với a1 + a2 = a). Nếu a1 < a2, thì trường hợp a1 × b và a2 × b đã được xét khi duyệt k = a1. Nếu a1 > a2, nó tương đương với trường hợp a2 × b và a1 × b (vì phép cộng ráp gọn). Do đó, chỉ cần xét một nửa các trường hợp là đủ.

Ví dụ: a=5, các cách cắt: (1,4) và (4,1) cho cùng kết quả, (2,3) và (3,2) cho cùng kết quả. Chỉ cần xét (1,4) và (2,3) là đủ.

Điều này giảm hệ số hằng số của độ phức tạp thời gian, giúp chương trình chạy nhanh hơn và an toàn hơn với giới hạn M, N = 1000.

Cách Giải thuật tham lam (Nhanh nhất)

#include <iostream>
using namespace std;

int solve(int m, int n) {
    // Dùng thuật toán Euclid để tìm ước lớn nhất
    // Số hình vuông tối thiểu = (m * n) / (gcd(m, n)^2)
    // Hoặc đơn giản là m / g + n / g - 1? Không, câu trả lời đúng là:
    // Nếu chia đôi được liên tục thì số lượng là max(m, n) / min(m, n) + ...
    // Thực chất bài toán này có lời giải tham lam: 
    // Cắt theo hình vuông lớn nhất có thể (kích thước gcd(m, n)).
    // Số lượng hình vuông = (m * n) / (gcd(m, n) * gcd(m, n)).
    // Tuy nhiên, lời giải trong các bài nộp là quy hoạch động.
    // Có một nhận xét quan trọng: Bài toán 'Cắt hình chữ nhật thành hình vuông ít nhất' 
    // thực chất là tìm số hình vuông cùng kích thước lớn nhất để lấp đầy.
    // Số hình vuông ít nhất = (m * n) / (gcd(m, n) ^ 2).
    // Ví dụ 5x6: gcd(5,6)=1 -> 30/1 = 30. Sai.
    // Ví dụ 6x10: gcd=2 -> 60/4 = 15. Sai.
    // Thực tế bài toán này là: Tìm số hình vuông (không nhất thiết cùng kích thước) ít nhất.
    // Nhận xét: Nếu ta dùng thuật toán Euclid:
    // 5x6: Cắt 5x5 (1 cái), còn 5x1. Cắt 5x1 thành 5 cái 1x1. Tổng 6.
    // Nhưng sample output là 5.
    // Sample 5x6 output 5. 
    // Cắt 5x6 -> Cắt dọc ở 5 -> 5x5 + 5x1. (1 + 5 = 6).
    // Cắt 5x6 -> Cắt ngang ở 3 -> 3x6 + 2x6.
    // 3x6: Cắt 3x3x2 -> 2 cái. 2x6: Cắt 2x2x3 -> 3 cái. Tổng 5.
    // Nhận xét: Bài toán này giống 'Minimum number of squares' trên Codeforces/SPOJ.
    // Công thức tối ưu: dp[i][j] = min(i, j) nếu i hoặc j chia hết cho còn lại? Không.
    // Công thức đúng cho 5x6 là 5.
    // Thuật toán Euclid: 
    // long long gcd(long long a, long long b) {
    //    if (b == 0) return a;
    //    return gcd(b, a % b);
    // }
    // Số hình vuông = (m * n) / (gcd(m, n) * gcd(m, n)) -> Sai với 5x6.
    // Phải dùng Quy hoạch động.

    // Code Quy hoạch động tối ưu:
    int dp[1001][1001];
    for(int i=0; i<=m; i++) {
        for(int j=0; j<=n; j++) {
            if(i==0 || j==0) dp[i][j] = 0;
            else if(i==j) dp[i][j] = 1;
            else {
                dp[i][j] = 1e9;
                // Cắt ngang
                for(int k=1; k<i; k++) 
                    dp[i][j] = min(dp[i][j], dp[k][j] + dp[i-k][j]);
                // Cắt dọc
                 for(int k=1; k<j; k++) 
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j-k]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << solve(m, n);
    return 0;
}

• Time Complexity: O(MN(M+N))
• Space Complexity: O(M*N)

Phương pháp này là Quy hoạch động cơ bản. Tuy nhiên, có một sự thật là bài toán này có thể giải bằng phương pháp tham lam nếu số hình vuông phải cùng kích thước. Nhưng ở đây các hình vuông có thể khác kích thước.

Có một nhận xét quan trọng để tối ưu code DP: Chỉ cần lặp một nửa vòng lặp.

Ngoài ra, có thể tối ưu thêm:

• Nếu i > j, ta chỉ cần xét việc cắt dọc (vì cắt ngang y hệt).
• Tuy nhiên, cách đơn giản nhất để đảm bảo đúng là dùng DP lặp tất cả các trường hợp.

Lưu ý quan trọng: Có một giải pháp dùng công thức toán học cho bài toán này, nhưng không hoàn toàn đơn giản. Tuy nhiên, với các giới hạn M, N <= 1000, DP là cách an toàn và dễ hiểu nhất.

Giải thích code:

• dp[i][j] lưu số hình vuông ít nhất để cắt i x j.
• Base case: dp[i][i] = 1.
• Quy hoạch: dp[i][j] = min(dp[k][j] + dp[i-k][j], dp[i][k] + dp[i][j-k]).

Đối với bài toán này, có một công thức khá thú vị: Nếu ta dùng Euclid để tìm gcd: long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); } Số hình vuông tối thiểu = (M * N) / (gcd(M, N) * gcd(M, N)). Chúng ta hãy thử với các trường hợp:

• 5x6: gcd=1 -> 30/1 = 30. -> Sai.
• 6x10: gcd=2 -> 60/4 = 15. -> Sai.

Vậy công thức Euclid chỉ đúng nếu các hình vuông phải cùng kích thước (để lấp đầy). Bài toán này yêu cầu "ít nhất" và các hình vuông có thể khác kích thước. Do đó, Quy hoạch động là phương pháp chính xác.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể chia nhỏ thành các bài toán con (quy hoạch động). Giá trị của một hình chữ nhật phụ thuộc vào giá trị của các hình chữ nhật nhỏ hơn.
• Chỉ cần xét các trường hợp cắt ở một nửa (từ 1 đến i/2) vì cắt ở vị trí k và i-k là tương đương về mặt số lượng hình vuông.
• Cơ sở của quy hoạch động là hình vuông (i = j) có giá trị là 1.

Lỗi thường gặp

• Lặp qua tất cả các vị trí cắt (từ 1 đến i-1) thay vì chỉ một nửa (1 đến i/2) có thể gây TLE (Time Limit Exceeded) hoặc chạy chậm với M, N lớn (1000).
• Quên xử lý trường hợp hình chữ nhật ban đầu đã là hình vuông (M == N) để trả về 1 ngay lập tức.
• Sử dụng các thuật toán khác (như Euclid) không phù hợp với yêu cầu của bài toán (có thể ra kết quả sai nếu các hình vuông không cần cùng kích thước).