Hiểu bài toán

Xác định số cách John và Brus có thể mua hai vé ngồi cạnh nhau (ghế bên cạnh) trong cùng một hàng. Rạp có n hàng, mỗi hàng m ghế. Khi nhập, có k ghế đã bị chiếm chỗ (tọa độ (hàng, ghế)). Hai người có thể chọn bất kỳ hai ghế trống liền kề nhau (ghế i và i+1) trong cùng một hàng. Vì hai người là không phân biệt, mỗi cặp ghế trống liền kề chỉ tính là 1 cách. Với các hàng không có ghế nào bị chiếm, số cách trên một hàng là (m-1) (các cặp 1-2, 2-3, ..., m-1-m). Với hàng có ghế bị chiếm, cần đếm các đoạn ghế trống liên tiếp có độ dài >= 2 và cộng dồn.

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

Cách Hash Map

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m;
    int k;
    cin >> n >> m >> k;
    map<int, vector<int>> occ;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        occ[r].push_back(c);
    }
    long long ans = (n - (long long)occ.size()) * (m - 1);
    for (auto &p : occ) {
        auto &v = p.second;
        sort(v.begin(), v.end());
        long long prev = 0;
        for (int c : v) {
            long long len = c - prev - 1; // gap length
            if (len >= 2) ans += len - 1;
            prev = c;
        }
        long long len = m - prev;
        if (len >= 2) ans += len - 1;
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(k log k) (do sort các hàng)
• Space Complexity: O(k)

Sử dụng map để lưu các ghế đã chiếm theo từng hàng. Với hàng không có ghế chiếm, cách tính là (m-1). Với hàng có ghế chiếm, ta sắp xếp các cột bị chiếm, sau đó duyệt để tính độ dài các đoạn ghế trống giữa các ghế chiếm và đoạn cuối hàng. Nếu đoạn trống có độ dài L >= 2 thì có L-1 cách đặt vé. Tổng thời gian phụ thuộc vào số hàng có ghế chiếm (<= k) và sort (O(k log k)).

Cách Sort by Row then Column

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m;
    int k;
    cin >> n >> m >> k;
    vector<pair<int, int>> seats(k);
    for (int i = 0; i < k; i++) {
        cin >> seats[i].first >> seats[i].second;
    }
    sort(seats.begin(), seats.end());
    long long ans = n * (m - 1);
    int i = 0;
    while (i < k) {
        int row = seats[i].first;
        vector<int> cols;
        while (i < k && seats[i].first == row) {
            cols.push_back(seats[i].second);
            i++;
        }
        sort(cols.begin(), cols.end());
        long long prev = 0;
        for (int c : cols) {
            long long len = c - prev - 1;
            if (len >= 2) ans -= (len - 1);
            prev = c;
        }
        long long len = m - prev;
        if (len >= 2) ans -= (len - 1);
    }
    cout << ans << endl;
    return 0;
}

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

Phương pháp này tính tổng số cách có thể nếu không có ghế nào chiếm, sau đó trừ đi các cách không thể dùng do ghế chiếm. Ban đầu tổng là n*(m-1). Sau đó sort tất cả ghế đang chiếm theo hàng và cột. Duyệt qua từng hàng đang chiếm, sort các cột trong hàng đó, sau đó tính các đoạn trống và trừ đi (len-1) nếu len >= 2. Cách này cũng hiệu quả và không cần map.

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

Bài học kinh nghiệm

• Với một hàng hoàn toàn trống, số cách luôn là m-1.
• Với một hàng có ghế chiếm, ta chỉ cần đếm các đoạn ghế trống liên tiếp có độ dài >= 2. Số cách trong một đoạn trống độ dài L là L-1.
• Do n, m có thể lên tới 10^9 trong khi k rất nhỏ (<= 50), ta không thể duyệt qua từng hàng mà chỉ cần xử lý các hàng có ghế chiếm.

Lỗi thường gặp

• Quên sort cột trước khi tính toán trong cùng một hàng.
• Sử dụng int để lưu trữ kết quả trung gian có thể gây tràn số vì n và m lên tới 10^9 (kết quả có thể ~ 10^18), cần dùng long long.
• Xử lý sai đoạn trống ở đầu và cuối hàng (ghép với rào cột 0 và m+1).
• Đếm lặp các cách do không phân biệt John và Brus (cần đảm bảo mỗi cặp ghế cạnh nhau chỉ tính 1 lần).