Editorial for palinz: Truy vấn xâu đối xứng

Hiểu bài toán

Cho một xâu S chỉ gồm các ký tự '0' và '1' với độ dài n ≤ 5000. Cần trả lời m truy vấn (m ≤ 5000), mỗi truy vấn hỏi xem đoạn con S[L...R] có phải là xâu đối xứng (đọc xuôi và đọc ngược giống nhau) hay không. Nếu có in 'YES', ngược lại in 'NO'.

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

Cách Brute Force

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

int main() {
    char s[5005];
    scanf("%s", s);
    int m;
    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        l--; r--; // Chuyển về chỉ số 0-based
        int is_palindrome = 1;
        while (l < r) {
            if (s[l] != s[r]) {
                is_palindrome = 0;
                break;
            }
            l++;
            r--;
        }
        printf("%s\n", is_palindrome ? "YES" : "NO");
    }
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(n)

Với mỗi truy vấn, ta dùng hai con trỏ một đầu từ L và một đầu từ R, duyệt vào giữa. Nếu gặp ký tự khác nhau, đoạn không đối xứng. Nếu duyệt hết mà không gặp lỗi, đoạn đối xứng. Độ phức tạp là O(m * n) trong trường hợp xấu nhất, nhưng với n, m ≤ 5000 thì tổng số thao tác khoảng 25 triệu, đủ để chạy trong thời gian giới hạn (thường là 1 giây).

Cách Precompute (Dynamic Programming)

#include <stdio.h>
#include <stdbool.h>

bool dp[5005][5005];
char s[5005];

int main() {
    scanf("%s", s);
    int n = 0;
    while (s[n]) n++;

    // dp[i][j] = true nếu s[i...j] đối xứng
    // Cơ sở: mọi xâu độ dài 1 đều đối xứng
    for (int i = 0; i < n; i++) dp[i][i] = true;

    // Xử lý xâu độ dài 2 trở lên
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2) dp[i][j] = true;
                else dp[i][j] = dp[i+1][j-1];
            } else {
                dp[i][j] = false;
            }
        }
    }

    int m;
    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%s\n", dp[l-1][r-1] ? "YES" : "NO");
    }
    return 0;
}

• Time Complexity: O(n^2 + m)
• Space Complexity: O(n^2)

Ta precompute trước tất cả các đoạn con đối xứng bằng bảng DP 2 chiều. dp[i][j] = true nếu s[i...j] đối xứng. Công thức truy hồi: dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]). Sau đó mỗi truy vấn trả lời O(1). Với n=5000, bảng DP có ~25 triệu phần tử, tốn khoảng 25MB bộ nhớ, vẫn nằm trong giới hạn cho phép của các kỳ thi.

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

Bài học kinh nghiệm

• Với ràng buộc n, m ≤ 5000, giải thuật O(m * n) (Brute Force) thường đủ tốt và dễ code.
• Giải thuật DP O(n^2 + m) đảm bảo thời gian chạy ổn định dù m lớn, nhưng tốn bộ nhớ hơn.

Lỗi thường gặp

• Quên chuyển chỉ số từ 1-based sang 0-based khi truy cập mảng.
• Xử lý sai độ dài xâu rỗng hoặc độ dài 1 (trong DP cần khởi tạo cơ sở đúng).
• Đọc input sai thứ tự do có thể có ký tự newline thừa, dùng scanf("%d") có thể bỏ qua.