Editorial for coloring: Tô màu 4

Hiểu bài toán

Bài toán yêu cầu tính diện tích phần còn lại của một hình chữ nhật lớn (kích thước W x H, bắt đầu từ (0,0)) sau khi đã tô màu các vùng dựa trên N điểm và các hướng tô màu tương ứng. Với mỗi điểm (xi, yi) và mã a_i:

• ai = 1: Tô màu bên trái điểm (x < xi).
• ai = 2: Tô màu bên phải điểm (x > xi).
• ai = 3: Tô màu bên dưới điểm (y < yi).
• ai = 4: Tô màu bên trên điểm (y > yi). Vùng chưa tô màu là phần giao nhau của các miền 'không bị tô'.

Ví dụ: Nếu có nhiều điều kiện 'tô bên trái', chỉ vùng có tọa độ x lớn nhất trong các ranh giới đó mới còn lại (vì các vùng x nhỏ hơn đã bị tô hết). Tương tự cho các hướng khác.

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

Cách Mô phỏng ma trận (Brute Force)

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

void paintRect(int x, int y, int a, vector<vector<int>> &rect) {
    switch (a) {
        case 1:
            for (int i = 0; i < rect.size(); i++) {
                for (int j = 0; j < x; j++) {
                    rect[i][j] = 1;
                }
            }
            break;
        case 2:
            for (int i = 0; i < rect.size(); i++) {
                for (int j = x; j < rect[i].size(); j++) {
                    rect[i][j] = 1;
                }
            }
            break;
        case 3:
            for (int i = 0; i < y; i++) {
                for (int j = 0; j < rect[i].size(); j++) {
                    rect[i][j] = 1;
                }
            }
            break;
        case 4:
            for (int i = y; i < rect.size(); i++) {
                for (int j = 0; j < rect[i].size(); j++) {
                    rect[i][j] = 1;
                }
            }
            break;
    }
}

int main() {
    int w, h, n;
    cin >> w >> h >> n;
    vector<vector<int>> rect(h, vector<int>(w, 0));
    for (int i = 0; i < n; i++) {
        int x, y, a;
        cin >> x >> y >> a;
        paintRect(x, y, a, rect);
    }
    int count = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (rect[i][j] == 0) count++;
        }
    }
    cout << count;
    return 0;
}

• Time Complexity: O(N * W * H)
• Space Complexity: O(W * H)

Cách tiếp cận này mô phỏng chính xác quá trình tô màu. Ta tạo một ma trận 2 chiều (W x H) đại diện cho hình chữ nhật. Ban đầu tất cả các ô đều trắng (0). Với mỗi lệnh tô màu, ta duyệt qua các ô tương ứng trong ma trận và đánh dấu chúng là đã tô (1). Cuối cùng, ta đếm số ô chưa bị đánh dấu.

Giới hạn của đề bài là W, H <= 100, nên kích thước ma trận tối đa là 10,000 ô. Với N <= 100, tổng số thao tác cập nhật là khoảng 100 * 10,000 = 1,000,000, hoàn toàn chấp nhận được về mặt thời gian.

Cách Tìm biên (Quy hoạch động)

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

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

    long long W, H;
    int N;
    cin >> W >> H >> N;

    long long left = 0, right = W, down = 0, up = H;

    for (int i = 0; i < N; i++) {
        long long x, y;
        int a;
        cin >> x >> y >> a;

        if (a == 1) left = max(left, x);
        else if (a == 2) right = min(right, x);
        else if (a == 3) down = max(down, y);
        else if (a == 4) up = min(up, y);
    }

    long long w = max(0LL, right - left);
    long long h = max(0LL, up - down);

    cout << w * h;
    return 0;
}

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

Đây là cách tiếp cận tối ưu. Thay vì mô phỏng từng ô, ta nhận thấy rằng vùng chưa tô màu luôn là một hình chữ nhật (hoặc rỗng). Vùng này được giới hạn bởi các đường biên:

• Bên trái: Lớn nhất các giá trị xi của các điểm có ai = 1 (vì tô bên trái xi, nên phần còn lại phải có x >= xi).
• Bên phải: Nhỏ nhất các giá trị xi của các điểm có ai = 2 (vì tô bên phải xi, nên phần còn lại phải có x <= xi).
• Bên dưới: Lớn nhất các giá trị yi của các điểm có ai = 3.
• Bên trên: Nhỏ nhất các giá trị yi của các điểm có ai = 4.

Ta chỉ cần duyệt qua N điểm một lần để cập nhật 4 biên này. Sau đó tính kích thước và nhân lên. Độ phức tạp O(N) rất nhanh.

Cách Tối ưu hóa mô phỏng (Lưu ý thứ tự)

// Tương tự Approach 1, nhưng có thể tối ưu nếu dùng mảng 1D hoặc vector<bool> 
// để tiết kiệm bộ nhớ, nhưng logic vẫn là O(N*W*H).

• Time Complexity: O(N * W * H)
• Space Complexity: O(W * H)

Cách này về cơ bản là Approach 1 nhưng có thể dùng các cấu trúc dữ liệu khác hoặc tối ưu vòng lặp, nhưng về bản chất độ phức tạp không đổi. Nó chỉ khác biệt nhỏ về mặt thực thi so với Brute Force.

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

Bài học kinh nghiệm

• Vùng chưa tô màu là hình chữ nhật và là phần giao nhau của các miền 'không bị tô'.
• Đối với mỗi hướng, chỉ có biên xa nhất (về phía không bị tô) mới quyết định hình dạng cuối cùng của vùng còn lại.
• Bài toán có thể biến về bài toán tìm min/max của các ranh giới thay vì mô phỏng chi tiết.

Lỗi thường gặp

• Lầm tưởng rằng các vùng tô có thể tạo ra hình dạng phức tạp không phải hình chữ nhật (trong khi thực tế giao của các nửa mặt phẳng vẫn là hình chữ nhật hoặc đa giác lồi, nhưng ở đây do điều kiện đặc biệt nên luôn là hình chữ nhật).
• Quên xử lý trường hợp các biên cắt nhau tạo ra diện tích âm (cần max(0, ...) khi tính kết quả).
• Sử dụng biến toàn cục hoặc mảng quá nhỏ so với giới hạn đề bài.