Phân tích

Biểu diễn đầu vào bằng đồ thị có một đỉnh mỗi tòa nhà, một cạnh có hướng mỗi cầu. Gọi \(G_i\) là đồ thị con gồm các cạnh bật sau \(i\) thao tác. Đồ thị vui khi mỗi đỉnh thuộc đúng một chu trình. Với mỗi \(i\), cần tìm cạnh \((v,w)\in G-G_i\) sao cho \(G_i\cup\{(v,w)\}\) vui.

Test Set 1

Đồ thị vui khi và chỉ khi bậc vào và bậc ra của mọi đỉnh đều bằng \(1\). Vì vậy cạnh cần thêm \((v,w)\) phải có \(\deg^+_{G_i}(v)=0\), \(\deg^-_{G_i}(w)=0\), và mọi bậc còn lại bằng \(1\). Ta kiểm tra các bậc để tìm ứng viên duy nhất \(v,w\); nếu cạnh \((v,w)\) tồn tại trong \(G\) thì đó là đáp án, còn thiếu ứng viên hoặc thiếu cạnh thì in X.

Duy trì bậc vào/ra. Khi bật cạnh \((v,w)\), tăng bậc ra \(v\), bậc vào \(w\); khi tắt thì giảm. Sau đó quét tuyến tính tìm ứng viên. Mỗi bước tốn \(O(B+S)\), tổng \(O(N(B+S))\).

Test Set 2

Đây là bản tối ưu của Test Set 1. Xét các đa tập đỉnh \(I_i,O_i\) biểu diễn các bậc vào/ra của \(G_i\). Với mỗi cạnh \(e\), gọi \(I'_e,O'_e\) là các đa tập mà \(I_i,O_i\) phải bằng để \(e\) là đáp án. Duy trì hash của \(I_i,O_i\) có thể cập nhật nhanh và một bảng ánh xạ cặp hash \((I'_e,O'_e)\) sang \(e\).

Tổng các giá trị ngẫu nhiên

Gán mỗi đỉnh \(v\) một số nguyên ngẫu nhiên \(x_v\) cố định trong bộ dữ liệu. Hash đa tập là tổng các \(x_v\), tính cả số lần lặp, modulo một số lớn. Có thể dùng bộ giá trị riêng cho hash vào và ra để tăng ngẫu nhiên. Đặt \(t=\sum_vx_v\); hash trạng thái thiếu đúng đầu mút của cạnh được suy ra bằng cách lấy \(t\) trừ giá trị đầu mút tương ứng.

Từ hash ở bước \(i\), cộng hoặc trừ tổng giá trị đầu/cuối của mọi cạnh bị thao tác để có bước \(i+1\). Tiền tính, với mỗi \(M\), mảng tổng trên \(i\) bội đầu tiên của \(M\) cho đầu và cuối cạnh. Tổng trên các bội thứ \(i\) tới \(j\) là hiệu hai tổng tiền tố.

Mảng của \(M\) dài \(\lfloor S/M\rfloor\) và

nên đủ nhanh. Khó chứng minh hình thức rằng tổng là hash tốt; biến thể sau cho xác suất va chạm rõ hơn.

XOR các giá trị ngẫu nhiên

Thay tổng bằng XOR, phần còn lại cài đặt tương tự. Vì XOR tự nghịch đảo, hai đa tập có cùng chẵn lẻ số lần xuất hiện của mọi đỉnh sẽ cùng hash. Khắc phục bằng cách lưu thêm tổng số cạnh của \(G_i\). Va chạm vẫn có thể xảy ra, nhưng trong trạng thái đích mọi số lần là \(0\) hoặc \(1\), nên đúng chẵn lẻ và đúng tổng đảm bảo cùng đa tập.

Tổng số cạnh cập nhật \(O(1)\) mỗi bước. Với XOR, mỗi bit kết quả độc lập. Do \(x_v\) ngẫu nhiên, xác suất một bit trùng giữa hai đa tập khác chẵn lẻ là \(1/2\); xác suất cả \(64\) bit tình cờ trùng là \(2^{-64}\), cực nhỏ.

Hash đa thức

Trong biến thể XOR, thực chất ta hash các tập đỉnh theo chẵn lẻ bậc. Hash đa thức vốn phù hợp cho tập, nên có thể dùng trực tiếp như cách thứ ba.

Hash đa thức tương đương biến thể tổng, ngoại trừ \(x_v\) là các lũy thừa của một số nguyên tố thay vì được chọn ngẫu nhiên. Lựa chọn ngẫu nhiên chống dữ liệu đối kháng tốt hơn và có tính phân bố đều tương tự; đây cũng là lập luận không hình thức giải thích vì sao tổng ngẫu nhiên là hash tốt cho bài.

Dựa trên phân tích chính thức của Google Code Jam 2021, Chung kết Thế giới, bài Slide Circuits.