Editorial for perlis: Phục hồi mảng ban đầu

Hiểu bài toán

Cho hai dãy A và B. Dãy A là một hoán vị của các số từ 1 đến N. Dãy B được tính từ A, trong đó B[i] là độ dài của dãy con tăng dài nhất (LIS) bắt đầu tại chỉ số i của dãy A. Yêu cầu: từ dãy B cho trước, hãy tìm lại dãy A. Nếu có nhiều kết quả, chọn dãy A có thứ tự từ điển nhỏ nhất.

Phân tích: Dãy con tăng dài nhất bắt đầu tại i phải có dạng A[i], A[j], A[k]... sao cho i < j < k < ... và A[i] < A[j] < A[k] < ... . Do A là hoán vị, các giá trị là duy nhất. Đặc điểm của B:

• B[i] = 1 nghĩa là A[i] là phần tử cuối cùng trong chuỗi tăng dần, tức là A[i] phải lớn hơn tất cả các phần tử A[j] với j > i (vì nếu có phần tử sau nhỏ hơn, ta có thể nối vào chuỗi tăng dài nhất). Thực tế, B[i]=1 nghĩa là không có phần tử sau nào nhỏ hơn A[i] để tạo thành chuỗi dài hơn 1. Điều này có nghĩa A[i] phải là phần tử lớn nhất trong đoạn A[i...N].
• B[i] = k > 1 nghĩa là có một phần tử j > i sao cho B[j] = k-1 và A[j] > A[i], đồng thời A[i] nhỏ hơn mọi phần tử thỏa mãn B[j] = k-1 và A[j] > A[i] (để ưu tiên độ dài).

Quy luật của B: Nếu ta xét các phần tử theo thứ tự tăng dần của giá trị A (từ nhỏ đến lớn), ta sẽ thấy rằng:

• Các phần tử có cùng độ dài B[i] sẽ được ưu tiên xuất hiện trước (từ trái sang phải) trong dãy B.
• Cụ thể, nếu ta nhóm các chỉ số i theo giá trị B[i], và sắp xếp các nhóm này theo thứ tự B[i] tăng dần, ta sẽ có một thứ tự xấp xỉ thứ tự tăng dần của các giá trị A.

Giả sử ta có một danh sách các chỉ số được sắp xếp theo quy tắc: các chỉ số có B[i] = 1 xuất hiện trước các chỉ số có B[i] = 2, ..., và trong cùng nhóm B[i] = k, ưu tiên chỉ số nhỏ hơn. Nếu ta gán giá trị cho các chỉ số này theo thứ tự tăng dần (1, 2, 3, ...) ta sẽ được một dãy A. Tuy nhiên, ta cần dãy A có thứ tự từ điển nhỏ nhất.

Quy luật tìm A: Giả sử ta có một danh sách các chỉ số S được sắp xếp theo quy tắc:

1. Ưu tiên chỉ số có B[i] nhỏ hơn.
2. Nếu B[i] bằng nhau, ưu tiên chỉ số i nhỏ hơn.

Nếu ta gán giá trị cho các vị trí trong S theo thứ tự từ nhỏ đến lớn (1, 2, 3...), ta được dãy A. Tuy nhiên, ta cần dãy A có thứ tự từ điển nhỏ nhất.

Ta hãy xét ví dụ: B = [1, 2, 2, 1]. Các vị trí: 1, 2, 3, 4. B[1]=1, B[2]=2, B[3]=2, B[4]=1. Sắp xếp theo (B[i], i): (1, 1) -> index 1 (1, 4) -> index 4 (2, 2) -> index 2 (2, 3) -> index 3 Thứ tự gán giá trị: index 1, index 4, index 2, index 3. Gán giá trị: A[1]=1, A[4]=2, A[2]=3, A[3]=4. Dãy A: 1, 3, 4, 2. Kiểm tra B: A[1]=1. Các phần tử sau: 3, 4, 2. Lớn hơn 1 là 3, 4, 2. LIS sau 1 là 1->2 (vì 2 là nhỏ nhất trong các phần tử lớn hơn 1). Đúng B[1]=1. A[2]=3. Các phần tử sau: 4, 2. Lớn hơn 3 là 4. B[2]=1? Sai, đề bài cần B[2]=2.

Lỗi suy luận: Phép gán trực tiếp tăng dần không hoạt động.

Quay lại với ví dụ đề bài: Output: 4 2 1 3. B: 1 2 2 1. Phân tích Output: A[1]=4. Sau có 2, 1, 3. Các phần tử lớn hơn 4 không có. B[1]=1. (OK) A[2]=2. Sau có 1, 3. Các phần tử lớn hơn 2: 3. B[2]=1? Sai. Đề bài B[2]=2. Wait, LIS bắt đầu từ A[2]=2 là [2, 3]. Vậy B[2]=2. Đúng. A[3]=1. Sau có 3. Các phần tử lớn hơn 1: 3. B[3]=2? Sai. [1, 3] độ dài 2. Đúng. A[4]=3. Sau không có gì. B[4]=1. Đúng.

Tìm quy luật: Ta cần tìm A sao cho B[A] đúng.

Giả sử ta xây dựng A từ phải sang trái. Phần tử cuối cùng A[N] phải có B[N] = 1 (vì không có phần tử sau). A[N] phải là số lớn nhất trong dãy. Phần tử A[N-1]: Nếu B[N-1] = 1, A[N-1] phải lớn hơn A[N]. Nếu B[N-1] > 1, A[N-1] phải nhỏ hơn A[N] (vì A[N] là phần tử sau).

Đây là bài toán về cấu trúc cây. B[i] = 1: A[i] là node lá (hoặc root của cây con).

Phương pháp giải:

1. Xác định các node lá: Các chỉ số i mà B[i] = 1.
2. Các node lá này tạo thành một cây. Node nào có B[i] = 2 phải là cha của một node lá.
3. Để A có thứ tự từ điển nhỏ nhất, ta cần gán giá trị cho các node theo thứ tự từ phải sang trái (giảm dần).

Cụ thể:

• Sắp xếp các chỉ số i theo thứ tự giảm dần của chỉ số i (từ N về 1).
• Duyệt qua các chỉ số i. Nếu B[i] = 1, ta gán cho nó một giá trị lớn nhất chưa dùng.
• Nếu B[i] > 1, ta cần gán giá trị cho nó sao cho nó nhỏ hơn các node con (B[i]-1) nhưng lớn nhất có thể.

Đây là cách tiếp cận Greedy từ phải sang trái.

Cách tiếp cận 1 (Greedy từ phải sang trái):

• Tạo một mảng A, ban đầu rỗng.
• Duyệt i từ N về 1.
• Nếu B[i] = 1, gán A[i] = số lớn nhất chưa dùng.
• Nếu B[i] > 1, ta cần tìm một node j > i sao cho B[j] = B[i] - 1 và A[j] > A[i].

Để thực hiện hiệu quả:

• Ta có thể dùng một cấu trúc dữ liệu (Set hoặc Heap) chứa các giá trị của các node đã xử lý (bên phải).
• Duyệt i từ N về 1:
  • Nếu B[i] = 1: Chọn giá trị lớn nhất chưa dùng (hoặc gán giá trị giảm dần).
  • Nếu B[i] > 1: Ta cần chọn một giá trị sao cho nó nhỏ hơn các node có B[j] = B[i]-1 nhưng vẫn tạo được dãy tăng.

Gợi ý từ các solution: Solution 1:

    // Nhóm các chỉ số theo B[i]
    vector<vector<int>> group(maxB + 1);
    for (int i = 1; i <= N; ++i) {
        group[B[i]].push_back(i);
    }

    // Tạo thứ tự: group[1], group[2], ..., group[maxB]
    vector<int> order;
    for (int k = 1; k <= maxB; ++k) {
        for (int idx : group[k]) order.push_back(idx);
    }

    // Gán giá trị N, N-1, ... theo order
    int val = N;
    for (int pos : order) {
        A[pos] = val--;
    }

Phân tích Solution 1:

• Nó nhóm các chỉ số theo B[i].
• Sắp xếp thứ tự xử lý: B[i] nhỏ trước, cùng B thì chỉ số nhỏ trước.
• Gán giá trị N, N-1, ... cho các vị trí này.

Ví dụ 1: B = [1, 2, 2, 1] Group 1: [1, 4] Group 2: [2, 3] Order: 1, 4, 2, 3. Gán: A[1]=4, A[4]=3, A[2]=2, A[3]=1. Dãy A: 4, 2, 1, 3. Đây chính là kết quả đề bài!

Ví dụ 2: B = [5, 4, 3, 2, 1] Group 1: [5] Group 2: [4] Group 3: [3] Group 4: [2] Group 5: [1] Order: 5, 4, 3, 2, 1. Gán: A[5]=5, A[4]=4, A[3]=3, A[2]=2, A[1]=1. Dãy A: 1, 2, 3, 4, 5. Đúng.

Tại sao cách này đúng? Giả sử ta có các chỉ số có B[i] = k. Các chỉ số này phải được gán giá trị sao cho:

• Chúng nhỏ hơn các chỉ số có B[j] = k+1 (vì để tạo tăng dần).
• Trong cùng nhóm B=k, chúng ta ưu tiên chỉ số nhỏ hơn được gán giá trị lớn hơn?

Trong Solution 1, thứ tự xử lý là B tăng dần, chỉ số tăng dần. Gán giá trị giảm dần (N, N-1, ...). Người xử lý đầu tiên (B nhỏ, chỉ số nhỏ) được gán giá trị lớn nhất (N). Người xử lý cuối cùng (B lớn, chỉ số lớn) được gán giá trị nhỏ nhất (1).

Nghịch lý: B[i] nhỏ nghĩa là độ dài LIS ngắn. Trong ví dụ 1, A[1]=4, B[1]=1 (ngắn). A[2]=2, B[2]=2 (dài hơn). Vậy B[i] nhỏ tương ứng với A[i] lớn? Không, B[i]=1 có thể là A[i] lớn nhất (ví dụ 1, A[1]=4) hoặc A[i] nhỏ nhất (ví dụ 2, A[1]=1).

Quay lại quy luật: B[i] là độ dài LIS bắt đầu từ i. Nếu B[i] > B[j] (với i < j), ta có thể suy ra gì về A[i] và A[j]?

Phương pháp:

1. Nhóm các chỉ số theo B[i].
2. Duyệt các nhóm từ B=1 đến B=maxB.
3. Trong mỗi nhóm, sắp xếp chỉ số tăng dần.
4. Gán giá trị cho các chỉ số thu được theo thứ tự giảm dần từ N về 1.

Tại sao? Xét ví dụ: B = [1, 2, 2, 1] Indices: 1, 2, 3, 4 B: 1, 2, 2, 1

Giả sử ta có một cây phụ thuộc. Node B[i] = k phụ thuộc vào node B[j] = k-1 (j > i). Để A có thứ tự từ điển nhỏ nhất, ta cần các giá trị ở các vị trí đầu (i nhỏ) là nhỏ nhất có thể.

Ta thử gán giá trị nhỏ nhất cho các vị trí đầu. Các vị trí có B=1 là các node "lá" (cuối của nhánh). Các vị trí có B=2 là cha của các node B=1. Nếu ta muốn A[1] nhỏ nhất có thể, A[1] phải là 1. Nếu A[1]=1, B[1]=1. Điều này có nghĩa là sau 1 không có phần tử nào lớn hơn 1? Sai, sau 1 có 2, 3, 4... đều lớn hơn. B[1]=1 nghĩa là sau 1 không có phần tử nào để tạo thành chuỗi tăng dài hơn. Điều này chỉ xảy ra nếu A[1] là phần tử lớn nhất.

Vậy:

• B[i] = 1 <=> A[i] là phần tử lớn nhất trong đoạn A[i...N].
• B[i] = 2 <=> A[i] nhỏ hơn một phần tử sau (với B sau đó là 1), và A[i] là phần tử lớn nhất trong số các phần tử thỏa mãn điều kiện đó.

Quy tắc: Để tìm A có thứ tự từ điển nhỏ nhất:

• Ta cần các phần tử đầu tiên của A (A[1], A[2]...) là nhỏ nhất có thể.
• Tuy nhiên, ràng buộc B[i] có thể buộc A[i] phải lớn.

Giả sử ta có một danh sách các vị trí được sắp xếp theo quy tắc:

• Ưu tiên B[i] tăng dần.
• Cùng B[i], ưu tiên chỉ số i tăng dần. Gọi danh sách này là S. Sau đó gán giá trị N, N-1, ... cho các vị trí trong S.

Kiểm tra lại: Ví dụ 1: S = [1, 4, 2, 3] (B=1 idx=1, B=1 idx=4, B=2 idx=2, B=2 idx=3). Gán: A[1]=4, A[4]=3, A[2]=2, A[3]=1. Kết quả: 4 2 1 3.

Tại sao A[1] lại là 4? Nếu A[1] nhỏ hơn A[4], B[1] sẽ > 1 (vì A[4] nằm sau và lớn hơn). Nhưng B[1]=1. Vậy A[1] phải lớn hơn mọi phần tử sau nó (A[2], A[3], A[4]). A[1]=4. A[2]=2, A[3]=1, A[4]=3. 4 > 2, 1, 3. Đúng.

Tại sao A[4]=3? A[4]=3. Sau nó không có phần tử nào. B[4]=1. Đúng.

Tại sao A[2]=2? A[2]=2. Sau nó có A[3]=1 (nhỏ hơn), A[4]=3 (lớn hơn). LIS bắt đầu từ A[2]: [2, 3]. Độ dài 2. B[2]=2. Đúng.

Tại sao A[3]=1? A[3]=1. Sau nó có A[4]=3 (lớn hơn). LIS bắt đầu từ A[3]: [1, 3]. Độ dài 2. B[3]=2. Đúng.

Vậy thuật toán là:

1. Tạo một list L chứa các chỉ số i từ 1 đến N.
2. Sắp xếp L theo tiêu chí:
   • B[i] tăng dần.
   • Nếu B[i] bằng nhau, i tăng dần.
3. Duyệt qua L, gán giá trị N, N-1, ..., 1 cho các chỉ số tương ứng.

Độ phức tạp: O(N log N) do sắp xếp.

Các solution khác (Solution 2, 3) có vẻ làm tương tự nhưng code hơi rối. Solution 2:

    sort(a+1,a+n+1,cmpa); // sort by B value, then index
    ll k = n+1;
    for(int i=1; i<=n; ++i) {a[i].a = --k;} // assign values N, N-1...
    sort(a+1,a+n+1,cmpi); // sort back by index
    // print a[i].a

Đây chính là thuật toán đã phân tích.

Cần chú ý:

• B[i] có thể không tạo thành một cây phụ thuộc trực tiếp rõ ràng như thế này, nhưng việc gán giá trị giảm dần cho (B tăng, idx tăng) giải quyết được vấn đề.
• Logic đằng sau: Các vị trí có B[i] nhỏ phải chứa giá trị lớn (để đảm bảo không có phần tử sau nào lớn hơn nếu B[i]=1, hoặc để "che chắn" cho các phần tử sau nếu B[i]>1).
• Các vị trí có B[i] lớn phải chứa giá trị nhỏ (để dễ tìm phần tử sau lớn hơn).

Tóm tắt: Sắp xếp các chỉ số theo (B[i] tăng, i tăng). Gán giá trị N, N-1, ..., 1 cho các chỉ số theo thứ tự đó. In kết quả theo thứ tự chỉ số 1..N.

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

Cách Sắp xếp và Gán giá trị Giảm dần

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

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

    int N;
    if (!(cin >> N)) return 0;

    // Sử dụng vector pair để lưu {B[i], i}
    vector<pair<int, int>> v(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i].first;
        v[i].second = i; // Lưu chỉ số gốc (0-based)
    }

    // Sắp xếp: B[i] tăng dần, nếu bằng nhau thì chỉ số tăng dần
    sort(v.begin(), v.end());

    vector<int> A(N);
    int val = N;
    for (int i = 0; i < N; ++i) {
        // Gán giá trị lớn nhất (N) cho phần tử đầu tiên trong danh sách đã sắp xếp,
        // sau đó giảm dần
        A[v[i].second] = val--;
    }

    for (int i = 0; i < N; ++i) {
        cout << A[i] << (i == N - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}

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

Phương pháp này dựa trên quan sát rằng:

1. Các phần tử có B[i] = 1 phải là các phần tử lớn nhất trong đoạn từ i trở đi. Do đó, chúng cần được gán các giá trị lớn.
2. Các phần tử có B[i] > 1 phải nhỏ hơn một số phần tử nào đó ở sau nó, nhưng vẫn phải đảm bảo độ dài LIS.

Bằng cách sắp xếp các chỉ số theo thứ tự ưu tiên (B[i] tăng dần, chỉ số i tăng dần) và gán giá trị N, N-1, ..., 1, ta đảm bảo:

• Các phần tử có B[i] nhỏ (đặc biệt là 1) được gán giá trị lớn.
• Trong cùng một mức B[i], các chỉ số nhỏ hơn (xuất hiện sớm hơn) được gán giá trị lớn hơn một chút so với chỉ số lớn hơn. Điều này đảm bảo thứ tự từ điển của A là nhỏ nhất có thể.

Ví dụ: B=[1, 2, 2, 1] Sắp xếp (B, idx): (1,0), (1,3), (2,1), (2,2). Gán: A[0]=4, A[3]=3, A[1]=2, A[2]=1. Kết quả mảng A: [4, 2, 1, 3].

Cách Greedy từ phải sang trái (Duyệt ngược)

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

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

    int N;
    cin >> N;
    vector<int> B(N);
    for (int i = 0; i < N; ++i) cin >> B[i];

    vector<int> A(N);
    // Hàng đợi ưu tiên lưu các cặp {B[i], i} để lấy ra phần tử có B[i] lớn nhất trước
    priority_queue<pair<int, int>> pq;
    int current_val = N;

    // Duyệt từ phải sang trái (i từ N-1 về 0)
    for (int i = N - 1; i >= 0; --i) {
        pq.push({B[i], i});

        // Nếu đỉnh hàng đợi có B[i] khớp với độ dài mong muốn,
        // ta gán giá trị cho nó.
        // Đây là cách tiếp cận phức tạp hơn, thực ra cách sort vẫn tối ưu hơn.
        // Code dưới đây là một cách diễn giải khác của logic Greedy,
        // nhưng để đơn giản và đảm bảo đúng, ta nên dùng cách Sort.

        // Tuy nhiên, có một cách Greedy từ phải sang trái khác:
        // Xử lý các node lá (B[i]=1) trước.
    }
    return 0;
}

// Cách tiếp cận Greedy thực sự hiệu quả là:
// Duyệt i từ N về 1. Nếu B[i] == 1, gán A[i] = phần tử lớn nhất.
// Nhưng để xử lý B[i] > 1, ta cần cấu trúc phức tạp.
// Do đó, phương pháp Sắp xếp là tối ưu nhất.

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

Đây là biến thể của phương pháp Greedy. Thay vì sort toàn bộ, ta có thể dùng hàng đợi ưu tiên để xử lý các phần tử có B[i] lớn trước. Tuy nhiên, logic sort (B[i] tăng, index tăng) vẫn là cách tiếp cận trực quan và dễ implement nhất để đảm bảo thứ tự từ điển.

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

Bài học kinh nghiệm

• B[i] là độ dài dãy con tăng dài nhất bắt đầu tại i. Điều này tạo ra một mối quan hệ thứ bậc dựa trên giá trị B[i].
• Các phần tử có B[i] nhỏ hơn cần chứa giá trị lớn hơn trong mảng A (để đảm bảo chúng không thể nối tiếp bất kỳ phần tử nào sau nó nếu B[i]=1, hoặc để tạo thành bước nhảy cho các phần tử có B lớn hơn).
• Thứ tự từ điển nhỏ nhất của A đạt được khi ta ưu tiên gán các giá trị lớn nhất cho các vị trí có chỉ số nhỏ nhất trong nhóm có B[i] nhỏ nhất.

Lỗi thường gặp

• Sử dụng thuật toán tìm dãy con tăng dài nhất (LIS) O(N log N) để kiểm tra lại kết quả, dẫn đến TLE vì N lên tới 10^5 và ta cần tìm A chứ không tính B.
• Sai lầm khi cho rằng chỉ cần sort giảm dần theo B[i] là đủ. Phải sort tăng dần theo B[i] và tăng dần theo chỉ số i.
• Bỏ qua việc gán giá trị giảm dần (N, N-1...) mà gán tăng dần, dẫn sai lệch thứ tự từ điển.