Editorial for ptit020: Đánh thức rồng vàng

Hiểu bài toán

Bài toán yêu cầu tìm ký tự thứ $k$ trong một xâu được tạo ra bằng cách lặp lại vô hạn quá trình biến đổi xâu $s$. Quá trình biến đổi như sau: từ xâu $s$ hiện tại, ta tạo một xâu mới $s'$ bằng cách lấy ký tự cuối cùng của $s$ đưa lên đầu, rồi ghép $s'$ vào cuối $s$. Ví dụ: $RYUU \to RYUUURYU \to RYUUURYUURYUUURY$. Xâu cuối cùng là vô hạn. Ta cần tìm ký tự tại vị trí $k$ (1-indexed, $k$ lên tới $10^{18}$) trong xâu này.

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

Cách Giả lập đệ quy quy hoạch động (Recursive Mapping)

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

ll get(ll N, int lv){
    if(N > k){
        if(k <= N/2) return k;
        else{
            ll pos = k - N/2 - 1;
            if(pos == 0) pos = N/2;
            return pos;
        }
    }
    ll curPos = get(N*2, lv + 1);
    if(lv == 0) return curPos;
    if(curPos > N/2){
        curPos = curPos - N/2 - 1;
        if(curPos == 0) curPos = N/2;
    }
    return curPos;
}

void solve(){
    cin >> k;
    cin >> s;
    ll pos = get(s.size(), 0);
    cout << s[pos - 1];
}

• Time Complexity: O(log k)
• Space Complexity: O(log k) (do đệ quy)

Approach này sử dụng một hàm đệ quy get(N, lv) để ánh xạ vị trí $k$ từ một cấp độ$xâu$ lớn hơn về cấp độ nhỏ hơn. Logic bên trong hàm xử lý việc chia đôi độ dài $N$ và điều chỉnh $k$ dựa trên quy tắc sinh xâu. Cấp độ lv giúp phân biệt việc có cần hiệu chỉnh giá trị trả về hay không. Đây là cách tiếp cận trực tiếp từ quy luật toán học của bài toán.

Cách Thực thi đệ quy quy hoạch động (Iterative)

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

int main() {
    ll k;
    string s;
    cin >> k >> s;

    ll dd = (ll)s.length();
    while (dd < k) dd *= 2;

    while (dd > (ll)s.length()) {
        ll half = dd / 2;
        if (k == half + 1) k = half;
        else if (k > half + 1) k -= (half + 1);
        dd /= 2;
    }

    cout << s[k - 1];
    return 0;
}

• Time Complexity: O(log k)
• Space Complexity: O(1)

Đây là phiên bản không đệ quy của approach 1. Thay vì gọi hàm đệ quy, ta tính toán độ dài cần thiết của xâu (lớn hơn hoặc bằng $k$) bằng cách nhân đôi độ dài ban đầu. Sau đó, ta lặp lại quá trình chia đôi độ dài và điều chỉnh $k$ cho đến khi $k$ nằm trong phạm vi độ dài ban đầu của xâu $s$. Logic xử lý $k$ dựa trên các quy tắc: nếu $k$ nằm ở phần 'đầu' của xâu cha (trước phần được thêm vào), ta giữ nguyên; nếu nằm ở phần mới, ta thực hiện hiệu chỉnh vị trí tương ứng.

Cách Tìm quy luật (Pattern Analysis)

// Tương tự Approach 2, nhưng giải thích theo góc nhìn quy luật
// Ví dụ logic:
// Xâu tại bước i có độ dài L_i. Xâu tại bước i+1 có độ dài 2*L_i + 1.
// Cấu trúc: S_{i+1} = S_i + C + S_i, với C là ký tự cuối của S_i.
// Ký tự thứ k trong S_{i+1}:
// - Nếu k <= L_i: tương ứng với ký tự thứ k trong S_i.
// - Nếu k == L_i + 1: là ký tự C.
// - Nếu k > L_i + 1: tương ứng với ký tự thứ (k - L_i - 1) trong S_i.

• Time Complexity: O(log k)
• Space Complexity: O(1)

Phân tích cấu trúc sinh xâu cho thấy xâu mới được tạo thành từ 2 bản sao của xâu cũ và một ký tự ở giữa. Điều này cho phép ta giảm quy mô bài toán: nếu $k$ nằm ở nửa sau của xâu hiện tại, ta có thể quy về xâu cũ với $k$ mới. Cụ thể, nếu $k > L{old} + 1$, ta trừ đi $L{old} + 1$ để về vị trí tương ứng trong nửa đầu. Nếu $k = L_{old} + 1$, đó là ký tự ở giữa. Quá trình này lặp lại cho đến khi $k$ nhỏ hơn độ dài ban đầu của $s$. Đây là cách diễn đạt trực quan nhất của thuật toán.

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

Bài học kinh nghiệm

• Cấu trúc xâu có tính đệ quy rõ ràng: $S{new} = S{old} + C + S_{old}$ (hoặc biến thể tương tự về logic). Điều này cho phép giảm quy mô bài toán từ $O(k)$ xuống $O(\log k)$.
• Do $k$ lên tới $10^{18}$, ta không thể xây dựng xâu hoặc mô phỏng từng bước. Cần tìm công thức toán học để ánh xạ vị trí $k$ về vị trí tương đối trong xâu ban đầu.
• Xử lý số lớn: Luôn sử dụng long long (hoặc unsigned long long) cho biến $k$ và độ dài xâu.

Lỗi thường gặp

• Sử dụng kiểu số nguyên 32-bit (int)导致 overflow khi $k$ hoặc độ dài xâu vượt quá $2 \times 10^9$.
• Lỗi off-by-one (sai số 1 đơn vị): Cẩn thận với các phép chia đôi và cộng trừ khi tính toán vị trí mới, đặc biệt khi $k$ chia hết cho 2 hoặc nằm ở biên.
• Quên trường hợp đặc biệt khi $k$ nằm chính xác ở vị trí trung tâm (ký tự được thêm vào giữa các bước lặp).