Editorial for fword: Khôi phục xâu 2

Hiểu bài toán

Bài toán yêu cầu khôi phục một xâu ký tự ban đầu bị che mờ một số vị trí. Ta có:

• Xâu s độ dài N chứa các ký tự thường và ký tự '#' (bị mờ).
• M vị trí bị mờ, mỗi vị trí có K ký tự候选 (abc...
• Các vị trí bị mờ được đánh dấu theo thứ tự từ trái sang phải trong s.
• Xếp hạng X của từ cần tìm trong danh sách các từ có thể tạo ra (sắp xếp theo thứ tự từ điển).

Ví dụ: s = "fr#e#ontest", các gợi ý là defg và abcd. Các từ tạo ra sẽ là:

1. frdeaontest
2. frdebontest
3. frdecontest
4. frdedontest
5. freeaontest
6. freebontest
7. freecontest ... Ta cần tìm từ thứ X.

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

Cách Quy hoạch động từ phải sang trái (DP)

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

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

    int N, M, K;
    long long X;
    cin >> N >> M >> K >> X;

    string s;
    cin >> s;

    vector<string> choices(M);
    for (int i = 0; i < M; i++) {
        cin >> choices[i];
        sort(choices[i].begin(), choices[i].end()); 
    }

    vector<int> pos;
    for (int i = 0; i < N; i++) {
        if (s[i] == '#') pos.push_back(i);
    }

    // Tính số lượng tổ hợp có thể có từ mỗi vị trí mờ về cuối
    // power[i] = số cách điền từ vị trí mờ thứ i đến hết
    vector<long long> power(M + 1, 1);
    for (int i = M - 1; i >= 0; i--) {
        power[i] = power[i + 1] * K;
        if (power[i] > 1e9 + 7) power[i] = 1e9 + 7; // Tràn số, chỉ cần quan tâm giá trị lớn hơn X
    }

    // Duyệt từng vị trí mờ từ đầu đến cuối
    for (int i = 0; i < M; i++) {
        for (char c : choices[i]) {
            long long cnt = power[i + 1]; // Số cách cho các vị trí sau
            if (X > cnt) {
                X -= cnt; // Nếu X lớn hơn số cách này, bỏ qua ký tự hiện tại
            } else {
                s[pos[i]] = c; // Chọn ký tự hiện tại
                break;
            }
        }
    }

    cout << s;
    return 0;
}

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

Phương pháp này dựa trên việc đếm số lượng xâu có thể tạo ra từ các vị trí bị mờ.

1. Tìm vị trí: Đầu tiên, lưu lại vị trí các ký tự '#' trong xâu s.
2. Tính số lượng tổ hợp: Tính power[i] là số cách điền cho các vị trí từ i đến M-1. Nếu power[i] quá lớn (> 10^9), ta có thể gán nó bằng một giá trị lớn (ví dụ 10^9 + 7) vì ta chỉ cần so sánh với X.
3. Xây dựng xâu: Duyệt qua từng vị trí mờ từ đầu tiên đến cuối cùng (từ i = 0 đến M-1):
   • Với mỗi ký tự c trong danh sách候选 của vị trí hiện tại (đã sắp xếp):
     • Tính số xâu có thể tạo ra nếu chọn các ký tự tiếp theo trong danh sách hoặc các vị trí sau: cnt = power[i+1].
     • Nếu X > cnt, điều này có nghĩa là từ thứ X không nằm trong nhóm các từ bắt đầu bằng c (vì có cnt từ bắt đầu bằng c). Do đó, ta trừ X đi cnt và chuyển sang ký tự候选 tiếp theo.
     • Nếu X <= cnt, điều này có nghĩa từ thứ X nằm trong nhóm bắt đầu bằng c. Ta chọn c cho vị trí này, cập nhật xâu s và dừng duyệt các ký tự候选 cho vị trí này.
4. Kết quả: In ra xâu s đã được khôi phục.

Ví dụ: X = 7, K = 4.

• Vị trí 1 (danh sách defg): cnt = power[1] = 4^1 = 4. 7 > 4. X mới = 7 - 4 = 3. Bỏ qua d.
• Vị trí 1 (tiếp tục): cnt = 4. 3 <= 4. Chọn e. Dừng.
• Vị trí 2 (danh sách abcd): cnt = power[2] = 1. 3 > 1. X mới = 3 - 1 = 2. Bỏ qua a.
• Vị trí 2 (tiếp tục): cnt = 1. 2 > 1. X mới = 2 - 1 = 1. Bỏ qua b.
• Vị trí 2 (tiếp tục): cnt = 1. 1 <= 1. Chọn c. Dừng.
• Kết quả: e tại vị trí 1, c tại vị trí 2 -> freecontest.

Cách Chuyển đổi số học (Base-K)

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

int main()
{
    int n, m, k, x;
    string s;
    vector<string>a;
    cin>>n>>m>>k>>x;
    cin.ignore();
    cin>>s;

    string t;
    for(int i = 0; i < m; i++)
    {
        cin>>t;
        sort(t.begin(), t.end());
        a.push_back(t);
    }

    vector<char> ans;
    // Tính từ cuối về đầu (phù hợp với quy tắc so sánh từ điển)
    for (int i = m - 1; i >= 0; i--) {
        int idx = (x - 1) % k; // Lấy số dư để xác định ký tự
        ans.push_back(a[i][idx]);
        x = (x - 1) / k + 1; // Chia nguyên cho k (giảm x về index của phần tử trước)
    }
    int l = ans.size() - 1;
    for (char c : s) {
        if (c != '#')
            cout << c;
        else
            cout << ans[l--]; // In ra từ vị trí mờ đầu tiên đến cuối
    }
    return 0;
}

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

Phương pháp này coi bài toán như bài toán chuyển đổi một số từ hệ đếm cơ số 10 sang hệ cơ số K.

1. Đặc tính: Vì có M vị trí mờ, mỗi vị trí có K lựa chọn, tổng số cách là K^M. Các từ được sắp xếp tăng dần, tương ứng với việc duyệt tuần tự các số từ 0 đến K^M - 1 trong hệ cơ số K (với các chữ số là các ký tự候选).
2. Tính toán: Ta cần tìm từ thứ X.
   • Ký tự cuối cùng (vị trí mờ cuối cùng trong xâu) thay đổi nhanh nhất, tương ứng với số hạng K^0.
   • Ký tự đầu tiên (vị trí mờ đầu tiên) thay đổi chậm nhất, tương ứng với số hạng K^{M-1}.
   • Để tìm các ký tự, ta thực hiện chia lấy dư:
     • idx = (X - 1) % k: Xác định ký tự cho vị trí mờ cuối cùng (vì X là 1-based).
     • x = (X - 1) / k + 1: Cập nhật X để tìm ký tự cho vị trí tiếp theo (vị trí mờ trước đó).
3. Thứ tự xử lý: Do cách tính này xác định ký tự từ vị trí cuối cùng lên vị trí đầu tiên, ta lưu các ký tự vào một mảng ans (hoặc stack) rồi in ra theo thứ tự xuất hiện trong xâu.
4. Tại sao +1 trong x = (x - 1) / k + 1?:
   • Ví dụ: K=4, X=7.
   • X-1 = 6.
   • idx = 6 % 4 = 2 (ký tự thứ 3).
   • x = 6 / 4 + 1 = 1 + 1 = 2.
   • Vòng lặp tiếp theo với X=2: idx = 1 % 4 = 1. x = 1 / 4 + 1 = 0 + 1 = 1.
   • Vòng lặp tiếp theo với X=1: idx = 0 % 4 = 0. x = 0 / 4 + 1 = 1. (Nếu x vẫn >0 và i >= 0).
   • Logic này đúng với việc quay lui từ cuối lên đầu.

Ví dụ: X=7, M=2, K=4.

• i=1 (cuối): idx = (7-1)%4 = 2. ans = [char[2]]. x = (6)/4 + 1 = 2.
• i=0 (đầu): idx = (2-1)%4 = 1. ans = [char[2], char[1]]. x = (1)/4 + 1 = 1.
• ans chứa ký tự cuối rồi ký tự đầu. Khi in, ta duyệt s và dùng l từ size-1 về 0.
• s: fr#e#ontest -> freecontest.

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

Bài học kinh nghiệm

• Bài toán có thể xử lý như một hệ đếm cơ số K, trong đó mỗi vị trí mờ là một chữ số.
• Thứ tự xuất hiện của các từ trong danh sách tương ứng với thứ tự tăng dần của các số nguyên khi coi các lựa chọn là các chữ số của hệ cơ số K.
• Cần phân biệt giữa Index (0-based) và Rank (1-based). Xử lý X-1 để chuyển về 0-based giúp việc tính toán đơn giản hơn.

Lỗi thường gặp

• Tràn số (Overflow): Nếu M lớn và K lớn, K^M có thể vượt quá giới hạn của long long. Cần xử lý bằng cách giới hạn giá trị tính toán ở một ngưỡng an toàn (ví dụ 10^9 + 7) vì X chỉ tối đa 10^9.
• Thứ tự xử lý: Nếu dùng phương pháp chia lấy dư, ta nhận được ký tự từ cuối lên đầu. Cần lưu lại thứ tự này trước khi in để đảm bảo thứ tự đúng trong xâu.
• Lỗi truy cập mảng: Cần đảm bảo thứ tự các gợi ý trong input tương ứng với thứ tự các ký tự '#' trong xâu từ trái sang phải.