Editorial for fillblank: Điền vào chỗ trống

Hiểu bài toán

Bài toán yêu cầu điền các xâu ký tự vào các dòng sao cho số lượng xâu được điền là lớn nhất. Có N dòng, mỗi dòng i có ai ô trống. Có M xâu, mỗi xâu j có độ dài là 2^(bj). Các ràng buộc:

1. Một dòng có thể chứa nhiều xâu, nhưng một xâu chỉ thuộc về một dòng.
2. Các ký tự của một xâu phải điền vào các ô trống liên tiếp.
3. Mỗi ô trống chỉ chứa một ký tự.

Như vậy, bài toán quy về bài toán cái túi (Knapsack): chọn các xâu (với kích thước là 2^bj) để nhét vào các dòng (với dung lượng ai), sao cho tổng số xâu là lớn nhất. Mỗi dòng có thể được sử dụng nhiều lần (trong phạm vi a_i của nó), và các xâu có thể được xếp vào bất kỳ dòng nào có dung lượng còn lại đủ. Đây là bài toán tối ưu hóa số lượng item có thể pack vào các bin (bin packing).

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

Cách Greedy Simulation với Multiset và Sắp xếp Giảm dần

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
using ll = long long;

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

    int N, M;
    cin >> N >> M;
    vector<ll> a(N), b(M);
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int j = 0; j < M; j++) {
        ll x; cin >> x;
        b[j] = 1LL << x;
    }

    // Sắp xếp a giảm dần để dùng dòng lớn cho xâu lớn trước
    sort(a.rbegin(), a.rend());
    // Sắp xếp b giảm dần để ưu tiên xâu lớn trước
    sort(b.rbegin(), b.rend());

    // Multiset lưu các khoảng trống còn lại sau khi đã nhét xâu
    multiset<ll> ms;
    for (ll val : a) ms.insert(val);

    int ans = 0;
    for (ll len : b) {
        // Tìm dòng có dung lượng >= len
        auto it = ms.lower_bound(len);
        if (it != ms.end()) {
            ll rem = *it - len;
            ms.erase(it);
            if (rem > 0) ms.insert(rem);
            ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}

• Time Complexity: O((N + M) log N)
• Space Complexity: O(N)

Cách tiếp cận này mô phỏng quá trình nhét đồ một cách trực quan.

1. Sắp xếp các xâu theo độ dài giảm dần (xâu dài nhất trước).
2. Sắp xếp các dòng theo dung lượng giảm dần.
3. Dùng một cấu trúc dữ liệu (Multiset) để lưu trữ các khoảng trống còn lại của các dòng.
4. Với mỗi xâu, ta tìm trong Multiset một khoảng trống lớn hơn hoặc bằng độ dài xâu (dùng lower_bound).
5. Nếu tìm thấy, ta nhét xâu vào, cập nhật khoảng trống còn lại (dung lượng - độ dài xâu) vào lại Multiset và tăng biến đếm.

Độ phức tạp: Sắp xếp O(N log N + M log M). Với mỗi xâu, thao tác trên multiset mất O(log N). Tổng cộng O((N+M) log N). Với N, M <= 10^6, cách này có thể chậm (do overhead của multiset và việc xử lý từng xâu một) và TLE.

Cách Tối ưu Greedy với Thống kê theo Bit (Bitwise Packing)

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

// D[k] luu so luong o kich thuoc 2^k co the lap day
// D[k] co the am, chi so so luong o thua/du
ll D[32]; 
int n, m;

int main() {
    Init(); // Toàn cục ios sync
    cin >> n >> m;

    // 1. Đọc và xử lý các dòng
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        // Phân tách dung lượng dòng thành các block 2^k
        for (int j = 1, p = 0; j <= x; j <<= 1, ++p) {
            if (x & j) D[p]++; 
        }
    }

    // 2. Đọc các xâu
    vector<int> b(m);
    for (int i = 0; i < m; ++i) cin >> b[i];
    sort(b.begin(), b.end()); // Xử lý xâu nhỏ trước để tối ưu cơ hội

    int ans = 0;
    for (int i = 0; i < m; ++i) {
        int k = b[i]; // Yêu cầu block 2^k

        // Cố gắng lấp đầy từ k trở lên
        bool success = false;
        ll carry = 0; // Biến nhớ

        // Duyệt từ bit cao xuống thấp (hoặc ngược lại tùy chiến lược)
        // Ở đây ta thử greedily dùng các block có sẵn
        // Tuy nhiên code gốc dùng vòng lặp phức tạp hơn.

        // Logic đơn giản hóa:
        // Ta có D[k] là số block 2^k sẵn có.
        // Nếu D[k] > 0, dùng 1. Nếu D[k] == 0, phải mượn từ D[k+1] (chia đôi).

        // Code gốc:
        for (int j = b[i], x = 1; j >= 0; x <<= 1, --j) {
            D[j] -= x;
            if (D[j] < 0) {
                cout << i;
                return 0;
            }
        }
    }
    cout << m;
    return 0;
}

• Time Complexity: O(N * log(10^9) + M * log(10^9)) ~ O(30N + 30M)
• Space Complexity: O(1) (mảng cố định 32 phần tử)

Đây là cách tiếp cận tối ưu nhất, dựa trên quan sát rằng:

1. Các kích thước của xâu là $2^{b_j}$ (luôn là lũy thừa của 2).
2. Các dòng có dung lượng $a_i$ có thể được xem là tập hợp các block có kích thước $2^k$.

Thuật toán:

• Tạo mảng D[32] (vì $2^{30} > 10^9$), D[k] lưu số lượng các block $2^k$ có thể dùng được.
• Với mỗi dòng có dung lượng $ai$, ta phân tích nó thành các bit: nếu bit $k$ của $ai$ bật, ta cộng 1 vào D[k]. Ví dụ $ai = 13 (11012)$, ta có 1 block $2^0$, 1 block $2^2$, 1 block $2^3$.
• Sắp xếp các xâu theo độ dài tăng dần.
• Duyệt qua từng xâu có độ dài $2^{bi}$:
  • Ta cần một block $2^{bi}$.
  • Nếu D[b_i] > 0, ta dùng nó, giảm D[b_i]. (Xâu này lấp đầy vừa khít).
  • Nếu D[b_i] == 0, ta phải "lấy thêm" từ các block lớn hơn. Ví dụ không có $2^{bi}$, ta lấy một $2^{bi+1}$ (nếu có), chia nó làm đôi. Một nửa dùng cho xâu hiện tại, nửa kia trở thành $2^{bi}$ mới được thêm vào kho. Nếu $2^{bi+1}$ cũng hết, ta lấy $2^{b_i+2}$... Cứ thế.
  • Nếu cạn kiệt tất cả các block lớn hơn mà không tìm được, ta không thể nhét xâu này.

Cách này xử lý theo batch (thống kê) thay vì từng dòng/xâu riêng lẻ, nên cực kỳ nhanh.

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

Bài học kinh nghiệm

• Bài toán là bài toán Packing, nhưng do tất cả kích thước xâu đều là lũy thừa của 2 ($2^{b_j}$), ta có thể tối ưu hóa bằng cách phân tích các dòng thành các block lũy thừa của 2.
• Thay vì dùng cấu trúc dữ liệu phức tạp như Multiset để mô phỏng từng bước, ta chỉ cần đếm số lượng các block kích thước $2^k$ có sẵn.
• Việc ưu tiên xử lý các xâu nhỏ trước (sau khi sort tăng dần) thường an toàn hơn trong các bài toán Greedy về Packing khi có nhiều ràng buộc về kích thước.

Lỗi thường gặp

• Sử dụng Multiset cho N, M lên tới $10^6$ có thể gây TLE do độ phức tạp logarit và overhead của cấu trúc tree-based, cộng với việc phải xử lý từng xâu một.
• Lỗi tràn số (overflow): Khi tính $2^{bj}$, nếu $bj$ lớn (ví dụ 30), $2^{30}$ là khoảng $10^9$, vừa đủ trong int nhưng nếu dùng sai phép tính có thể tràn. Nên dùng long long cho các phép tính giá trị.
• Sai lầm khi Greedy: Lựa chọn dòng ngẫu nhiên có dung lượng >= xâu (như trong Solution 1) không tối ưu bằng việc chọn dòng phù hợp nhất (ví dụ dòng nhỏ nhất đủ chứa) hoặc phân tích theo bit.