Editorial for Làng Ma Sói


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: Nghaiz

Lời giải: Làng Ma Sói

Chủ đề: dict, list, hàm, vòng lặp for, chuỗi (tên người), suy luận logic

Tóm tắt đề

Có hai phe. Lần lượt nhận \(q \leq 10^5\) lời khai "cùng phe" / "khác phe" và câu hỏi. Với mỗi lời khai cho biết nó mâu thuẫn (LIE), đã suy ra được (KNOWN) hay mới (NEW); với mỗi câu hỏi cho biết SAME / DIFF / UNKNOWN.

Bước 1: hiểu "suy ra được" nghĩa là gì

Vẽ mỗi người là một điểm, mỗi lời khai đã tin là một đường nối hai người, trên đường nối ghi \(0\) (cùng phe) hoặc \(1\) (khác phe).

  • Hai người không được nối với nhau (trực tiếp hay gián tiếp) → không có thông tin gì về quan hệ của họ → UNKNOWN.
  • Hai người được nối qua một dãy người trung gian → quan hệ của họ hoàn toàn xác định: đi dọc đường nối, mỗi lần gặp "khác phe" thì đổi phe một lần. Số lần đổi phe chẵn → cùng phe, lẻ → khác phe. Đây chính là "kẻ thù của kẻ thù là bạn".

Vì Mèo Mun chỉ tin những lời khai không mâu thuẫn, mọi dãy nối giữa hai người luôn cho cùng một kết quả.

Bước 2: nhóm người và "màu" tương đối

Ta chia mọi người thành các nhóm: hai người cùng nhóm khi được nối với nhau. Trong mỗi nhóm, chọn tùy ý phe của một người làm mốc, khi đó phe của mọi người khác trong nhóm đều xác định. Ta lưu cho mỗi người:

  • nhom[ten]: mã nhóm của người đó;
  • mau[ten]: \(0\) nếu cùng phe với người làm mốc, \(1\) nếu khác phe;
  • thanh_vien[ma_nhom]: danh sách người trong nhóm.

Khi đó:

  • Câu hỏi ASK A B: nếu \(A = B\) → SAME. Nếu hai người cùng nhóm → SAME khi mau[A] == mau[B], ngược lại DIFF. Khác nhóm (hoặc chưa từng xuất hiện) → UNKNOWN.
  • Lời khai cùng nhóm: so sánh mau[A] ^ mau[B] với lời khai (\(0\) cho SAME, \(1\) cho DIFF): khớp → KNOWN, không khớp → LIE.
  • Lời khai khác nhóm → NEW, và phải gộp hai nhóm thành một.

Bước 3: gộp nhóm sao cho đủ nhanh

Gộp nhóm của \(B\) vào nhóm của \(A\) nghĩa là: với mỗi người \(x\) trong nhóm của \(B\), đổi nhom[x] thành mã nhóm của \(A\). Nếu cần (để thỏa lời khai mới), đảo luôn màu của cả nhóm \(B\): mau[x] ^= lat, với lat = mau[A] ^ mau[B] ^ (lời khai).

Cái bẫy: nếu lúc nào cũng chuyển nhóm của \(B\) sang nhóm của \(A\), một người có thể bị chuyển đi chuyển lại rất nhiều lần. Ví dụ dãy lời khai SAME x2 x1, SAME x3 x1, SAME x4 x1, ...: lần nào nhóm khổng lồ của x1 cũng bị chuyển sang nhóm một người. Tổng cộng \(1 + 2 + \dots + q \approx 5 \cdot 10^9\) thao tác → TLE.

Mẹo: luôn chuyển nhóm NHỎ hơn sang nhóm LỚN hơn. Mỗi khi một người bị chuyển nhóm, nhóm mới của người đó lớn ít nhất gấp đôi nhóm cũ. Nhóm không thể lớn quá \(2 \cdot 10^5\) người, nên mỗi người chỉ bị chuyển tối đa khoảng \(\log_2(2 \cdot 10^5) \approx 18\) lần. Tổng số thao tác chỉ còn cỡ \(q \log q\).

if len(thanh_vien[ga]) < len(thanh_vien[gb]):
    a, b, ga, gb = b, a, gb, ga          # đổi vai để gb là nhóm nhỏ
lat = mau[a] ^ mau[b] ^ khac_phe
for ten in thanh_vien[gb]:
    nhom[ten] = ga
    mau[ten] ^= lat
thanh_vien[ga].extend(thanh_vien[gb])
del thanh_vien[gb]

Để ý phép hoán đổi bằng tuple a, b, ga, gb = b, a, gb, ga: một dòng thay cho bốn biến tạm.

Cách khác: Disjoint Set Union

Bạn nào đã biết cấu trúc DSU (Union-Find) có thể dùng DSU có lưu thêm "độ lệch chẵn lẻ" so với gốc. Khi đó cần nén đường đi và gộp theo kích thước, đồng thời viết hàm find bằng vòng lặp while chứ không đệ quy. Nếu viết find đệ quy mà không gộp theo kích thước, các lời khai SAME x1 x2, SAME x2 x3, ... sẽ tạo ra một "dây xích" dài \(10^5\), lần find đầu tiên trên dây xích đó gây RecursionError → IR.

Độ phức tạp

\(O(q \log q)\) thao tác với dict, mỗi thao tác trung bình \(O(1)\).

Code mẫu

import sys


def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])

    nhom = {}
    mau = {}
    thanh_vien = {}

    def them_nguoi(ten):
        if ten not in nhom:
            ma = len(nhom)
            nhom[ten] = ma
            mau[ten] = 0
            thanh_vien[ma] = [ten]

    kq = []
    for i in range(q):
        lenh, a, b = data[3 * i + 1], data[3 * i + 2], data[3 * i + 3]

        if lenh == b"ASK":
            if a == b:
                kq.append("SAME")
            elif a in nhom and b in nhom and nhom[a] == nhom[b]:
                kq.append("SAME" if mau[a] == mau[b] else "DIFF")
            else:
                kq.append("UNKNOWN")
            continue

        khac_phe = 1 if lenh == b"DIFF" else 0
        them_nguoi(a)
        them_nguoi(b)
        ga, gb = nhom[a], nhom[b]

        if ga == gb:
            kq.append("KNOWN" if (mau[a] ^ mau[b]) == khac_phe else "LIE")
            continue

        if len(thanh_vien[ga]) < len(thanh_vien[gb]):
            a, b, ga, gb = b, a, gb, ga
        lat = mau[a] ^ mau[b] ^ khac_phe
        for ten in thanh_vien[gb]:
            nhom[ten] = ga
            mau[ten] ^= lat
        thanh_vien[ga].extend(thanh_vien[gb])
        del thanh_vien[gb]
        kq.append("NEW")

    sys.stdout.write("\n".join(kq) + "\n")


main()

Comments

There are no comments at the moment.