Hiểu bài toán

Cho một mảng A gồm n số nguyên. Nhiệm vụ là biến đổi mảng theo quy tắc sau: Với mỗi chỉ số i là số lẻ (tính từ 0), tăng giá trị của A[i] lên một lượng bằng chênh lệch giữa hai phần tử lân cận của nó. Nếu phần tử ở đầu hoặc cuối mảng (không có lân cận trái hoặc phải), coi như lân cận đó bằng 0. Mảng đầu ra là mảng sau khi đã biến đổi.

Cụ thể:

• Chỉ số i lẻ: A[i] mới = A[i] cũ + |A[i-1] - A[i+1]| (nếu có đủ 2 lân cận).
• Nếu i = 0 (lẻ) nhưng là phần tử đầu tiên: Chỉ có lân cận phải (A[1]), lân cận trái coi như 0. Theo công thức chênh lệch 2 bên, ta có |0 - A[1]| = A[1].
• Nếu i = n-1 (lẻ) nhưng là phần tử cuối cùng: Chỉ có lân cận trái (A[n-2]), lân cận phải coi như 0. Tương tự, |A[n-2] - 0| = A[n-2].

Ví dụ mẫu: Input 4 [1, 3, 2, 5]

• i=0 (lẻ, đầu mảng): 1 + |0 - 3| = 4.
• i=1 (lẻ): 3 + |1 - 2| = 3 + 1 = 4.
• i=2 (chẵn): không thay đổi -> 2.
• i=3 (lẻ, cuối mảng): 5 + |2 - 0| = 7. Output: 1 4 2 7.

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

Cách Xử lý trực tiếp theo điều kiện biên

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

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

    for (int i = 0; i < n; i++) {
        if (i % 2 == 1) { // Chỉ số lẻ
            if (i == n - 1) { // Phần tử cuối
                a[i] += abs(a[i - 1]);
            } else { // Các trường hợp còn lại (đầu hoặc giữa)
                // Nếu i=0, a[i-1] không tồn tại. Solution 2 check riêng, nhưng có thể gộp
                // vì i=0 là chẵn nên không vào đây. Chỉ cần xử lý i < n-1 là đủ.
                // Tuy nhiên, để chắc chắn xử lý đúng biên, ta check:
                int left = (i - 1 >= 0) ? abs(a[i-1]) : 0;
                int right = (i + 1 < n) ? abs(a[i+1]) : 0;
                // Công thức chênh lệch 2 bên: |left - right|.
                // Nếu chỉ có phải (i=0): |0 - right| = right.
                // Nếu chỉ có trái (i=n-1): |left - 0| = left.
                // Nếu có đủ: |left - right|.
                // Solution 1 dùng a[i-1] và a[i+1] trực tiếp khi i < n-1. Với i=0, i-1 không hợp lệ.
                // May thay, i=0 là chẵn nên không vào nhánh này. Solution 1 an toàn.
                a[i] += abs(a[i - 1] - a[i + 1]);
            }
        }
    }
    // Output logic
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

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

Đây là cách tiếp cận cơ bản nhất, bám sát mô tả vấn đề. Ta duyệt qua từng phần tử của mảng. Nếu chỉ số là số lẻ, ta thực hiện tăng giá trị phần tử đó.

• Trong các giải pháp đã cho, Solution 1 (Zed) là ví dụ điển hình. Solution này chỉ kiểm tra if (i == n - 1) cho trường hợp biên cuối mảng. Do điều kiện vòng lặp if (i % 2 == 1) và i bắt đầu từ 0, chỉ số 0 (lẻ) không bao giờ được xử lý do i phải nhỏ hơn n-1.
• Solution 2 (tuyetlancontact) chi tiết hơn: kiểm tra if ((i-1>=0) && (i+1<n)) cho các phần tử ở giữa, và else xử lý các biên (dù thực tế biên đầu mảng có chỉ số lẻ duy nhất là i=0 rất hiếm gặp trong các test case tiêu chuẩn nhưng vẫn an toàn).

Cách làm này đảm bảo tính chính xác bằng cách xử lý từng trường hợp đặc biệt của chỉ số lẻ (đầu mảng, cuối mảng, hoặc ở giữa).

Cách Tối ưu hóa với biến trung gian

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

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

    for (int i = 1; i < n; i += 2) {
        int left = (i - 1 >= 0) ? a[i - 1] : 0;
        int right = (i + 1 < n) ? a[i + 1] : 0;
        // Dựa vào logic: |left - right|
        // Nếu không có left (i=0, không xảy ra vì i=1), left=0 -> |0 - right| = right.
        // Nếu không có right (i=n-1), right=0 -> |left - 0| = left.
        a[i] += abs(left - right);
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

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

Tiếp cận này là một phiên bản gọn gàng hơn của phương pháp trực tiếp.

• Thay vì dùng vòng lặp for (int i = 0; i < n; i++) và kiểm tra if (i % 2 == 1), ta có thể dùng for (int i = 1; i < n; i += 2) để duyệt trực tiếp qua các chỉ số lẻ. Điều này giúp bỏ qua các phép chia và kiểm tra điều kiện lặp.
• Để xử lý các trường hợp biên (đầu và cuối mảng) một cách thống nhất, ta sử dụng các biến left và right. Nếu chỉ số lẻ nằm ở biên, chỉ số truy cập mảng tương ứng sẽ nằm ngoài phạm vi, ta gán giá trị cho biến đó là 0.
• Sau đó, ta luôn cộng abs(left - right) vào a[i]. Công thức này bao hàm cả trường hợp chỉ có lân cận trái, chỉ có lân cận phải, hoặc có đủ cả hai.
• Solution 3 (hoangdaimyloc27) là một biến thể của cách tiếp cận này. Solution này dùng mảng phụ b và chỉ xử lý các phần tử ở giữa (i=1 đến n-2). Sau đó, giải pháp này dùng câu lệnh if (n%2 == 0) để xử lý riêng phần tử cuối cùng (vì nếu n chẵn, chỉ số cuối cùng n-1 là lẻ). Cách này cũng tối ưu vì bỏ qua các phép tính không cần thiết.

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

Bài học kinh nghiệm

• Công thức chênh lệch |A[i-1] - A[i+1]| có thể được tổng quát hóa cho các biên bằng cách coi phần tử ngoài mảng có giá trị 0. Khi đó, giá trị tăng thêm luôn là |left - right| với left và right được gán 0 nếu không t tồn tại.
• Việc thay đổi cách lặp từ duyệt toàn bộ mảng sang lặp bước 2 (i += 2) giúp code ngắn gọn và hiệu hiệu quả hơn một chút về mặt logic.
• Sử dụng hàm abs() từ thư viện <stdlib.h> (hoặc <math.h>) là bắt buộc để tính giá trị tuyệt đối.

Lỗi thường gặp

• Truy cập ngoài biên mảng: Khi tính a[i-1] hoặc a[i+1], cần đảm bảo chỉ số nằm trong khoảng [0, n-1]. Các giải pháp đều xử lý điểm này, nhưng nếu cẩn thận, nên dùng phép kiểm tra điều kiện.
• Sai lệch về chỉ số: Nhớ rằng chỉ số mảng tính từ 0. Chỉ số lẻ là 1, 3, 5,... Do đó, chỉ số 0 không bao giờ được xử lý (trừ khi n=1, nhưng khi n=1, chỉ số 0 là chẵn).
• Kiểu dữ liệu: Mặc dù output yêu cầu số nguyên, nhưng khi tính toán (abs), cần đảm bảo không bị tràn số nếu các giá trị đầu vào lớn (đến 10^8). Tuy nhiên, trong C/C++, int (thường là 32-bit) có thể chứa đến ~2*10^9, nên tổng 10^8 + 10^8 vẫn an toàn.