Editorial for findper: Biến đổi dãy số

Hiểu bài toán

Bài toán yêu cầu mô phỏng quá trình xây dựng một dãy số B rỗng thông qua N bước biến đổi. Tại mỗi bước i (từ 1 đến N), ta thực hiện hai thao tác: thêm số a_i vào cuối dãy B, và sau đó đảo ngược toàn bộ dãy B. Với ràng buộc N <= 2*10^5, việc mô phỏng trực tiếp bằng cách thêm và đảo ngược mảng (O(N) cho mỗi bước) sẽ dẫn đến độ phức tạp tổng thể O(N^2), gây quá thời gian. Ta cần tìm một quy luật hoặc cách tiếp cận hiệu quả hơn để nhận ra dãy kết quả mà không cần thực hiện các phép đảo ngược thực tế.

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

Cách Mô phỏng với Deque (Nhanh)

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

int main() {
    int n;
    cin >> n;
    deque<int> b;
    bool reversed = false; // Trạng thái đảo ngược hiện tại

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (!reversed) {
            // Nếu chưa đảo ngược, thêm vào cuối
            b.push_back(a);
        } else {
            // Nếu đã đảo ngược, thêm vào đầu (tương đương cuối của bản chất)
            b.push_front(a);
        }
        // Luôn đảo ngược trạng thái sau mỗi bước
        reversed = !reversed;
    }

    // Nếu số bước N là chẵn, trạng thái cuối cùng là bình thường.
    // Nếu N là lẻ, trạng thái cuối cùng là đảo ngược.
    if (n % 2 == 0) {
        for (int x : b) cout << x << " ";
    } else {
        for (int i = b.size() - 1; i >= 0; i--) cout << b[i] << " ";
    }
    return 0;
}

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

Cách tiếp cận này mô phỏng lại quá trình biến đổi nhưng tối ưu hóa việc 'đảo ngược'. Thay vì thực sự đảo ngược mảng, ta chỉ cần nhớ xem dãy đang bị đảo ngược hay không (biến.ToBoolean). Nếu dãy đang ở trạng thái 'bình thường', thêm ai vào cuối. Nếu dãy đang ở trạng thái 'đảo ngược', thêm ai vào đầu. Cuối cùng, in ra dãy theo đúng trạng thái cuối cùng của N. Sử dụng cấu trúc dữ liệu Deque (Double Ended Queue) cho phép thêm vào đầu/cuối trong thời gian O(1).

Cách Quy luật trực tiếp (Tối ưu)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vector<long long> b(n);
    int left = 0, right = n - 1;

    // Duyệt từ phần tử cuối cùng của mảng a về đầu
    // Nếu (n-1 - i) là số chẵn (tính từ 0), ta thêm vào bên phải của dãy B
    // Nếu (n-1 - i) là số lẻ, ta thêm vào bên trái của dãy B
    // (Cách khác: Nếu N chẵn, a[N-1] vào đầu, a[N-2] vào cuối...)

    // Ta có thể dùng biến đếm lùi từ N-1
    for (int i = n - 1; i >= 0; i--) {
        if ((n - 1 - i) % 2 == 0) {
            b[right--] = a[i];
        } else {
            b[left++] = a[i];
        }
    }

    // Nếu N chẵn, thứ tự in là b[0] -> b[n-1]
    // Nếu N lẻ, thứ tự in là b[n-1] -> b[0]
    // Thực tế, với cách điền mảng như trên:
    // Khi N chẵn: các số a[lẻ] nằm bên phải dãy B, a(chẵn) nằm bên trái -> in từ 0
    // Khi N lẻ: ...

    // Đơn giản hóa logic điền:
    // Solution 2 trong bài đã cho cách điền khá rõ ràng.
    // Nếu N chẵn: Lấy các số ở vị trí chẵn của a (0, 2, 4...), đảo ngược thứ tự và put vào đầu.
    // Lấy các số ở vị trí lẻ của a (1, 3, 5...), put vào cuối.
    // Nếu N lẻ: ...

    // Code tối ưu hóa theo Solution 2:
    int x = 0;
    if (n % 2 == 0) {
        for (int i = n - 1; i >= 0; i -= 2) b[x++] = a[i];
        for (int i = 0; i < n; i += 2) b[x++] = a[i];
    } else {
        for (int i = n - 1; i >= 0; i -= 2) b[x++] = a[i];
        for (int i = 1; i < n; i += 2) b[x++] = a[i];
    }

    for (int i = 0; i < n; i++) cout << b[i] << " ";
    return 0;
}

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

Đây là cách tiếp cận hiệu quả nhất, không cần dùng cấu trúc Deque động. Ta nhận thấy quy luật:

• Các phần tử được thêm vào luân phiên ở 2 phía của dãy B (đầu hoặc cuối).
• Nếu N chẵn, dãy B cuối cùng sẽ có thứ tự 'bình thường' (không bị đảo ngược).
• Nếu N lẻ, dãy B cuối cùng sẽ bị 'đảo ngược'.

Ta có thể chia mảng A thành 2 dãy: các số ở vị trí chẵn (0, 2, ...) và vị trí lẻ (1, 3, ...) trong mảng A.

• Khi N chẵn: Các số ở vị trí chẵn của A sẽ nằm ở nửa sau của B (theo thứ tự A), các vị trí lẻ nằm ở nửa trước. Ta chỉ cần nối các phần tử A[odd] (đảo ngược) + A[even] (thứ tự bình thường) là ra kết quả.
• Khi N lẻ: Tương tự nhưng thứ tự bị hoán đổi.

Cụ thể: Nếu N chẵn: In a[N-1], a[N-3], ... xong in a[0], a[2], ... Nếu N lẻ: In a[N-1], a[N-3], ... xong in a[1], a[3], ...

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

Bài học kinh nghiệm

• Việc 'đảo ngược' sau mỗi bước có thể được tối ưu bằng cách thay đổi hướng chèn vào deque hoặc suy ra quy luật vị trí cuối cùng của các phần tử.
• Nếu N chẵn, thứ tự ban đầu của các phần tử được giữ lại (về mặt logic chẵn/lẻ). Nếu N lẻ, thứ tự bị hoán đổi.

Lỗi thường gặp

• Lầm tưởng độ phức tạp O(N^2) của mô phỏng trực tiếp (dùng vector + reverse) là chấp nhận được dẫn đến TLE.
• Sai lệch khi in kết quả cuối cùng của Deque: Nếu N lẻ, deque đang ở trạng thái 'đảo ngược', cần in từ cuối lên đầu thay vì đầu lên cuối.
• Quên cập nhật trạng thái đảo ngược đúng cách (ví dụ: chỉ đảo ngược khi thêm, hoặc dùng biến boolean sai).