--- tags: LQDOJ, Number Theory, Flows, Matchings, kazamahoang, SPyofgame --- LQDOJ - VIPSET === [https://lqdoj.edu.vn/problem/vipset](https://lqdoj.edu.vn/problem/vipset) ----- ###### Tags: `Number Theory`, `Flows`, `Matchings`, ----- ### Hướng dẫn Ta định nghĩa: - Một **chain** là một tập hợp các số sao cho **với mọi** cặp số, ta có thể so sánh chúng được với nhau. - Một **antichain** là một tập hợp các số sao cho **không tồn tại** hai số nào so sánh được với nhau. - Một **chain decomposition** là một cách chia dãy thành các **chain** không giao nhau. Theo định lý **[Dilworth](https://en.wikipedia.org/wiki/Dilworth%27s_theorem)**, kích thước lớn nhất của một **antichain** trong dãy là số lượng **chain** ít nhất trong một **chain decomposition**. Trong bài toán này, phép so sánh **(comparator)** được sử dụng là: $a < b$ $\Leftrightarrow$ $a\ |\ b$. Do đó, ta đưa bài toán về tìm **chain decomposition** chia dãy ra thành ít **chain** nhất. Nói cách khác, ta cần tìm cách chia dãy thành ít tập hợp nhất sao cho mỗi số đều thuộc **duy nhất** một tập hợp và các số trong cùng một tập hợp so sánh được với nhau. Trước hết, sắp xếp các phần tử của dãy theo thứ tự tăng dần. Ta biểu diễn đồ thị như nhau: - Coi mỗi số là một đỉnh trên đồ thị. - Đỉnh $u$ có cạnh nối trực tiếp đến đỉnh $v$ $(u < v)$ nếu $a_u\ |\ a_v$. Lúc này, ta được một **DAG** (đồ thị không chu trình có hướng), bài toàn trở thành tìm số đường ít nhất đi qua tất cả các đỉnh của đồ thị. Đối với những bạn yêu thích `Flows` hay `Max Matching` thì đây là một bài toán cơ bản. Dù vậy, để đảm bảo tính đúng đắn, người viết editorial sẽ chứng minh ở cuối bài. Anyway, ta có thể làm như sau: - Ta xây dựng đồ thị hai phía. Gọi đỉnh bên trái là $u$, đỉnh bên phải tương ứng là $u'$ - Ta xây dựng đồ thị hai phía. Với mỗi đỉnh $u$, ta nối cạnh sang $v'$ nếu có cạnh nối trực tiếp từ $u$ đến $v$ trên **DAG**, hay $a_u\ |\ a_v$. - Trên đồ thị hai phía, ta tìm cặp ghép cực đại. Gọi $X$ là cặp ghép cực đại tìm được. Kết quả là $n - X$ ($n$ là kích thước của dãy). - Để tìm cặp ghép cực đại trên đồ thị hai phía, ta có thể dùng thêm đỉnh giả và tìm cặp ghép cực đại. Ngoài ra, với giới hạn $n \leq 300$, ta có thể dùng **[Kuhn's Algorithm](https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html)**. ----- ### Độ phức tạp Biểu diễn **DAG** chỉ là bước minh hoạ. Tất cả những thứ ta cần làm là áp dụng thuật toán **Kuhn**. Người ta đã chứng minh được rằng, **Kuhn's Algorithm** chạy trong độ phức tạp $O(n\times m)$. Tuy nhiên, thực tế thuật toán này chạy rất nhanh trên đồ thị hai phía ngẫu nhiên. Ta còn có thể cải tiến thêm bằng cách chọn ngẫu nhiên thứ tự match. Ngoài ra, bước tạo đồ thị hai phía mất thời gian $O(n^2)$ Vậy tổng độ phức tạp là $O(n^3)$ ----- ### Code > **Time:** $O(n)$ > **Space:** $O(n)$ ```cpp= ... ```