Editorial for tabledel: Xóa phần tử trong ma trận

Hiểu bài toán

Cho một bảng kích thước n x m, trong đó có k ô màu đen tại các vị trí (xi, yi). Các ô còn lại là trắng. Bạn có thể thực hiện 2 loại thao tác: xóa một dòng chỉ toàn ô trắng, hoặc xóa một cột chỉ toàn ô trắng. Mục tiêu là tìm số ô còn lại tối thiểu sau khi thực hiện các thao tác.

Phân tích:

• Một dòng có thể bị xóa nếu TẤT CẢ các ô trong dòng đó đều trắng. Nghĩa là dòng đó không chứa bất kỳ ô đen nào.
• Tương tự, một cột có thể bị xóa nếu trong cột đó KHÔNG có ô đen nào.
• Sau khi xóa các dòng/cột trắng, các ô đen còn lại nằm ở các dòng và cột chưa bị xóa.
• Gọi R là tập hợp các dòng CHƯA bị xóa (tức là có ít nhất 1 ô đen). Gọi C là tập hợp các cột CHƯA bị xóa.
• Số ô đen còn lại chính bằng số cách chọn một dòng trong R và một cột trong C, tức là |R| * |C|.
• Để số ô còn lại là nhỏ nhất, ta cần |R| và |C| nhỏ nhất.
• |R| chính là số lượng dòng khác nhau xuất hiện trong danh sách các ô đen. Tương tự, |C| là số lượng cột khác nhau.

Ví dụ: Input: n=3, m=4, k=3, blacks = {(2,1), (2,4), (3,3)}

• Các dòng có ô đen là {2, 3} -> |R| = 2.
• Các cột có ô đen là {1, 3, 4} -> |C| = 3.
• Số ô còn lại = 2 * 3 = 6.

Các dòng/cột không chứa ô đen sẽ bị xóa tự động vì chúng không ảnh hưởng đến các ô đen.

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

Cách Sử dụng Hash Set để đếm số lượng dòng/cột khác nhau

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

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

    int n, m, k;
    cin >> n >> m >> k;

    set<int> rows;
    set<int> cols;

    for (int i = 0; i < k; ++i) {
        int r, c;
        cin >> r >> c;
        rows.insert(r);
        cols.insert(c);
    }

    cout << (long long)rows.size() * cols.size() << endl;

    return 0;
}

• Time Complexity: O(k log k)
• Space Complexity: O(k)

Cách tiếp cận này sử dụng hai cấu trúc dữ liệu set (hoặc unordered_set) để lưu trữ các dòng và cột khác nhau chứa ô đen.

1. Khởi tạo hai set rỗng: rows và cols.
2. Đọc từng ô đen (x, y):
   • Thêm dòng x vào set rows.
   • Thêm cột y vào set cols.
   • Set tự động loại bỏ các phần tử trùng lặp.
3. Sau khi đọc hết k ô đen:
   • rows.size() chính là số lượng dòng khác nhau có ô đen (|R|).
   • cols.size() chính là số lượng cột khác nhau có ô đen (|C|).
4. Kết quả là tích của hai số này.

Độ phức tạp: Với set thường, thao tác chèn mất O(log k), tổng thời gian là O(k log k). Với unordered_set, trung bình O(k). Do k <= 10^5, cả hai đều chấp nhận được.

Cách Mảng đánh dấu (Boolean Array)

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

bool row_has_black[100005];
bool col_has_black[100005];

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

    int n, m, k;
    cin >> n >> m >> k;

    // Đọc dữ liệu và đánh dấu
    for (int i = 0; i < k; ++i) {
        int r, c;
        cin >> r >> c;
        row_has_black[r] = true;
        col_has_black[c] = true;
    }

    // Đếm số dòng và cột có ô đen
    long long cnt_rows = 0;
    for (int i = 1; i <= n; ++i) {
        if (row_has_black[i]) cnt_rows++;
    }

    long long cnt_cols = 0;
    for (int i = 1; i <= m; ++i) {
        if (col_has_black[i]) cnt_cols++;
    }

    cout << cnt_rows * cnt_cols << endl;

    return 0;
}

• Time Complexity: O(n + m + k)
• Space Complexity: O(n + m)

Cách tiếp cận này sử dụng các mảng boolean (hoặc bitset) để đánh dấu xem một dòng hoặc cột cụ thể có chứa ô đen hay không.

1. Khởi tạo hai mảng row_has_black và col_has_black với kích thước tương ứng n và m, giá trị ban đầu là false.
2. Duyệt qua k ô đen:
   • Với ô (r, c), đặt row_has_black[r] = true và col_has_black[c] = true.
3. Duyệt qua các mảng từ 1 đến n (và 1 đến m) để đếm số lượng true.
   • Biến đếm cnt_rows tăng mỗi khi gặp row_has_black[i] == true.
   • Biến đếm cnt_cols tăng mỗi khi gặp col_has_black[i] == true.
4. Tính tích cnt_rows * cnt_cols.

Độ phức tạp: Cần duyệt qua k ô đen để đánh dấu (O(k)), sau đó duyệt qua n dòng và m cột để đếm (O(n + m)). Tổng thời gian là O(n + m + k). Khoảng cách nhớ O(n + m).

Cách Đếm trực tiếp trong một vòng lặp

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

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

    long long n, m, k, x, y;
    cin >> n >> m >> k;

    // u[i] = 1 nếu dòng i chưa có ô đen, 0 nếu có
    // v[j] = 1 nếu cột j chưa có ô đen, 0 nếu có
    vector<int> u(n + 1, 1), v(m + 1, 1);

    for (int i = 0; i < k; ++i) {
        cin >> x >> y;
        u[x] = 0;
        v[y] = 0;
    }

    long long cnt_rows = 0, cnt_cols = 0;

    // Đếm số dòng bị xóa (tức là vẫn còn 1)
    // Số dòng giữ lại = n - số dòng bị xóa
    for (int i = 1; i <= n; ++i) {
        if (u[i]) cnt_rows++; // cnt_rows đếm dòng rỗng
    }

    // Đếm số cột bị xóa
    for (int i = 1; i <= m; ++i) {
        if (v[i]) cnt_cols++; // cnt_cols đếm cột rỗng
    }

    // Số dòng giữ lại là n - cnt_rows
    // Số cột giữ lại là m - cnt_cols
    // Kết quả = (n - cnt_rows) * (m - cnt_cols)
    cout << (n - cnt_rows) * (m - cnt_cols);

    return 0;
}

• Time Complexity: O(n + m + k)
• Space Complexity: O(n + m)

Đây là một biến thể của phương pháp mảng đánh dấu, nhưng thay vì đếm các dòng/cột có ô đen, ta đếm các dòng/cột không có ô đen.

1. Khởi tạo mảng u (cho dòng) và v (cho cột) với giá trị 1. 1 nghĩa là dòng/cột này 'trống' (chưa có ô đen).
2. Khi đọc ô đen (x, y):
   • Đặt u[x] = 0 (dòng x không còn trống).
   • Đặt v[y] = 0 (cột y không còn trống).
3. Duyệt mảng u để đếm số dòng còn giữ giá trị 1 (số dòng trắng tinh khiết).
4. Duyệt mảng v để đếm số cột còn giữ giá trị 1 (số cột trắng tinh khiết).
5. Số dòng/cột có ô đen = Tổng - Số trắng tinh khiết.

Cách này cũng có độ phức tạp O(n + m + k) và O(n + m) bộ nhớ.

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

Bài học kinh nghiệm

• Vấn đề quy về đếm số lượng dòng và cột khác nhau có chứa ít nhất một ô đen. Số ô đen còn lại chính là tích của hai số này.
• Có thể dùng集合 (Set) để loại bỏ trùng lặp tự động hoặc mảng đánh dấu để đếm.
• Các dòng/cột không chứa ô đen bị xóa hoàn toàn, không ảnh hưởng đến các ô đen còn lại.

Lỗi thường gặp

• Sử dụng int để lưu kết quả cuối cùng có thể gây tràn số vì n * m có thể lên tới 10^10. Cần dùng long long.
• Lưu ý thứ tự nhập vào (n, m, k) có thể bị hoán đổi trong một số bài viết mẫu (ví dụ Solution 2 nhập cin >> m >> n >> k). Cần kiểm tra đề bài chính xác.
• Quên khởi tạo mảng hoặc set có thể gây lỗi runtime hoặc giá trị rác.