\(\Huge \text{🌱 Tin học trẻ 2021 - Vòng Khu vực - Bảng C - Thi đấu cầu lông}\)

📌 Tags: Greedy, Data Structure, Sorting
👤 Writer: @SPyofgame
👥 Contributor: @Editorial Slayers Team
📋 Content:

Hướng dẫn subtask 1-2-3

Với mỗi truy vấn, ta dựng đồ thị hai phía:

  • Các cạnh \(u - v\) có ý nghĩa là vận động viên \((a_u, b_u)\) khi ghép với vận động viên \((x_v, y_v)\) sẽ mang tới bàn thằng
  • Chỉ có cạnh nối \(u - v\) khi và chỉ khi \((a_u > x_v)\) và \((b_u > y_v)\), những trường hợp khác không có cạnh nối tới
  • Với mỗi giá trị \(u\) của độ thị này, chỉ được bắt cặp với một giá trị \(v\) duy nhất của đồ thị còn lại

Kết quả bài toán là số cặp ghép tối đa có thể tạo được trên đồ thị hai phía kể trên

Để tìm số cặp ghép cực đại trên đồ thị hai phía ta có thể có thể dùng thuật toán Kuhn-Munkres hoặc Hopcroft-Karp-Karzanov

Tất nhiên ta có thể chuyển đồ thị hai phía về dạng luồng và sử dụng thuật toán Ford-Fulkerson, Edmonds-Karp, Dinic, Push-relabel

Hướng dẫn subtask 4

Với mỗi truy vấn, ta giải như sau:

Không mất tính tổng quát ta sắp xếp các các vận động viên tăng dần

  • Các cặp \((a_u, b_u)\) sắp xếp theo \(a_u\) tăng dần
  • Các cặp \((x_v, y_v)\) sắp xếp theo \(x_v\) tăng dần

Gọi tập ứng cử viên \(S(u)\) là tập vào thời điểm \(u\) có các giá trị \(y_v\) mà tồn tại cặp \((x_v, y_v)\) thỏa mãn \((x_v < a_u)\), và chỉ những đỉnh \(v\) này thì \(u\) mới bắt cặp được

  • Chứng minh: Khi có tập \(S\), điều kiện \(x_v < a_u\) luôn thỏa nên ta chỉ xét các cạnh \(y_v < b_u\) để bắt cặp
  • Ứng dụng: Khi mình bắt cặp \(u - v\) thì mình cũng xóa phần tử đó ra khỏi tập \(S\) và duyệt tới \(u\) tiếp theo, cách chọn này sẽ không làm bị trùng giá trị với các cách chọn khác

Từ định nghĩa của \(S(u)\) thì với mọi \(u \leq u'\) ta có \(S(u) \subseteq S(u')\)

  • Chứng minh: Nếu tồn tại một phần tử \(y_v\) sao cho tồn tại cặp \((x_v, y_v)\) thỏa mãn \(x_v \geq a_{u_0}\) và \(x_v < a_u\) thì vô lí vì \(x_v < a_u \leq a_{u_0}\) (tính chất dãy sắp xếp)
  • Ứng dụng: Nếu chọn được một tập các giá trị \(y_v\) lấy được từ \(S(u)\) thì tồn tại cách thay thế giá trị \(y_v\) với một giá trị nhỏ hơn trong \(S(u)\) mà vẫn thỏa điều kiện ghép cặp

Từ hai tính ứng dụng trên, nhận xét rằng khi có tập \(T\) là các cạnh \(u-v\) được bắt cặp, nếu ta luôn bắt cặp giá trị \(y_v\) lớn nhất chưa được chọn cho mỗi \(u\) thì luôn đảm bảo là cho ra kết quả không tệ hơn mọi cách bắt cặp khác

  • Tính tối ưu: \(T\) luôn đảm bảo rằng sẽ không có tập \(S\) thỏa mãn nào khác mà có thể thay đổi các giá trị được chọn thành một số nhỏ hơn để mà \(S\) trở thành \(T\) được cả
  • Tính độc nhất: Vì nếu tồn tại một cách bắt cặp tối ưu hơn hẳn tập \(T\), thì cũng tồn tại cách để thay giá trị đó thành một giá trị nhỏ hơn sao cho các số được trọn trở thành \(T\), nhưng điều này vì vô lí như đã nói ở trên

Vậy, thuật toán tham lam của ta như sau:

  • Sau khi sắp xếp, ta duyệt qua các phần tử \(u\) đồng thời lấy thêm các phần tử \(y_v < a_u\) chưa xét ở tập \(S(u - 1)\) thêm vào tập \(S(u)\)
  • Sắp xếp tập \(S(u)\) và nếu tồn tại một giá trị \(y_v < b_u\) trong \(S(u)\) thì ta xóa \(y_v\) khỏi \(S(u)\) và tăng kết quả lên \(1\)

Để thêm bớt và tìm kiếm đủ nhanh cho một tập các giá trị có thể trùng nhau \(S(u)\), ta có thể sài các cấu trúc dữ liệu dạng cây:

  • Như trong ngôn ngữ C++ có std::multiset còn không bạn có thể dùng trie vì có hằng số nhỏ và code dễ
  • Các cấu trúc dữ liệu khác như Segment Tree với nén số, Dynamic Segment Tree, std::map, C++ ordered_set có vẻ như không đủ nhanh để qua time limit

Độ phức tạp:

  • Thời gian: \(O(n \log n)\) cho mỗi truy vấn, tổng cộng là \(O(q \times n \log n)\)
  • Bộ nhớ: \(O(n)\) cho nhập xuất và cây (nếu là cây trie thì khoảng \(O(n \times \log_2 x)\))

Code

General Time: \(O(q \times n \log n)\)
Query Time: \(O(n \log n)\)
Space: \(O(n)\)
Algo: Greedy, Data Structure, Sorting

SPyofgame multiset Implementation 



































































#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

const int LIM = 1e5 + 15;

int NumEarth, NumGamer, NumAlien, NumQuery;
pair<int, int> Earth[LIM]; /// Earth player
pair<int, int> Gamer[LIM]; /// All Z planet players
pair<int, int> Alien[LIM]; /// Few Z planet players that in each query
void input()
{
    cin >> NumEarth >> NumGamer >> NumQuery;
    for (int idx = 1; idx <= NumEarth; ++idx) cin >> Earth[idx].first;
    for (int idx = 1; idx <= NumEarth; ++idx) cin >> Earth[idx].second;
    for (int idx = 1; idx <= NumGamer; ++idx) cin >> Gamer[idx].first;
    for (int idx = 1; idx <= NumGamer; ++idx) cin >> Gamer[idx].second;
    sort(Earth + 1, Earth + NumEarth + 1); /// Sort these players
}

int query()
{
    int sft;
    cin >> sft;

    /// We find the set of player to play in this query
    NumAlien = NumEarth;
    for (int idx = 1; idx <= NumAlien; ++idx) Alien[idx] = Gamer[idx + sft - 1];
    
    /// Let also sort it
    sort(Alien + 1, Alien + NumAlien + 1);

    int result = 0;
    multiset<int> Candidate; /// Out candidate list S(u)
    for (int idx = 1, pos = 1; idx <= NumEarth; ++idx) /// For each u
    {
        /// Such $y_v$ satisfied exist such pair $(x_v, y_v)$ that $x_v < a_u$
        /// We only take such $y_v$ that not belong to $S(u - 1)$
        for (; pos <= NumAlien && Alien[pos].first < Earth[idx].first; ++pos)
            Candidate.insert(Alien[pos].second); /// Add $y_v$ to $S(u)$

        /// If there exist at least one solution
        if (Candidate.size() && *Candidate.begin() < Earth[idx].second)
        {
            /// Erase this $y_v$ out of $S(u)$
            Candidate.erase(--Candidate.lower_bound(Earth[idx].second));
            
            /// Increase the result
            ++result;
        }
    }

    return result;
}

int main()
{
    // file("Test");
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    input();
    while (NumQuery-->0) cout << query() << "\n";
    return 0;
}

Bonus

Bạn có thể giải truy vấn nhanh hơn \(O(n)\) khi \(q\) lớn hơn và \(n\) đủ nhỏ không ?

Select a repo