Editorial for filedel: Dọn dẹp máy tính

Hiểu bài toán

Một hệ thống có N tập tin, mỗi tập tin có tên là một xâu kí tự. Có Q thao tác xóa, mỗi thao tác xóa một kí tự c. Khi thực hiện thao tác xóa kí tự c, tất cả các tập tin đang còn lại mà trong tên có chứa kí tự c sẽ bị xóa. Sau mỗi thao tác, yêu cầu in ra số lượng tập tin còn lại.

Lưu ý quan trọng: Các thao tác xóa có hiệu lực trên chính danh sách các file còn lại ở thời điểm thực hiện thao tác đó. Tuy nhiên, một khi một file đã bị xóa thì nó sẽ không còn trong danh sách ở các bước sau.

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

Cách Mô phỏng với đánh dấu (Brute Force)

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

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

    int n, q;
    cin >> n >> q;
    vector<string> s(n);
    for(int i = 0; i < n; i++) cin >> s[i];

    vector<bool> deleted(n, false);
    int remaining = n;

    while(q--) {
        char c;
        cin >> c;
        for(int i = 0; i < n; i++) {
            if (!deleted[i]) {
                bool has_c = false;
                for(char x : s[i]) {
                    if (x == c) {
                        has_c = true;
                        break;
                    }
                }
                if (has_c) {
                    deleted[i] = true;
                    remaining--;
                }
            }
        }
        cout << remaining << "\n";
    }
    return 0;
}

• Time Complexity: O(Q * N * L) ~ O(10^8 - 10^9)
• Space Complexity: O(N * L)

Cách tiếp cận trực tiếp nhất là mô phỏng y như đề bài. Duyệt qua từng thao tác xóa. Với mỗi thao tác, duyệt qua tất cả các file. Nếu file đó chưa bị xóa và chứa kí tự cần xóa, ta đánh dấu file đó là đã xóa và giảm biến đếm số file còn lại. Độ phức tạp thời gian là O(Q * N * L) do với mỗi truy vấn, ta duyệt qua N file và kiểm tra độ dài xâu L. Với N, Q <= 100000, cách này chắc chắn bị TLE.

Cách Hash Map theo kí tự

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

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

    int N, Q;
    cin >> N >> Q;
    vector<string> name(N);
    for (int i = 0; i < N; i++) {
        cin >> name[i];
    }

    // Map mỗi ký tự 'a'-'z' đến danh sách các index file chứa nó
    vector<vector<int>> occ(26);
    for (int i = 0; i < N; i++) {
        // Duyệt qua các ký tự duy nhất của file để thêm vào occ
        vector<bool> seen(26, false);
        for (char c : name[i]) {
            if (!seen[c - 'a']) {
                occ[c - 'a'].push_back(i);
                seen[c - 'a'] = true;
            }
        }
    }

    vector<bool> alive(N, true);
    int aliveCount = N;

    while (Q--) {
        char c;
        cin >> c;
        int x = c - 'a';

        if (!occ[x].empty()) {
            for (int id : occ[x]) {
                if (alive[id]) {
                    alive[id] = false;
                    aliveCount--;
                }
            }
            // Quan trọng: Xóa danh sách để tránh lặp lại trong tương lai
            occ[x].clear();
        }
        cout << aliveCount << "\n";
    }
    return 0;
}

• Time Complexity: O(N * L + Q)
• Space Complexity: O(N * L)

Tối ưu hóa mô phỏng. Thay vì duyệt toàn bộ N file mỗi khi có truy vấn, ta预计算 (precompute) cho mỗi kí tự từ 'a' đến 'z' danh sách các file chứa kí tự đó. Khi nhận truy vấn xóa kí tự c, ta chỉ cần duyệt qua danh sách đã lưu sẵn. Để tránh xóa trùng lặp và tốn thời gian ở các truy vấn sau, ta cần đánh dấu các file đã xóa (mảng alive) và quan trọng là sau khi xử lý xong một kí tự c, ta phải xóa danh sách của c đi (hoặc đánh dấu là c đã được xử lý) vì các file chứa c đã bị xóa hết rồi, không cần xử lý lại.

Cách Bitset

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

const int MAXN = 100005;
bitset<MAXN> mark[26]; // mark[c] = bitset các từ có ký tự c

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

    int n, t;
    cin >> n >> t;

    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        vector<bool> seen(26, false);
        for (char c : s) {
            if (!seen[c - 'a']) {
                mark[c - 'a'].set(i);
                seen[c - 'a'] = true;
            }
        }
    }

    bitset<MAXN> removed; // các từ đã “loại bỏ”
    while (t--) {
        char c; cin >> c;
        removed |= mark[c - 'a'];
        cout << n - (int)removed.count() << "\n";
    }
}

• Time Complexity: O(N * L + Q * (N/64))
• Space Complexity: O(26 * N)

Sử dụng cấu trúc dữ liệu Bitset. Tạo một bitset cho mỗi kí tự, trong đó bit thứ i là 1 nếu file thứ i chứa kí tự đó. Khi có truy vấn xóa kí tự c, ta thực hiện phép toán bitwise OR giữa bitset tổng các file đã xóa (removed) và bitset của kí tự c. Số file còn lại là N - số bit 1 trong removed. Cách này rất nhanh về mặt lý thuyết do các phép toán bit chạy song song (thường xử lý 64 bit một lúc). Tuy nhiên, trong thực tế với C++ hiện đại, giải pháp Hash Map (Approach 2) thường chạy nhanh và ổn định do chi phí overhead của Bitset và cách truy cập bộ nhớ.

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

Bài học kinh nghiệm

• Bài toán có thể được coi là bài toán tập hợp (Set operations). Mỗi file là một phần tử, mỗi truy vấn xóa kí tự c là loại bỏ các phần tử thuộc tập hợp 'File chứa kí tự c' ra khỏi tập hợp hiện tại.
• Vì tên file rất ngắn (độ dài <= 8), số lượng kí tự khác nhau trong một file rất ít. Ta có thể precompute thông tin để tránh việc kiểm tra lại nhiều lần.
• Một kí tự chỉ cần được xử lý một lần duy nhất. Sau khi xử lý xong kí tự c, tất cả các file chứa c đều đã bị xóa, nên các truy vấn sau đó với ký tự c sẽ không xóa thêm file nào.

Lỗi thường gặp

• Xử lý trùng lặp: Nếu một file chứa kí tự c, và ta xử lý truy vấn c nhiều lần, ta không được giảm biến đếm nhiều lần cho cùng một file. Cần có cơ chế đánh dấu file đã xóa (mảng deleted hoặc alive).
• Tính đúng đắn của thứ tự xóa: Cần đảm bảo rằng file bị xóa là do nó còn sống ở thời điểm truy vấn đó. Approaches 2 và 3 đều xử lý đúng vấn đề này.
• Lưu ý Input/Output: Với N, Q lên tới 100,000, cần dùng fast I/O (ios_base::sync_with_stdio(false); cin.tie(0);) để tránh TLE.