Hiểu bài toán

Bài toán yêu cầu mô phỏng quá trình lật một mảng số nguyên $A = [1, 2, \dots, n]$ dựa trên $k$ bước lặp lại của hai thao tác: lật đoạn $[u, v]$ và lật đoạn $[l, r]$ (thứ tự lật được xác định bởi input). Tuy nhiên, nếu $k$ quá lớn, việc mô phỏng trực tiếp là bất khả thi. May mắn thay, do hai thao tác lật này được lặp đi lặp lại theo chu kỳ, mảng sẽ trở về trạng thái ban đầu sau một số bước $T$ (chu kỳ). Do đó, bài toán có thể giảm tải bằng cách tính $k = k \pmod T$ và chỉ mô phỏng $k$ bước còn lại.

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

Cách Mô phỏng trực tiếp

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

void rv(vector<ll>& a, ll l, ll r) {
    while (l < r) {
        swap(a[l], a[r]);
        l++; r--;
    }
}

int main() {
    // Đọc input
    vector<ll> a(n+1);
    for(ll i=1; i<=n; i++) a[i] = i;

    // Thực hiện k bước
    while(k--) {
        rv(a, u, v);
        rv(a, l, r);
    }

    // In kết quả
}

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

Đây là cách tiếp cận trực quan nhất. Khởi tạo mảng $A$ với $A[i] = i$. Với mỗi bước, ta thực hiện lật đoạn $[u, v]$ bằng cách hoán đổi các phần tử đối xứng, sau đó làm tương tự với đoạn $[l, r]$. Cách này hoạt động tốt nếu $k$ nhỏ, nhưng sẽ bị Time Limit Exceeded nếu $k$ lớn (ví dụ $10^9$).

Cách Tìm chu kỳ (Cycle Detection)

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

// Hàm lật đoạn
void rv(vector<ll>& a, ll l, ll r) { ... }

// Kiểm tra mảng đã sắp xếp chưa
bool isSorted(vector<ll>& a) { ... }

int main() {
    // Doc input
    vector<ll> a(n+1);
    for(ll i=1; i<=n; i++) a[i] = i;

    vector<vector<ll>> history;
    int cycle_len = 0;

    // Tìm chu kỳ
    while(true) {
        rv(a, u, v);
        rv(a, l, r);
        cycle_len++;

        // Kiểm tra xem mảng có về trạng thái ban đầu không
        if (isSorted(a)) break;

        // Hoặc kiểm tra trạng thái đã xuất hiện trước đó (nếu không về đúng 1..n)
    }

    // Giảm k
    k %= cycle_len;

    // Mô phỏng lại k bước
    // ... (tái khởi tạo mảng và mô phỏng k bước)
}

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

Giả sử quá trình lặp lại $u \to v \to l \to r$ là một hàm số $f(x)$. Sau một số lần $T$, mảng sẽ quay về trạng thái ban đầu $f^T(x) = x$. Ta chỉ cần mô phỏng để tìm $T$, sau đó tính $k \leftarrow k \pmod T$. Cuối cùng, ta chỉ cần mô phỏng $k$ bước thay vì $k$ ban đầu. Trong các giải pháp được cung cấp, việc kiểm tra isSorted hoặc check() chỉ là một cách tối ưu hóa nhỏ để dừng sớm nếu may mắn, nhưng về cơ bản ta cần theo dõi trạng thái để tìm chu kỳ chính xác.

Cách Giả lập theo chu kỳ (Optimized Simulation)

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

int main() {
    // Đọc input
    int n, k, l, r, u, v;
    cin >> n >> k >> l >> r >> u >> v;

    int a[1000005]; // Kích thước足够 lớn
    for(int i = 1; i <= n; i++) a[i] = i;

    // Tìm chu kỳ
    int T = 0;
    bool first_state = true;
    do {
        if (T % 2 == 0) {
            // Lật đoạn l, r
            reverse(a + l, a + r + 1);
        } else {
            // Lập đoạn u, v
            reverse(a + u, a + v + 1);
        }
        T++;
        // Kiểm tra điều kiện dừng: trở lại trạng thái ban đầu
    } while (!is_sorted(a+1, a+n+1)); // Hoặc so sánh với mảng ban đầu

    // Giảm k
    k %= T;

    // Reset và chạy lại
    for(int i = 1; i <= n; i++) a[i] = i;
    for(int i = 0; i < k; i++) {
        if (i % 2 == 0) reverse(a + l, a + r + 1);
        else reverse(a + u, a + v + 1);
    }

    // In kết quả
}

• Time Complexity: O(n + T * n)
• Space Complexity: O(n)

Đây là cách tiếp cận tối ưu hóa từ mô phỏng trực tiếp. Thay vì dùng hàm hoán đổi thủ công, ta dùng hàm reverse của C++. Quan trọng nhất, ta chia bài toán làm 2 giai đoạn: 1) Chạy vòng lặp cho đến khi mảng trở về trạng thái ban đầu để tìm chu kỳ $T$. 2) Tính $k = k \pmod T$. 3) Reset mảng và chỉ chạy $k$ bước. Điều này giảm độ phức tạp từ $O(k \cdot n)$ xuống $O(T \cdot n)$, trong đó $T$ là chu kỳ (thường nhỏ hơn $k$ rất nhiều).

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

Bài học kinh nghiệm

• Bài toán có tính lặp lại (periodic). Sau một số bước $T$, mảng sẽ trở về trạng thái ban đầu.
• Giảm $k$ bằng cách lấy modulo với chu kỳ $T$ ($k = k \pmod T$) là chìa khóa để giải quyết các test case có $k$ lớn.
• Thứ tự lật quan trọng: rv(u, v) rồi rv(l, r) hay ngược lại phụ thuộc vào input. Trong code mẫu, u, v thường là đoạn lật đầu tiên, l, r là đoạn lật thứ hai.

Lỗi thường gặp

• Sử dụng long long cho biến chỉ số và $k$ để tránh tràn số nguyên (overflow).
• Lỗi logic trong hàm lật: Đảm bảo chỉ số l và r được xử lý chính xác (ví dụ l+r có thể chẵn hoặc lẻ).
• Khởi tạo lại mảng trước khi mô phỏng $k$ bước cuối cùng sau khi đã tìm được chu kỳ.
• Xác định sai chu kỳ: Đôi khi mảng không quay về $1, 2, ..., n$ nhưng vẫn lặp lại trạng thái $S$ nào đó. Ta cần lưu lịch sử trạng thái hoặc chỉ cần chạy đủ $k$ bước sau khi giảm $k$.