Hướng dẫn giải của Mức độ hài lòng


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hohoanghai5042011, lephuochauhungvuong, asenen_kiet

Editorial for bridges: Mức độ hài lòng

Hiểu bài toán

Bài toán yêu cầu tính tổng số cặp cầu giao nhau. Mỗi cầu nối từ điểm (0, u) ở bờ trái đến (1, v) ở bờ phải. Hai cầu (u1, v1) và (u2, v2) giao nhau nếu và chỉ nếu:

  1. u1 < u2 và v1 > v2 (một cầu nằm bên dưới và bên trên cầu kia tương ứng ở hai bờ).
  2. Hoặc u1 > u2 và v1 < v2 (trường hợp đối xứng). Điều này tương đương với việc đếm số cặp chỉ số (i, j) với i < j sao cho ui và uj có thứ tự ngược với vi và vj. Nói cách khác, chúng ta cần đếm số cặp nghịch thế trong dãy v sau khi đã sắp xếp các cầu theo thứ tự tăng dần của u. Giả sử sau khi sắp xếp theo u, ta có dãy v: v1, v2, ..., vn. Chúng ta cần đếm số cặp (i, j) với i < j và vi > v_j.

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

Cách Quy hoạch động (TLE)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> bridges(n);
    for (int i = 0; i < n; ++i) {
        cin >> bridges[i].first >> bridges[i].second;
    }
    // Sap xep theo toa do ben trai (u)
    sort(bridges.begin(), bridges.end());

    long long ans = 0;
    // Su dung quy hoach dong O(n^2) de dem so nghich the
    // dp[i] la so luong phan tu lon hon v[i] o ben phai
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (bridges[i].second > bridges[j].second) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n)

Cách tiếp cận này sắp xếp các cầu theo tọa độ u (bờ trái) tăng dần. Sau đó, với mỗi cặp cầu (i, j) mà i < j, ta kiểm tra xem vi có lớn hơn vj hay không. Nếu có, chúng giao nhau. Do giới hạn N <= 10^5, độ phức tạp O(n^2) sẽ bị quá thời gian (Time Limit Exceeded).

Cách Fenwick Tree (BIT)
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct Fenwick {
    int n;
    vector<int64> bit;
    Fenwick(int n=0): n(n), bit(n+1,0) {}
    void add(int idx, int64 val){
        for(; idx<=n; idx += idx & -idx) bit[idx] += val;
    }
    int64 sum(int idx){
        int64 r = 0;
        for(; idx>0; idx -= idx & -idx) r += bit[idx];
        return r;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if(!(cin >> N)) return 0;
    vector<pair<long long,long long>> a(N);
    for(int i=0;i<N;i++){
        long long u,v;
        cin >> u >> v;
        a[i] = {u,v};
    }

    // Sap xep theo u
    sort(a.begin(), a.end());

    // Coordinate compression for v
    vector<long long> vals;
    vals.reserve(N);
    for(auto &p: a) vals.push_back(p.second);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    Fenwick bit(vals.size());
    int64 ans = 0;
    for(int i=0;i<N;i++){
        long long v = a[i].second;
        // Tim chi so trong mang da compress
        int idx = lower_bound(vals.begin(), vals.end(), v) - vals.begin() + 1;
        // Dem so luong phan tu da them vao ma co v > v hien tai
        // Tong so phan tu da them la i
        // So luong phan tu co v <= v hien tai la bit.sum(idx)
        // Vay so luong phan tu co v > v hien tai la i - bit.sum(idx)
        ans += i - bit.sum(idx);
        bit.add(idx, 1);
    }
    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Đây là giải thuật tối ưu để đếm số cặp nghịch thế.

  1. Sắp xếp các cầu theo tọa độ u tăng dần.
  2. Duyệt qua các cầu theo thứ tự đã sắp xếp. Với mỗi cầu hiện tại:
    • Cần đếm xem trong số các cầu đã duyệt qua trước đó, có bao nhiêu cầu có tọa độ v lớn hơn v của cầu hiện tại (vì u của chúng nhỏ hơn u hiện tại do đã sắp xếp).
    • Ta sử dụng Fenwick Tree (BIT) để lưu trữ các giá trị v của các cầu đã duyệt.
    • Do v có thể lên tới 10^9, ta cần nén tọa độ (coordinate compression) các giá trị v về khoảng [1, N].
    • Truy vấn BIT để lấy tổng số lượng các cầu có v <= v hiện tại. Trừ đi số lượng cầu đã duyệt (i) ta được số lượng cầu có v > v hiện tại.
    • Cộng kết quả vào ans và cập nhật BIT. Độ phức tạp: O(N log N) do sắp xếp và thao tác BIT.
Cách Merge Sort (Divide and Conquer)
#include <bits/stdc++.h>
using namespace std;

int n;
vector<pair<int,int>> a;
vector<int> b;

long long c = 0;

// Ham dem so nghich the trong mang b
void f(vector<int>& v, int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    f(v, l, m);
    f(v, m+1, r);
    vector<int> t;
    int i = l, j = m+1;
    while (i <= m && j <= r) {
        if (v[i] <= v[j]) t.push_back(v[i++]);
        else {
            t.push_back(v[j++]);
            // Neu v[i] > v[j] va i o ben trai (da sap xep), 
            // thi tat ca phan tu tu i den m deu lon hon v[j]
            c += m - i + 1;
        }
    }
    while (i <= m) t.push_back(v[i++]);
    while (j <= r) t.push_back(v[j++]);
    for (i = l; i <= r; i++) v[i] = t[i-l];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    // Sap xep theo u
    sort(a.begin(), a.end());
    b.resize(n);
    for (int i = 0; i < n; i++) b[i] = a[i].second;
    // Dem nghich the tren mang v
    f(b, 0, n-1);
    cout << c;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Giải thuật này cũng dựa trên việc đếm số cặp nghịch thế.

  1. Sắp xếp các cầu theo u.
  2. Trích xuất dãy v thành một mảng.
  3. Sử dụng thuật toán Merge Sort để đếm số cặp nghịch thế. Trong quá trình gộp (merge) hai nửa mảng đã sắp xếp:
    • Nếu phần tử ở nửa bên phải nhỏ hơn phần tử ở nửa bên trái, nó sẽ tạo ra một cặp nghịch thế với tất cả các phần tử còn lại trong nửa bên trái (vì mảng con bên trái đã được sắp xếp).
    • Ta cộng dồn số lượng này vào biến toàn cục. Độ phức tạp: O(N log N) do chia để trị của Merge Sort.

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

Cách tiếp cận Time Space Tên
1 O(n^2) O(n) Quy hoạch động (TLE)
2 O(N log N) O(N) Fenwick Tree (BIT)
3 O(N log N) O(N) Merge Sort (Divide and Conquer)

Bài học kinh nghiệm

  • Vấn đề giao nhau của các cầu có thể chuyển hóa thành bài toán đếm số cặp nghịch thế (inversions) trong dãy số.
  • Phải sắp xếp các cầu theo một trục (ví dụ trục u) trước khi xử lý để giảm bài toán về việc đếm nghịch thế trong trục còn lại (trục v).
  • Fenwick Tree (Binary Indexed Tree) là công cụ hiệu quả để đếm số phần tử trong một dãy số nằm trong một khoảng giá trị nhất định, rất phù hợp cho bài toán này sau khi đã nén tọa độ.

Lỗi thường gặp

  • Quên sắp xếp các cầu trước khi xử lý, dẫn đến kết quả sai.
  • Không nén tọa độ (coordinate compression) khi sử dụng Fenwick Tree, gây tràn bộ nhớ hoặc lỗi do tọa độ quá lớn.
  • Sử dụng thuật toán O(n^2) dẫn đến quá thời gian chạy.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.