Editorial for Làng Ma Sói
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 →SAMEkhimau[A] == mau[B], ngược lạiDIFF. 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\) choSAME, \(1\) choDIFF): 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