Hiểu bài toán

Bài toán yêu cầu xoay một mảng gồm n số nguyên sang phải k lần. Sau đó, có q truy vấn, mỗi truy vấn hỏi giá trị tại vị trí m trong mảng sau khi xoay. Với ràng buộc n, k lên đến 10^5, ta cần một giải pháp hiệu quả để xử lý số lần xoay lớn và nhiều truy vấn.

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

Cách Mô phỏng xoay (Brute Force)

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

int main() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Mô phỏng k lần xoay
    for (int i = 0; i < k; i++) {
        int last = a[n-1];
        for (int j = n-1; j > 0; j--) {
            a[j] = a[j-1];
        }
        a[0] = last;
    }

    while (q--) {
        int m;
        cin >> m;
        cout << a[m] << '\n';
    }
    return 0;
}

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

Giải pháp này mô phỏng chính xác quá trình xoay. Với mỗi lần xoay, ta dịch chuyển toàn bộ mảng sang phải (O(n)). Tổng thời gian là O(k*n). Với n=10^5 và k=10^5, thời gian thực thi khoảng 10^10 thao tác, quá chậm và chắc chắn bị TLE. Cách này chỉ mang tính tham khảo để hiểu bài toán.

Cách Tạo mảng kết quả (Simulate Rotation by Building New Array)

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

int main() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    k %= n; // Xử lý trường hợp k >= n

    // Xây dựng mảng mới sau khi xoay
    vector<int> res(n);
    int idx = 0;
    // Sao chép phần tử từ index (n - k) đến (n - 1) lên đầu
    for (int i = n - k; i < n; i++) {
        res[idx++] = a[i];
    }
    // Sao chép phần tử từ index 0 đến (n - k - 1)
    for (int i = 0; i < n - k; i++) {
        res[idx++] = a[i];
    }

    while (q--) {
        int m;
        cin >> m;
        cout << res[m] << '\n';
    }
    return 0;
}

• Time Complexity: O(n + q)
• Space Complexity: O(n)

Thay vì mô phỏng từng bước, ta tính toán vị trí mới của các phần tử sau k lần xoay. Nếu xoay phải k lần, phần tử tại vị trí i ban đầu sẽ chuyển đến vị trí (i + k) % n. Do đó, phần tử tại vị trí j trong mảng mới chính là phần tử tại vị trí (j - k + n) % n trong mảng cũ. Hoặc ta có thể xây dựng lại mảng theo thứ tự: các phần tử cuối của mảng cũ (từ n-k đến n-1) sẽ lên đầu mảng mới, rồi đến các phần tử đầu của mảng cũ. Giải pháp này chạy trong O(n) để xây dựng mảng và O(1) cho mỗi truy vấn. Rất nhanh và dễ hiểu.

Cách Tính toán trực tiếp qua công thức (Mathematical Index Mapping)

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

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

    long long n, k, q;
    cin >> n >> k >> q;

    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    k %= n; // Bắt buộc phải giảm k về dưới n

    while (q--) {
        long long x;
        cin >> x;
        // Công thức tính index trong mảng gốc
        long long idx = (x - k + n) % n;
        cout << a[idx] << "\n";
    }

    return 0;
}

• Time Complexity: O(q) (hoặc O(n + q) nếu tính thời gian đọc input)
• Space Complexity: O(n)

Đây là cách tối ưu nhất về mặt phức tạp tính toán và bộ nhớ động (không cần mảng phụ). Ta nhận thấy rằng sau k lần xoay phải, giá trị tại vị trí m trong mảng mới tương đương với giá trị tại vị trí (m - k) % n (mang dấu âm) trong mảng cũ. Để tránh số âm, ta cộng thêm n: idx = (m - k + n) % n. Ta phải thực hiện k %= n trước để tránh tràn số và đảm bảo công thức đúng. Với mỗi truy vấn, ta chỉ cần O(1) thời gian.

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

Bài học kinh nghiệm

• Xoay phải k lần tương đương với việc phần tử tại vị trí i ban đầu sẽ nằm ở vị trí (i + k) % n. Do đó, để tìm phần tử tại vị trí m sau khi xoay, ta cần tìm phần tử tại vị trí (m - k + n) % n trong mảng ban đầu.
• Luôn thực hiện phép chia lấy dư cho số lần xoay (k %= n) trước khi xử lý. Điều này giúp giảm k về khoảng [0, n-1], tránh lặp lại chu kỳ xoay và phòng tránh tràn số khi tính toán.
• Vì số lượng truy vấn q khá nhỏ (≤ 500) nhưng n và k lớn, việc xây dựng lại toàn bộ mảng (O(n)) hay dùng công thức (O(1)/truy vấn) đều hiệu quả. Tuy nhiên, dùng công thức trực tiếp là tối ưu nhất về thời gian và bộ nhớ.

Lỗi thường gặp

• Quên giảm k modulo n (k %= n) dẫn đến lỗi logic hoặc tràn số khi tính chỉ số mảng.
• Sử dụng thuật toán mô phỏng O(k*n) sẽ gây quá thời gian (Time Limit Exceeded) do k và n có thể lên tới 10^5.
• Lỗi truy cập mảng out of bounds khi tính chỉ số mới nếu không xử lý số âm cẩn thận (ví dụ: (m - k) % n có thể ra số âm ở một số ngôn ngữ). Nên dùng (m - k + n) % n.