Editorial for stpara: Cuộc diễu hành đường phố

Hiểu bài toán

Một đoàn xe gồm n xe có thứ tự từ 1 đến n cần diễu hành vào đường Chu Văn Thịnh theo thứ tự tăng dần. Hiện tại, chúng đang xếp lộn xộn trên đường Trường Chinh. Có một đoạn đường Điện Biên cho phép các xe quay đầu (tức là có thể dùng như một bãi đỗ xe tạm thời/stack). Các xe trên đường chính không được phép vượt nhau hay đi lùi.

Bài toán yêu cầu kiểm tra xem với trật tự ban đầu given, ta có thể dùng đường Điện Biên (với thao tác push/pop theo quy tắc stack) để đưa các xe ra đường Chu Văn Thịnh theo thứ tự 1, 2, ..., n hay không.

Quy trình mô phỏng:

1. Xe đến từ đường Trường Chinh (input order).
2. Ta có thể cho xe vào đường Điện Biên (đẩy vào stack).
3. Ta có thể cho xe từ đường Trường Chinh hoặc từ đường Điện Biên ra đường Chu Văn Thịnh (đầu ra). Điều kiện: Xe chỉ được ra đường Chu Văn Thịnh khi nó là xe tiếp theo cần xuất hiện (bắt đầu từ 1).

Nói cách khác, ta cần kiểm tra xem trật tự input có phải là một valid stack permutation của trật tự output (1..n) hay không.

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

Cách Mô phỏng Dùng Stack (Simulate)

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

int stack[100005];
int top = -1;

void push(int n) {
    stack[++top] = n;
}

int pop() {
    if (top == -1) return -1;
    return stack[top--];
}

int main() {
    int n;
    while (scanf("%d", &n) && n != 0) {
        int *s = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            scanf("%d", &s[i]);
        }

        int k = 1; // Xe cần tìm tiếp theo (1, 2, ...)
        top = -1;
        int i = 0;

        while (i < n) {
            // Nếu xe hiện tại là xe cần thiết, cho ra luôn
            if (s[i] == k) {
                k++;
                i++;
            } 
            // Nếu không, kiểm tra stack: có phải xe ở đỉnh stack là xe cần không?
            else if (top != -1 && stack[top] == k) {
                pop();
                k++;
            } 
            // Nếu không phải, đẩy xe hiện tại vào stack
            else {
                push(s[i++]);
            }
        }

        // Đã duyệt hết input, kiểm tra stack còn lại
        while (top != -1 && stack[top] == k) {
            pop();
            k++;
        }

        if (top == -1) printf("yes\n");
        else printf("no\n");

        free(s);
    }
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất, mô phỏng chính xác quá trình xe di chuyển theo luật.

• Duyệt qua danh sách xe đầu vào.
• Nếu xe đầu vào đúng là xe cần (k), ta cho nó đi luôn.
• Nếu không, ta phải đẩy nó vào stack (đường Điện Biên).
• Sau mỗi lần đẩy hoặc kiểm tra xe đầu vào, ta kiểm tra stack. Nếu đỉnh stack chứa đúng xe cần (k), ta cho xe đó đi (pop).
• Nếu duyệt hết xe đầu vào mà stack rỗng, nghĩa là đã sắp xếp thành công.

Cách Mô phỏng Cải tiến (Optimized Simulation)

#include <stdio.h>

int stack[100005];

void check(int a[], int n) {
    int in = 0;  // Chỉ số top của stack (dùng mảng 0-indexed)
    int count = 1; // Xe cần tìm

    for (int i = 0; i < n; i++) {
        // Nếu đỉnh stack là xe cần, pop ra
        while (in > 0 && stack[in - 1] == count) {
            in--;
            count++;
        }

        if (a[i] == count) {
            count++;
        } else {
            stack[in++] = a[i];
        }
    }

    // Kiểm tra nốt các xe còn lại trong stack
    while (in > 0 && stack[in - 1] == count) {
        in--;
        count++;
    }

    if (in == 0) printf("yes");
    else printf("no");
}

int main() {
    int n;
    while (scanf("%d", &n) && n != 0) {
        int a[100005];
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        check(a, n);
        printf("\n");
    }
    return 0;
}

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

Phiên bản này có logic tương tự Solution 1 nhưng tối ưu hơn một chút về cách xử lý:

• Sử dụng biến in để quản lý độ cao của stack.
• Trong vòng lặp duyệt input, ưu tiên pop các xe từ stack ra nếu chúng đúng bằng xe cần (count) trước khi xử lý xe mới từ input. Điều này đảm bảo ta luôn ưu tiên lấy xe từ stack thay vì giữ lại.
• Nếu xe đầu vào không phải là xe cần và không thể pop từ stack, ta đẩy nó vào stack.
• Cuối cùng chỉ việc kiểm tra xem stack có rỗng không.

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

Bài học kinh nghiệm

• Bài toán là một dạng bài toán về Stack Permutations. Một dãy đầu vào là hợp lệ nếu nó có thể được sinh ra bằng các thao tác push/pop trên một stack với dãy đầu ra 1, 2, ..., n.
• Luôn ưu tiên xuất xe (pop) từ đường Điện Biên (stack) nếu xe đó là xe tiếp theo cần thiết, trước khi quyết định đưa xe mới vào stack.

Lỗi thường gặp

• Quên kiểm tra stack sau khi đã duyệt hết input: Có thể các xe cuối cùng vẫn còn nằm trong stack và cần được xuất ra.
• Lỗi thứ tự so sánh: Phải so sánh xe hiện tại với xe cần thiết (count) chứ không phải so sánh lung tung.
• Xử lý input nhiều test case: Cần reset biến stack (top/in) và biến đếm về lại trạng thái ban đầu cho mỗi test case.