Hướng dẫn giải của Mái che

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, Random_guy123, tranhaian173, BaoDuy12345

Hiểu bài toán

Bài toán yêu cầu tìm một hình chữ nhật con trong một lưới m x n sao cho diện tích của nó đúng bằng k và số lượng ô có cây (giá trị '1') bên trong là nhỏ nhất. Nếu không tồn tại hình chữ nhật nào có diện tích k, ta phải in ra -1. Các hình chữ nhật này có cạnh song song với cạnh của lưới.

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

Cách Brute Force với mảng cộng dồn (Prefix Sum)
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> grid(m);
    for (int i = 0; i < m; i++) cin >> grid[i];

    // Tạo mảng cộng dồn P
    // P[i][j] là tổng số cây từ (0,0) đến (i-1, j-1)
    vector<vector<int>> P(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int val = (grid[i-1][j-1] == '1' ? 1 : 0);
            P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + val;
        }
    }

    int min_trees = INT_MAX;
    bool found = false;

    // Duyệt qua tất cả các chiều cao h có thể của hình chữ nhật
    for (int h = 1; h <= m; h++) {
        if (k % h != 0) continue; // Diện tích k phải chia hết cho h
        int w = k / h;
        if (w > n) continue; // Chiều rộng không được vượt quá n

        // Duyệt tất cả các vị trí có thể cho hình chữ nhật h x w
        for (int i = h; i <= m; i++) {
            for (int j = w; j <= n; j++) {
                // Tính số cây trong hình chữ nhật (i-h+1, j-w+1) đến (i, j)
                int trees = P[i][j] - P[i-h][j] - P[i][j-w] + P[i-h][j-w];
                min_trees = min(min_trees, trees);
                found = true;
            }
        }
    }

    if (!found) cout << -1 << endl;
    else cout << min_trees << endl;

    return 0;
}
  • Time Complexity: O(m * n * sqrt(k)) hoặc O(m * n * sốlượngướccủak). Trong trường hợp xấu nhất (k = m*n), độ phức tạp là O(m^2 * n^2). Với m, n <= 500, trường hợp xấu nhất này quá chậm (khoảng 6.25 * 10^9 thao tác). Tuy nhiên, với các test thông thường hoặc k có ít ước, nó có thể chạy được.
  • Space Complexity: O(m * n) để lưu mảng cộng dồn.

Cách tiếp cận này sử dụng mảng cộng dồn (2D Prefix Sum) để tính số lượng cây trong một hình chữ nhật bất kỳ trong thời gian O(1). Sau đó, ta duyệt qua tất cả các chiều cao h mà k chia hết. Với mỗi h, ta tính chiều rộng w = k / h. Tiếp theo, ta duyệt qua tất cả các vị trí (góc dưới bên phải) có thể của hình chữ nhật h x w trong lưới và tính số cây bằng mảng cộng dồn. Ta cập nhật kết quả tối thiểu. Độ phức tạp phụ thuộc vào số lượng vị trí và số lượng ước của k.

Cách Tối ưu với Sliding Window (Hàng và Cột)
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> grid(m);
    for (int i = 0; i < m; i++) cin >> grid[i];

    int min_trees = INT_MAX;
    bool found = false;

    // Duyệt qua tất cả các chiều cao h
    for (int h = 1; h <= m; h++) {
        if (k % h != 0) continue;
        int w = k / h;
        if (w > n) continue;

        // Tạo mảng cộng dồn theo chiều dọc (dọc theo các hàng)
        // col_sum[j] sẽ lưu tổng số cây trong cột j từ hàng i-h+1 đến i
        vector<int> col_sum(n + 1, 0);

        // Khởi tạo cho cửa sổ trượt đầu tiên (hàng 1 đến h)
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= h; i++) {
                col_sum[j] += (grid[i-1][j-1] == '1' ? 1 : 0);
            }
        }

        // Duyệt các cửa sổ theo chiều ngang (Sliding Window Horizontal)
        // Tính tổng đầu tiên của cột 1 đến w
        int current_sum = 0;
        for (int j = 1; j <= w; j++) current_sum += col_sum[j];
        min_trees = min(min_trees, current_sum);
        found = true;

        // Trượt sang phải
        for (int j = w + 1; j <= n; j++) {
            current_sum += col_sum[j] - col_sum[j - w];
            min_trees = min(min_trees, current_sum);
        }

        // Trượt xuống dưới (Sliding Window Vertical)
        for (int i = h + 1; i <= m; i++) {
            // Cập nhật cột sum cho hàng mới
            for (int j = 1; j <= n; j++) {
                col_sum[j] += (grid[i-1][j-1] == '1' ? 1 : 0) - (grid[i-h-1][j-1] == '1' ? 1 : 0);
            }

            // Tính lại tổng cho hàng mới
            current_sum = 0;
            for (int j = 1; j <= w; j++) current_sum += col_sum[j];
            min_trees = min(min_trees, current_sum);

            for (int j = w + 1; j <= n; j++) {
                current_sum += col_sum[j] - col_sum[j - w];
                min_trees = min(min_trees, current_sum);
            }
        }
    }

    if (!found) cout << -1 << endl;
    else cout << min_trees << endl;

    return 0;
}
  • Time Complexity: O(m * n * sqrt(k)) hoặc O(m * n * sốlượngướccủak).
  • Space Complexity: O(n) (hoặc O(m*n) nếu dùng mảng phụ lưu grid).

Thay vì dùng mảng cộng dồn 2D để truy vấn O(1) cho mỗi hình chữ nhật, ta sử dụng kỹ thuật Sliding Window. Với mỗi chiều cao h cố định:

  1. Tính mảng col_sum lưu tổng số cây của mỗi cột trong một cửa sổ chiều cao h (ban đầu từ hàng 1 đến h).
  2. Sử dụng Sliding Window trên chiều ngang để tìm dải w cột liên tiếp có tổng nhỏ nhất. Cần O(n) cho mỗi hàng.
  3. Khi trượt xuống hàng tiếp theo, cập nhật col_sum cho mỗi cột (thêm hàng mới, bớt hàng cũ) và lặp lại bước 2. Cách này tối ưu hơn về mặt truy vấn nhưng vẫn giữ nguyên độ phức tạp tổng thể do vẫn phải duyệt qua tất cả các h và các vị trí.
Cách Tối ưu Sliding Window với 2D Prefix Sum (Optimized)
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> grid(m);
    for (int i = 0; i < m; i++) cin >> grid[i];

    // Mảng cộng dồn P
    vector<vector<int>> P(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + (grid[i-1][j-1] == '1');
        }
    }

    int min_trees = INT_MAX;
    bool found = false;

    // Duyệt qua tất cả các chiều cao h
    for (int h = 1; h <= m; h++) {
        if (k % h != 0) continue;
        int w = k / h;
        if (w > n) continue;

        // Tính số cây trong các cột dọc h x 1 (từ hàng 1 đến h)
        // Sử dụng mảng phụ col_val thay vì tính đi tính lại
        vector<int> col_val(n + 1);
        for (int j = 1; j <= n; j++) {
            col_val[j] = P[h][j] - P[0][j] - P[h][j-1] + P[0][j-1];
        }

        // Sliding window ngang cho hàng đầu tiên
        int current_sum = 0;
        for (int j = 1; j <= w; j++) current_sum += col_val[j];
        min_trees = min(min_trees, current_sum);
        found = true;

        for (int j = w + 1; j <= n; j++) {
            current_sum += col_val[j] - col_val[j - w];
            min_trees = min(min_trees, current_sum);
        }

        // Sliding window xuống dưới
        for (int i = h + 1; i <= m; i++) {
            // Cập nhật cột: thay thế giá trị cột cũ bằng giá trị cột mới (từ hàng i-h+1 đến i)
            // Thay vì dùng grid, dùng P để tính nhanh giá trị cột mới
            for (int j = 1; j <= n; j++) {
                int new_col_val = P[i][j] - P[i-h][j] - P[i][j-1] + P[i-h][j-1];
                col_val[j] = new_col_val;
            }

            // Tính lại sliding window ngang
            current_sum = 0;
            for (int j = 1; j <= w; j++) current_sum += col_val[j];
            min_trees = min(min_trees, current_sum);

            for (int j = w + 1; j <= n; j++) {
                current_sum += col_val[j] - col_val[j - w];
                min_trees = min(min_trees, current_sum);
            }
        }
    }

    if (!found) cout << -1 << endl;
    else cout << min_trees << endl;

    return 0;
}
  • Time Complexity: O(m * n * sqrt(k))
  • Space Complexity: O(m * n)

Đây là cách tiếp cận tối ưu nhất trong các solution được cung cấp. Nó kết hợp Sliding Window với mảng cộng dồn.

  • Thay vì duyệt từng ô để tính col_sum, ta dùng truy vấn O(1) từ mảng P để lấy tổng số cây trong một cột chiều cao h tại vị trí (i, j).
  • Với mỗi h cố định, ta tính mảng col_val cho hàng đầu tiên, rồi dùng Sliding Window ngang.
  • Khi trượt xuống hàng i, ta cập nhật lại mảng col_val cho từng cột bằng truy vấn O(1) từ P tương ứng với cửa sổ hàng (i-h+1, i). Sau đó lại dùng Sliding Window ngang. Cách này giảm thời gian tính toán bên trong vòng lặp so với cách Sliding Window thô, nhưng về tổng thể độ phức tạp vẫn là O(m * n * sqrt(k)) do số lượng h cần duyệt.

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

Cách tiếp cận Time Space Tên
1 O(m * n * sqrt(k)) hoặc O(m * n * sốlượngướccủak). Trong trường hợp xấu nhất (k = m*n), độ phức tạp là O(m^2 * n^2). Với m, n <= 500, trường hợp xấu nhất này quá chậm (khoảng 6.25 * 10^9 thao tác). Tuy nhiên, với các test thông thường hoặc k có ít ước, nó có thể chạy được. O(m * n) để lưu mảng cộng dồn. Brute Force với mảng cộng dồn (Prefix Sum)
2 O(m * n * sqrt(k)) hoặc O(m * n * sốlượngướccủak). O(n) (hoặc O(m*n) nếu dùng mảng phụ lưu grid). Tối ưu với Sliding Window (Hàng và Cột)
3 O(m * n * sqrt(k)) O(m * n) Tối ưu Sliding Window với 2D Prefix Sum (Optimized)

Bài học kinh nghiệm

  • Sử dụng mảng cộng dồn 2D (2D Prefix Sum) để tính tổng số cây trong bất kỳ hình chữ nhật con nào trong thời gian O(1).
  • Biến đổi công thức diện tích k = h * w cho phép duyệt qua các chiều cao h (và chiều rộng w tương ứng) thay vì duyệt qua tất cả các kích thước hình chữ nhật, giảm đáng kể số lần lặp.
  • Kỹ thuật Sliding Window (Cửa sổ trượt) có thể được áp dụng để tối ưu quá trình tìm dải cột liên tiếp có tổng nhỏ nhất, nhưng với ràng buộc k cố định, việc kết hợp với duyệt h và w là quan trọng.

Lỗi thường gặp

  • Nếu chỉ duyệt Brute Force thuần túy (O(m^2 * n^2)) mà không dùng mảng cộng dồn hoặc không tối ưu theo h, w, chương trình sẽ bị Time Limit Exceeded (TLE) với m, n lên tới 500.
  • Lỗi truy cập mảng cộng dồn: Sai lệch chỉ số (off-by-one) khi tính toán tổng theo công thức P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1].
  • Không kiểm tra trường hợp không tồn tại hình chữ nhật: Nếu không có cặp h, w nào thỏa mãn k % h == 0 và w <= n, h <= m, cần in ra -1.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.