Hiểu bài toán

Cho mảng A gồm N phần tử đánh số từ 1 đến N. Tìm một hoán vị B của A sao cho với mọi i, hiệu |B[i] - A[i]| = K. Nếu K = 0, B phải bằng A. Nếu K > 0, ta cần tìm cách ghép các giá trị.

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

Cách Kiểm tra chia hết (Incorrect Logic)

#include <stdio.h>
int main(){
    int n, k ;
    scanf("%d %d", &n , &k) ;
    if ( k == 0 ) { for (int i=1; i<=n; i++) printf("%d ", i) ; } else 
    if ( (n/k)%2 == 1 ) {printf("-1"); }
    else 
    {
        for (int i=1; i<=n; i++ )
        {
            int j= (i-1)/k ;
             if ( j%2 == 0 ) printf("%d ", i+k) ; else printf("%d ", i-k) ;
        }

    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đoạn code này sử dụng điều kiện (n/k)%2 == 1 để kiểm tra. Logic này không chính xác cho tất cả các trường hợp (ví dụ N=6, K=2 thỏa mãn nhưng N/K=3 là số lẻ). Tuy nhiên, cách sinh ra mảng B bằng cách chia nhóm các phần tử liên tiếp độ dài K và hoán đổi xen kẽ (i+k nếu nhóm chẵn, i-k nếu nhóm lẻ) là một ý tưởng đúng đắn.

Cách Kiểm tra chia hết cho 2K (Đúng)

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

int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    if(k==0){
        for(int i=1;i<=n;i++){
            printf("%d ",i);
        }
    }
    else if(n/2%k!=0){
        printf("-1");
    }
    else{
        for(int i=1;i<=n;i++){
            if((i-1)/k%2==0){
                printf("%d ",i+k);
            }
            else{
                printf("%d ",i-k);
            }
        }
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Cách tiếp cận này kiểm tra điều kiện n % (2*k) == 0 (thông qua n/2%k != 0). Điều kiện này đảm bảo rằng mảng có thể được chia thành các cặp hoặc khối 2*K phần tử để hoán đổi. Nếu thỏa mãn, nó in ra kết quả bằng cách chia mảng thành các khối liên tiếp độ dài K và hoán đổi giá trị giữa các khối chẵn và lẻ.

Cách Giải thuật trực tiếp (Direct Construction)

#include <stdio.h>

int main() {
    long long n, k;
    scanf("%lld %lld", &n, &k);

    // Trường hợp đặc biệt
    if (k == 0) {
        for (long long i = 1; i <= n; i++) printf("%lld ", i);
        return 0;
    }

    // Nếu không chia hết cho 2k thì không thể tạo hoán vị hợp lệ
    if (n % (2 * k) != 0) {
        printf("-1");
        return 0;
    }

    long long b[n + 1];

    for (long long i = 1; i <= n; i++) {
        long long block = (i - 1) / k;
        if (block % 2 == 0)
            b[i] = i + k;
        else
            b[i] = i - k;
    }

    for (long long i = 1; i <= n; i++)
        printf("%lld ", b[i]);

    return 0;
}

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

Đây là cách tiếp cận tối ưu và chính xác nhất. Đầu tiên kiểm tra n % (2 * k) == 0. Nếu K=0, in ra dãy ban đầu. Nếu K>0 và chia hết cho 2K, ta dùng quy tắc: chia mảng thành các khối K phần tử. Khối 0, 2, 4... sẽ được hoán đổi với khối 1, 3, 5... tương ứng. Cụ thể, nếu (i-1)/k là số chẵn, B[i] = i + K; ngược lại B[i] = i - K.

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

Bài học kinh nghiệm

• Vấn đề có thể được chia thành các khối độc lập. Nếu K > 0, ta có thể hoán đổi các giá trị trong các khối liên tiếp độ dài K.
• Điều kiện tồn tại nghiệm là N phải chia hết cho 2*K (hoặc K=0). Điều này đảm bảo các cặp giá trị hoán đổi không bị trùng lặp và nằm trong giới hạn [1, N].
• Một cách hiểu khác: Ta cần ghép các số i thành các cặp (i, i+K). Để tạo thành hoán vị, các cặp này phải tạo thành các chu trình hoặc đường đi, điều này chỉ xảy ra khi N chia hết cho 2K.

Lỗi thường gặp

• Sai điều kiện kiểm tra: Dùng n/k chia hết cho 2 thay vì n chia hết cho 2*k. Ví dụ N=6, K=2, N/K=3 không chia hết cho 2 nhưng N%(2*K)=0 nên nghiệm t tồn tại.
• Quên xử lý trường hợp K=0: Khi K=0, điều kiện chia hết cho 2K không có ý nghĩa, phải in ra chính mảng A.
• Lỗi truy cập mảng: Khi tính i+k hoặc i-k, cần đảm bảo giá trị nằm trong [1, N].