Editorial for mcake: Luộc bánh Chưng

Hiểu bài toán

Bài toán yêu cầu tính hai giá trị:

1. Theo dự kiến: Số ô nhiều nhất mà một lớp có thể nhận được nếu không có sự xung đột về vị trí. Đây đơn giản là độ dài lớn nhất của các đoạn [ai, bi] được cho.
2. Trên thực tế: Số ô nhiều nhất mà một lớp thực sự nhận được. Các lớp nhận địa điểm theo thứ tự từ 1 đến n. Nếu một lớp đến lượt và một ô trong đoạn [ai, bi] đã bị lớp trước đó chiếm giữ, lớp đó sẽ không nhận được ô đó.

Ví dụ:

• Lớp 1: [2, 4] -> Nhận 3 ô (2, 3, 4).
• Lớp 2: [7, 8] -> Nhận 2 ô (7, 8).
• Lớp 3: [6, 9] -> Các ô 6, 9 còn trống, ô 7, 8 đã bị chiếm -> Nhận 2 ô.

Kết quả: Dự kiến là 4 (từ [2,5]), thực tế là 3 (từ lớp 1).

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

Cách Mô phỏng trực tiếp (Simulation)

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n, L;
    scanf("%d %d", &n, &L);

    // Mảng đánh dấu các ô đã được chiếm
    bool occupied[1001] = {false}; 

    int max_expected = 0;
    int max_actual = 0;

    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);

        // Tính theo dự kiến (độ dài đoạn)
        int expected = b - a + 1;
        if (expected > max_expected) {
            max_expected = expected;
        }

        // Tính trên thực tế
        int actual = 0;
        for (int j = a; j <= b; j++) {
            if (!occupied[j]) {
                occupied[j] = true;
                actual++;
            }
        }

        if (actual > max_actual) {
            max_actual = actual;
        }
    }

    printf("%d %d", max_expected, max_actual);
    return 0;
}

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

Phương pháp này dùng mảng boolean occupied để lưu trạng thái của từng ô đất.

• Khởi tạo mảng occupied với giá trị false.
• Duyệt từng lớp một:
  • Tính độ dài đoạn hiên tại để cập nhật max_expected.
  • Duyệt qua từng ô trong đoạn [a, b]. Nếu ô chưa bị chiếm (occupied[j] == false), đánh dấu ô đó là true và tăng biến đếm actual.
  • Cập nhật max_actual.
• Ưu điểm: Dễ hiểu, dễ implement.
• Nhược điểm: Nếu L lớn (ví dụ 10^9), mảng không thể khai báo và duyệt bị quá thời gian. Tuy nhiên với giới hạn L ≤ 1000, phương pháp này hoàn toàn khả thi.

Cách Quét dải (Sweep Line)

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

// Hàm so sánh cho qsort
int cmp(const void *a, const void *b) {
    int *pa = *(int**)a;
    int *pb = *(int**)b;
    // Sắp xếp theo điểm bắt đầu tăng dần
    if (pa[0] != pb[0]) return pa[0] - pb[0];
    // Nếu bắt đầu bằng nhau, kết thúc tăng dần
    return pa[1] - pb[1];
}

int main() {
    int n, L;
    scanf("%d %d", &n, &L);

    // Lưu các đoạn vào mảng 2 chiều
    int **segments = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        segments[i] = (int*)malloc(2 * sizeof(int));
        scanf("%d %d", &segments[i][0], &segments[i][1]);
    }

    // Sắp xếp các đoạn theo thứ tự a tăng dần
    qsort(segments, n, sizeof(int*), cmp);

    int max_expected = 0;
    int max_actual = 0;
    int current_end = 0; // Biến lưu vị trí cuối cùng đã bị chiếm

    for (int i = 0; i < n; i++) {
        int a = segments[i][0];
        int b = segments[i][1];

        // Dự kiến
        int expected = b - a + 1;
        if (expected > max_expected) max_expected = expected;

        // Thực tế
        int actual = 0;
        // Nếu đoạn bắt đầu sau vị trí đã chiếm trước đó
        if (a > current_end) {
            actual = b - a + 1;
            current_end = b;
        } else {
            // Đoạn bị chồng lấp một phần hoặc toàn phần
            if (b > current_end) {
                actual = b - current_end;
                current_end = b;
            } else {
                actual = 0;
            }
        }

        if (actual > max_actual) max_actual = actual;
    }

    printf("%d %d", max_expected, max_actual);
    return 0;
}

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

Phương pháp này tối ưu hóa bằng cách sắp xếp các đoạn theo thứ tự.

1. Đọc và lưu các đoạn [a, b] vào mảng.
2. Sắp xếp các đoạn tăng dần theo điểm đầu a. Nếu điểm đầu bằng nhau, sắp xếp theo điểm cuối b.
3. Duyệt các đoạn đã sắp xếp:
   • Cập nhật max_expected dựa trên độ dài đoạn.
   • Duyệt thực tế: Giả sử các đoạn được xử lý theo thứ tự và chỉ bị chồng lấp bởi các đoạn có điểm đầu nhỏ hơn hoặc bằng.
   • Duyệt một đoạn bất kỳ:
     • Nếu a > current_end (vị trí cuối cùng bị chiếm bởi các đoạn trước): Đoạn này hoàn toàn mới, nhận toàn bộ b - a + 1 ô. Cập nhật current_end = b.
     • Nếu a <= current_end: Đoạn này bị chồng lấp. Số ô mới nhận được là b - current_end (nếu b > current_end), ngược lại là 0. Cập nhật current_end = max(current_end, b).

• Phương pháp này giả định rằng việc xử lý theo thứ tự sắp xếp sẽ tương đương với thứ tự xử lý thực tế. Tuy nhiên, bài toán quy định thứ tự xử lý là 1 -> n. Nếu các đoạn được cho không theo thứ tự a tăng dần, phương pháp sai.
• Lưu ý: Code mẫu ở trên chỉ đúng nếu thứ tự input được sắp xếp sẵn hoặc nếu ta dùng giải pháp khác.

Cách Tối ưu (Duyệt theo thứ tự cho trước)

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_L 1001

int main() {
    int n, L;
    scanf("%d %d", &n, &L);

    // Cải tiến: Dùng mảng bool hoặc int thay vì int arr[1001] để tối ưu
    // Sử dụng mảng đánh dấu
    int mark[MAX_L]; // 0 là trống, 1 là đã chiếm
    memset(mark, 0, sizeof(mark));

    int max_expected = 0;
    int max_actual = 0;

    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);

        // 1. Tính max theo dự kiến
        int len = b - a + 1;
        if (len > max_expected) max_expected = len;

        // 2. Tính max theo thực tế
        int current_actual = 0;
        for (int j = a; j <= b; j++) {
            if (mark[j] == 0) {
                mark[j] = 1;
                current_actual++;
            }
        }

        if (current_actual > max_actual) max_actual = current_actual;
    }

    printf("%d %d", max_expected, max_actual);
    return 0;
}

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

Đây là phiên bản sạch sẽ và chính xác nhất cho giới hạn đề bài (L ≤ 1000).

• Logic:
  • Khởi tạo mảng mark để ghi nhận ô đã được cấp phát.
  • Vòng lặp chính duyệt qua n lớp.
  • Trong mỗi lớp, tính độ dài đoạn [a, b] để update max_expected.
  • Duyệt từ a đến b, đếm số ô chưa được đánh dấu (mark[j] == 0), đánh dấu chúng và update max_actual.
• Đây là phương pháp trực tiếp và đảm bảo đúng thứ tự xử lý (1 đến n).

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

Bài học kinh nghiệm

• Phần 1 của output (Theo dự kiến) không phụ thuộc vào thứ tự hay sự chồng lấp. Nó chỉ là bài toán tìm độ dài lớn nhất của các đoạn cho trước.
• Phần 2 của output (Thực tế) đòi hỏi phải mô phỏng chính xác thứ tự xử lý và việc các ô bị chiếm giữ.
• Với ràng buộc n, L ≤ 1000, giải thuật mô phỏng O(n*L) (khoảng 1 triệu thao tác) là hoàn toàn chấp nhận được và là lựa chọn an toàn nhất.
• Giải thuật Sweep Line (Sắp xếp theo a) chỉ đúng nếu thứ tự xử lý của các lớp là ngẫu nhiên hoặc theo a. Vì đề bài quy định thứ tự xử lý là 1, 2, ..., n, ta không được sắp xếp lại các đoạn trước khi xử lý.

Lỗi thường gặp

• Lầm tưởng rằng Sweep Line (sắp xếp theo a) là tối ưu cho mọi trường hợp. Nếu input cho các đoạn [a, b] không theo thứ tự a tăng dần, Sweep Line sẽ cho kết quả sai cho phần 'Thực tế' vì nó vi phạm thứ tự xử lý.
• Quên cập nhật max_actual sau mỗi lớp. Biến đếm số ô thực tế của lớp hiện tại phải được reset về 0 sau mỗi lớp.
• Lỗi off-by-one: Tính độ dài đoạn phải là b - a + 1.