Editorial for ptit037: Gameshow "Ai là triệu phú"

Hiểu bài toán

Một người chơi muốn tìm một từ số (ZERO, ONE, ..., NINE) có thể được tạo thành bằng cách chọn các ký tự từ xâu S cho trước (theo đúng thứ tự xuất hiện trong S, không nhất thiết liên tiếp nhưng không được đảo vị trí). Nếu có nhiều từ số thỏa mãn, chọn từ có giá trị số học nhỏ nhất. Nếu không có từ số nào thỏa mãn, in ra thông báo buồn bã.

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

Cách Thăm dò theo thứ tự từ nhỏ đến lớn (Greedy Validation)

#include <stdio.h>
#include <string.h>

char *words[] = {
    "ZERO", "ONE", "TWO", "THREE", "FOUR",
    "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"
};

// Kiểm tra xem word có phải là subsequence của s không
int is_subsequence(const char *s, const char *word) {
    int i = 0, j = 0;
    while (s[i] && word[j]) {
        if (s[i] == word[j]) j++;
        i++;
    }
    return word[j] == '\0';
}

int main() {
    char s[1005];
    scanf("%s", s);

    // Duyệt tuần tự từ 0 đến 9, gặp cái đầu tiên thỏa mãn là dừng
    for (int i = 0; i < 10; i++) {
        if (is_subsequence(s, words[i])) {
            printf("%s\\n", words[i]);
            return 0;
        }
    }

    printf("CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!\\n");
    return 0;
}

• Time Complexity: O(N * M) (với N là độ dài S, M là độ dài từ số, M tối đa là 5)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Ta duyệt qua danh sách các từ số từ nhỏ đến lớn (0 đến 9). Với mỗi từ, ta kiểm tra xem nó có phải là một subsequence của S hay không (tức là các ký tự của từ có xuất hiện trong S theo đúng thứ tự hay không). Hàm is_subsequence dùng hai con trỏ để duyệt qua S và từ số, nếu tìm thấy ký tự khớp thì tiến con trỏ từ số. Nếu duyệt hết S mà chưa khớp hết từ số thì từ đó không thỏa mãn. Vì ta duyệt theo thứ tự tăng dần, từ đầu tiên tìm được chắc chắn là số nhỏ nhất.

Cách Quay lui (Backtracking)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string words[] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
string S;
string result = "";

bool isSubsequence(const string& sub, const string& main) {
    int j = 0;
    for (int i = 0; i < main.length() && j < sub.length(); i++) {
        if (main[i] == sub[j]) j++;
    }
    return j == sub.length();
}

void solve() {
    cin >> S;
    for (int i = 0; i < 10; i++) {
        if (isSubsequence(words[i], S)) {
            cout << words[i] << endl;
            return;
        }
    }
    cout << "CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!" << endl;
}

int main() {
    solve();
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Cách này về bản chất logic giống với cách 1 (Thăm dò). Nó cũng kiểm tra từng từ số một. Trong bối cảnh bài toán này, quay lui thường được dùng khi cần tạo ra các xâu con phức hợp, nhưng ở đây chỉ cần kiểm tra tính tồn tại của subsequence. Giải pháp dùng vòng lặp lồng nhau (thăm dò) là hiệu quả và dễ hiểu nhất.

Cách Duyệt ký tự và đánh dấu (Greedy Character Matching)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    char s[1001];
    scanf("%s", s);

    // Mảng lưu trạng thái tiến độ khớp của từng từ
    // progress[i] là chỉ số ký tự đang chờ khớp của từ thứ i
    int progress[10] = {0};
    char* words[] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
    int len[] = {4, 3, 3, 5, 4, 4, 3, 5, 5, 4};
    int completed[10] = {0}; // Đánh dấu từ nào đã khớp xong
    int n = strlen(s);

    for (int i = 0; i < n; i++) {
        char c = s[i];
        // Kiểm tra tất cả các từ尚未 hoàn thành
        for (int w = 0; w < 10; w++) {
            if (!completed[w] && progress[w] < len[w] && words[w][progress[w]] == c) {
                progress[w]++;
                if (progress[w] == len[w]) {
                    completed[w] = 1;
                }
            }
        }
    }

    // Tìm từ hoàn thành đầu tiên (từ nhỏ nhất)
    for (int i = 0; i < 10; i++) {
        if (completed[i]) {
            printf("%s\\n", words[i]);
            return 0;
        }
    }

    printf("CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!\\n");
    return 0;
}

• Time Complexity: O(N * M) (N là độ dài S, M là số lượng từ số)
• Space Complexity: O(1)

Cách này duyệt qua xâu S một lần duy nhất. Với mỗi ký tự trong S, nó thử 'nuốt' ký tự đó cho tất cả các từ số đang được theo dõi. Nếu một từ số được 'nuốt' hết các ký tự (đạt độ dài đầy đủ), nó được đánh dấu là hoàn thành. Vì ta duyệt S theo thứ tự và kiểm tra các từ số theo thứ tự 0..9, từ nào hoàn thành sớm nhất sẽ là đáp án. Cách này khác với cách 1 ở chỗ nó không cần lặp lại duyệt S cho mỗi từ số, mà xử lý tất cả trong 1 lượt.

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

Bài học kinh nghiệm

• Bài toán yêu cầu tìm một subsequence (xâu con theo thứ tự) của S khớp với một trong các từ số.
• Do yêu cầu in ra số nhỏ nhất nếu có nhiều đáp án, ta nên ưu tiên kiểm tra các từ số có giá trị tăng dần (từ 0 đến 9).
• Một từ số được coi là khớp nếu tất cả các ký tự của nó xuất hiện trong S theo đúng trình tự.

Lỗi thường gặp

• Lầm tưởng rằng các ký tự phải liền nhau trong S. Thực tế chỉ cần xuất hiện theo đúng thứ tự.
• Việc kiểm tra subsequence cần phải đúng trình tự: ví dụ S="ONE" thì không khớp "ONE" nếu S="N-O-E" (vì thứ tự O-N-E không đúng trình tự O->N->E).