Editorial for ptit060: Hoán vị vòng tròn

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 trái k lần. Sau khi xoay, phần tử tại vị trí i sẽ được thay thế bằng phần tử tại vị trí (i + k) % n của mảng ban đầu. Do đó, để in ra mảng kết quả, ta chỉ cần in ra các phần tử từ vị trí k đến n-1, rồi in tiếp các phần tử từ vị trí 0 đến k-1. Đây là thao tác đơn giản trên mảng.

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

Cách Xoay trực tiếp và In

#include <stdio.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int arr[1000005]; // Mảng đủ lớn để chứa dữ liệu

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

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

    // In các phần tử từ vị trí k đến n-1
    for (int i = k; i < n; i++) {
        printf("%d ", arr[i]);
    }

    // In các phần tử từ vị trí 0 đến k-1
    for (int i = 0; i < k; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

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

Phương pháp này đọc toàn bộ dữ liệu vào mảng. Sau đó, nó tính lại giá trị của k (k % n) để đảm bảo không truy cập ngoài biên. Cuối cùng, nó in ra các phần tử theo thứ tự mới: các phần tử sau vị trí k được in trước, và các phần tử trước vị trí k được in sau. Cách này không cần tạo mảng mới hay thực hiện các thao tác hoán vị rườm rà, chỉ cần in theo đúng thứ tự.

Cách Xoay mảng và In

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int *arr = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    k %= n;

    // Tạo một mảng tạm để lưu phần tử đầu
    int *temp = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        temp[i] = arr[i];
    }

    // Dịch trái mảng
    for (int i = k; i < n; i++) {
        arr[i - k] = arr[i];
    }

    // Đưa phần tử đầu vào cuối
    for (int i = 0; i < k; i++) {
        arr[n - k + i] = temp[i];
    }

    // In mảng đã xoay
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    free(temp);
    free(arr);
    return 0;
}

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

Phương pháp này thực sự thay đổi vị trí của các phần tử trong mảng. Nó lưu k phần tử đầu tiên vào một mảng tạm, dịch các phần tử còn lại sang trái (ghi đè lên vị trí ban đầu), và sau đó đưa các phần tử đã lưu vào cuối mảng. Cuối cùng in ra mảng. Cách này thực hiện đúng thao tác xoay vật lý nhưng cần thêm bộ nhớ cho mảng tạm và nhiều phép gán hơn.

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

Bài học kinh nghiệm

• Bài toán xoay vòng có thể được giải quyết chỉ bằng cách thay đổi thứ tự in ra mà không cần thay đổi dữ liệu trong bộ nhớ.
• Công thức quan trọng: k = k % n để xử lý các trường hợp k lớn hơn độ dài mảng.

Lỗi thường gặp

• Quên giảm k modulo n dẫn đến lỗi truy cập ngoài biên mảng hoặc in sai thứ tự.
• Sử dụng biến kiểu int cho n và k nhưng để k quá lớn (lên tới 10^9) có thể gây tràn số nếu không dùng kiểu dữ liệu lớn hơn (long long) ở một số ngôn ngữ/tình huống tính toán khác, mặc dù trong C++/C hiện đại với int k; k %= n; thì k sau khi chia lấy dư sẽ fit trong int vì n <= 10^6.