Hiểu bài toán

Bài toán yêu cầu đếm số lượng số đối xứng (palindrome) trong đoạn [l, r]. Một số được gọi là đối xứng nếu đọc từ trái sang phải hay từ phải sang trái đều giống nhau (ví dụ: 121, 1331). Dữ liệu đầu vào gồm nhiều bộ test, mỗi bộ gồm hai số l và r. Với mỗi bộ test, ta cần in ra số lượng số đối xứng trong đoạn [l, r].

Giới hạn: l, r có thể lên tới 10^15, nhưng độ dài đoạn [l, r] (tức là r - l) không quá 10^5. Số lượng dòng input không quá 1000.

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

Cách Brute Force

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

bool isPalindrome(long long n) {
    long long original = n;
    long long reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

int main() {
    long long l, r;
    while (scanf("%lld %lld", &l, &r) == 2) {
        int count = 0;
        for (long long i = l; i <= r; i++) {
            if (isPalindrome(i)) {
                count++;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

• Time Complexity: O((r - l) * log10(r))
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Với mỗi số i trong khoảng [l, r], ta kiểm tra xem nó có phải là số đối xứng hay không. Hàm isPalindrome hoạt động bằng cách đảo ngược các chữ số của số n và so sánh với số gốc.

• Độ phức tạp thời gian: Với mỗi số, việc đảo ngược số mất O(log10(n)) thao tác (tương đương số lượng chữ số). Tổng thời gian cho một truy vấn là O((r - l) * log10(r)). Với r-l <= 10^5 và log10(r) <= 16, số phép toán khoảng 1.6 triệu, hoàn toàn chấp nhận được trong thời gian chạy.
• Độ phức tạp không gian: Chỉ cần một vài biến lưu trữ, O(1).

Cách Brute Force (Digit Array)

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

bool check(long long n) {
    int dp[20];
    int i = 0;
    while (n > 0) {
        dp[i] = n % 10;
        i++;
        n /= 10;
    }
    i--; // Chỉnh chỉ số về phần tử cuối cùng
    for (int j = 0; j <= i / 2; j++) {
        if (dp[j] != dp[i - j]) return false;
    }
    return true;
}

int main() {
    long long m, n;
    while (scanf("%lld %lld", &m, &n) == 2) {
        int count = 0;
        for (long long u = m; u <= n; u++) {
            if (check(u)) count++;
        }
        printf("%d\n", count);
    }
    return 0;
}

• Time Complexity: O((r - l) * log10(r))
• Space Complexity: O(log10(r))

Cách này cũng lặp qua từng số trong khoảng [l, r] nhưng cách kiểm tra khác. Thay vì tạo ra số đảo ngược, nó lưu các chữ số vào mảng, sau đó dùng hai con trỏ (hoặc chỉ số) đầu và cuối để so sánh các cặp đối xứng.

• Phương pháp này về mặt lý thuyết có thể nhanh hơn một chút so với việc nhân chênh lệch lớn (tràn số tiềm năng, dù trong bài này long long đủ dùng) nhưng về tổng thể độ phức tạp vẫn giống phương pháp 1.
• Lưu ý: Mảng dp có cố định kích thước 20, đủ cho số có tối đa 19 chữ số (vì 10^15 có 16 chữ số).

Cách Tổng quát (Sinh số đối xứng)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

vector<long long> pals;

// Sinh số đối xứng có số chữ số lẻ (ví dụ: 121)
void gen_odd(int len, long long val) {
    if (len == 0) {
        pals.push_back(val);
        return;
    }
    long long next_val;
    for (int i = 0; i <= 9; i++) {
        if (val == 0 && i == 0) continue; // Không dẫn đầu bằng 0
        next_val = val * 10 + i;
        gen_odd(len - 1, next_val);
    }
}

// Sinh số đối xứng có số chữ số chẵn (ví dụ: 1221)
void gen_even(int len, long long val) {
    if (len == 0) {
        pals.push_back(val);
        return;
    }
    long long next_val;
    for (int i = 0; i <= 9; i++) {
        if (val == 0 && i == 0) continue;
        next_val = val * 10 + i;
        gen_even(len - 1, next_val);
    }
}

void precompute() {
    pals.push_back(0);
    // 1 chữ số
    for (int i = 1; i <= 9; i++) pals.push_back(i);

    // >= 2 chữ số: lặp từ 1-9 cho trung tâm
    // Số chữ số tối đa: 16
    // Gen số có odd len (bằng cách build half và mirror)
    // Hoặc đơn giản là dùng recursion gen như code mẫu (chỉ là minh họa logic)
    // Thực tế ta dùng loop sinh ra tất cả số đối xứng <= 10^15
    // Cách này thực thi phức tạp, nên giải pháp Brute Force là tối ưu nhất cho ràng buộc r-l <= 10^5.
    // Dưới đây là code minh họa cho việc sinh số đối xứng (Recursive), nhưng không được dùng trong submission do độ phức tạp sinh số cao.
    // Thay vào đó, ta nhận thấy giải pháp Brute Force là tốt nhất.
}

int main() {
    // Không cần gen trước, Brute Force là tối ưu
    return 0;
}
// *Lưu ý: Code này chỉ để minh họa ý tưởng 'Generate and Count',
// nhưng Brute Force才是 optimal solution cho ràng buộc r-l <= 10^5.*

• Time Complexity: O((r - l) * log10(r))
• Space Complexity: O(1)

Một cách tiếp cận khác (thường dùng khi r-l rất lớn, ví dụ 10^18) là sinh ra tất cả các số đối xứng nhỏ hơn r và kiểm tra xem chúng có nằm trong [l, r] không. Tuy nhiên, với ràng buộc r-l <= 10^5, việc lặp trực tiếp từ l đến r là đơn giản và hiệu quả nhất.

Giải pháp Brute Force (dùng vòng lặp từ l đến r và kiểm tra từng số) là tối ưu nhất cho bài toán này vì:

1. Ràng buộc r-l nhỏ (<= 10^5).
2. Kiểm tra một số có phải là palindrome rất nhanh (O(log n)).
3. Tổng số phép toán chỉ khoảng 1.6 triệu, chạy trong 1 giây.

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

Bài học kinh nghiệm

• Ràng buộc quan trọng nhất là r - l <= 10^5. Điều này cho phép duyệt qua từng số trong đoạn [l, r] mà không lo TLE.
• Kiểm tra một số có phải là số đối xứng có độ phức tạp O(log n) (tương đương số lượng chữ số). Với log n <= 16, phép kiểm tra này rất nhanh.
• Phương pháp sinh số đối xứng (Generate Palindromes) thường được dùng khi r lớn hơn rất nhiều (ví dụ 10^18) nhưng r - l nhỏ, nhưng trong bài này nó không cần thiết và phức tạp hơn.

Lỗi thường gặp

• Dùng số nguyên 32-bit (int) để lưu trữ l và r trong khi chúng có thể lên tới 10^15. Phải dùng long long (hoặc int64_t).
• Quên xử lý input đa dòng (dùng while(scanf(...) != EOF)).
• Lỗi tràn số khi đảo ngược số: Với số lớn (ví dụ 10^15), số đảo ngược có thể lớn hơn 2^63-1? Thực tế số đối xứng lớn nhất 10^15 là 999...999 (15 chữ số) hoặc 100...001, đều nằm trong long long (tối đa ~9e18). Tuy nhiên, khi tạo số đảo ngược, nếu số đó không phải palindrome, số đảo ngược có thể bị tràn số nếu dùng phép nhân liên tiếp. Nhưng với long long và số <= 10^15, phép toán này an toàn.
• Lỗi logic khi tính số lượng: Ví dụ in ra r - l thay vì số lượng palindrome.