Mô tả bài toán

Cho một chuỗi ký tự số có độ dài n, chỉ bao gồm các chữ số từ 0 đến 9. Chuỗi này có thể được xem như một số thập phân có n chữ số. Nhiệm vụ là chọn ra một chuỗi con liên tục và đảo ngược nó (thực hiện tối đa một lần). Sau khi đảo ngược và đặt lại vào vị trí cũ, ta thu được một số mới. Yêu cầu đặt ra là đếm số lượng cách chọn chuỗi con sao cho số mới tạo thành nghiêm ngặt nhỏ hơn số ban đầu. Hai cách chọn được coi là khác nhau nếu vị trí của chuỗi con trong chuỗi gốc là khác nhau. Lưu ý rằng số mới có thể chứa số 0 ở đầu (leading zeros), và điều này hoàn toàn hợp lệ.

Định dạng đầu vào và đầu ra

Đầu vào: Một dòng duy nhất chứa chuỗi số có độ dài n. Các ràng buộc về độ dài như sau:

• 20% số test có 1 ≤ n ≤ 100.
• 40% số test có 1 ≤ n ≤ 1000.
• 100% số test có 1 ≤ n ≤ 5000.

Đầu ra: Một số nguyên duy nhất là tổng số cách chọn chuỗi con thỏa mãn điều kiện.

Ví dụ minh họa

Đầu vào:

210102

Đầu ra:

8

Giải thích: Có 8 cách chọn chuỗi con để đảo ngược tạo ra số nhỏ hơn:

• Đảo đoạn từ chỉ số 0 đến 1: 120102 < 210102
• Đảo đoạn từ chỉ số 0 đến 2: 012102 < 210102
• Đảo đoạn từ chỉ số 0 đến 3: 101202 < 210102
• Đảo đoạn từ chỉ số 0 đến 4: 010122 < 210102
• Đảo đoạn từ chỉ số 0 đến 5: 201012 < 210102
• Đảo đoạn từ chỉ số 1 đến 2: 201102 < 210102
• Đảo đoạn từ chỉ số 1 đến 4: 201012 < 210102
• Đảo đoạn từ chỉ số 3 đến 4: 210012 < 210102

Phân tích thuật toán

Để giải quyết bài toán này một cách hiệu quả, ta có thể sử dụng kỹ thuật mở rộng từ tâm (center expansion). Thay vì duyệt qua tất cả các cặp điểm đầu và điểm cuối của chuỗi con rồi so sánh từng ký tự (độ phức tạp $O(n^3)$), ta sẽ cố định tâm của chuỗi con và mở rộng dần ra hai bên.

Khi mở rộng từ tâm ra ngoài, cặp ký tự đầu tiên không đối xứng (khác nhau) sẽ quyết định việc đảo ngược chuỗi con có làm cho số nhỏ đi hay không. Cụ thể:

• Nếu ký tự bên trái lớn hơn ký tự bên phải (num_str[left] > num_str[right]), khi đảo ngược, ký tự nhỏ hơn sẽ được đưa lên hàng có trọng số cao hơn (bên trái), làm cho toàn bộ số nhỏ đi.
• Ngược lại, nếu num_str[left] < num_str[right], việc đảo ngược sẽ làm số lớn hơn.
• Nếu hai ký tự bằng nhau, ta tiếp tục mở rộng ra lớp ngoài vì kết quả phụ thuộc vào các cặp ký tự tiếp theo.

Bằng cách duy trì một biến trạng thái boolean trong quá trình mở rộng, ta có thể đếm số lượng chuỗi con hợp lệ với độ phức tạp thời gian là $O(n^2)$, hoàn toàn đáp ứng được giới hạn $n \le 5000$.

Mã nguồn tham khảo (C++)

Dưới đây là cách triển khai tối ưu sử dụng cấu trúc rõ ràng hơn, xử lý cả chuỗi con độ dài chẵn và lẻ trong cùng một luồng logic, đồng thời sử dụng kiểu dữ liệu long long để tránh tràn số khi kết quả lớn.

#include <iostream>
#include <string>

using namespace std;

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

    string num_str;
    if (!(cin >> num_str)) return 0;

    int n = num_str.size();
    long long total_ways = 0;

    for (int center = 0; center < n; ++center) {
        bool makes_smaller = false;
        
        for (int left = center - 1, right = center + 1; left >= 0 && right < n; --left, ++right) {
            if (num_str[left] > num_str[right]) makes_smaller = true;
            else if (num_str[left] < num_str[right]) makes_smaller = false;
            if (makes_smaller) total_ways++;
        }

        makes_smaller = false;
        for (int left = center, right = center + 1; left >= 0 && right < n; --left, ++right) {
            if (num_str[left] > num_str[right]) makes_smaller = true;
            else if (num_str[left] < num_str[right]) makes_smaller = false;
            if (makes_smaller) total_ways++;
        }
    }

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