Editorial for Tiệc Halloween

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Có thể giải quyết mỗi truy vấn bằng cách trả lời câu hỏi sau: "Với $i$ ~i~ cạnh đầu tiên của đồ thị, số lượng đỉnh nhiều nhất có thể thăm là bao nhiêu ?"

Để trả lời câu hỏi trên, có thể sử dụng cấu trúc Disjoint-Set Union để xử lý. Với truy vấn thứ $j$ ~j~, lần lượt thêm các cạnh $i$ ~i~ ( $1 \le i \le N$ ~1 \le i \le N~) vào đồ thị, với mỗi cạnh $i$ ~i~ được thêm, đếm số lượng đỉnh nhiều nhất có thể thăm được, nếu số lượng lớn hơn hoặc bằng $Z_j$ ~Z_j~ thì giá trị $i$ ~i~ là đáp án của truy vấn. Thời gian xử lý của mỗi truy vấn tối đa là $O((N+M).log(M))$ ~O((N+M).log(M))~, độ phức tạp với $Q$ ~Q~ truy vấn là $O(Q.(N+M).log(M))$ ~O(Q.(N+M).log(M))~.

Nhận thấy rằng, khi tiến hành xây dựng cấu trúc Disjoint-Set Union cho các truy vấn, thao tác "thêm cạnh thứ $1$ ~1~, thêm cạnh thứ $2$ ~2~,..., thêm cạnh thứ $i$ ~i~" được lặp lại nhiều lần. Vì vậy, có thể sử dụng phương pháp Tìm kiến nhị phân song song (Parellel Binary Search) trên tất cả các truy vấn và kết hợp kĩ thuật Roll Back để giải quyết bài toán với độ phức tạp tốt hơn:

parallel_binary_search(L, R, candidates): // Đáp án của các truy vấn trong tập candidates đều nằm trong khoảng [L,R]
    if L == R:
        for query in candidates:
            answer[query] = L // Gán giá trị đáp án của các truy vấn trong tập candidates bằng L
        return
    mid = (L + R) / 2
    rollback(mid) // Roll Back cấu trúc về thời điểm trước khi thêm cạnh mid + 1
    left, right = split(candidates) // Chia candidates thành hai tập: left (đã hoàn thành) và right (chưa hoàn thành)
    parallel_binary_search(L, mid, left)
    addEdge(mid + 1, R) // Thêm các cạnh từ mid + 1 đến R vào cấu trúc
    parallel_binary_search(mid + 1, R, right)

Độ phức tạp: $O((N+M+Q).log(M).log(Q))$ ~O((N+M+Q).log(M).log(Q))~

Editorial for Tiệc Halloween

Comments