Khó khăn của bài toán nằm ở chỗ trạng thái của một hộp có thể ảnh hưởng tới kết quả rất lâu sau khi chó đã đi qua hộp đó, bởi nó có thể chặn hoặc không chặn một đường hầm. Ta xử lý khó khăn này bằng cách ghi nhớ trạng thái các hộp. Tất nhiên số hộp quá lớn để ghi nhớ toàn bộ trạng thái, nên ta nén trạng thái thành một lượng thông tin nhỏ hơn và có thể quản lý được. Cách nén khác nhau giữa hai phân nhóm.

Phân nhóm 1

Trong Phân nhóm 1, mọi đường hầm đều dẫn tới một hộp ở gần. Điều đó có nghĩa là khi chó đang ở hộp \(i\), trạng thái của những hộp có số nhỏ hơn \(i-5\) không còn có thể ảnh hưởng tới kết quả. Vì vậy, ta có thể dùng quy hoạch động để tính xác suất hộp \(i\) có mèo, với điều kiện biết trạng thái của \(k\) hộp gần nhất. Chỉ có \(O(N\times 2^k)\) trạng thái; vì ở Phân nhóm 1, \(k\) bị chặn trên bởi \(10\), số trạng thái này đủ nhỏ để giải bài.

Phân nhóm 2

Trong Phân nhóm 2, số hộp gần mà ta có thể cần ghi nhớ không bị chặn bởi một hằng số nhỏ, nên không thể dùng lời giải có độ phức tạp hàm mũ theo số đó. Hãy xét đồ thị có hướng mà mỗi hộp là một đỉnh và mỗi đường hầm là một cạnh có hướng. Do đồ thị có cùng số đỉnh và số cạnh, đây là một functional graph. Functional graph trông giống một rừng, ngoại trừ việc các “gốc” của nó là các chu trình. Lưu ý rằng chỉ thành phần liên thông trong đồ thị vô hướng nền có chứa hộp cuối cùng mới ảnh hưởng tới đáp án (các hộp thuộc những thành phần khác không ảnh hưởng tới việc hộp cuối có mèo hay không). Do đó, ta có thể loại bỏ mọi thành phần khác và từ đây giả sử đồ thị liên thông; khi ấy nó là một functional graph có đúng một chu trình.

Như một bài tập tư duy, trước hết giả sử đồ thị đường hầm thực ra là một cây có hướng (đã bỏ đi một đường hầm). Trong trường hợp này, ta có thể giải bài bằng cách mô phỏng hành trình của chó và ghi nhớ thông tin một cách khéo léo. Ta duy trì một rừng gồm các đỉnh tương ứng với mọi hộp và những đường hầm có thể đã được dùng cho tới lúc hiện tại, tức là các đường hầm đi ra từ những hộp mà chó đã đi qua. Với mỗi đỉnh, ta tính xác suất có mèo ở đó. Các biến cố “có mèo” tại hai hộp bất kỳ là độc lập nếu hai hộp thuộc hai cây khác nhau của rừng này; nếu chúng cùng một cây thì có thể không độc lập.

Ban đầu, rừng chứa mọi đỉnh nhưng chưa có cạnh. Xác suất tại mỗi đỉnh khởi đầu bằng \(0\), \(1/2\) hoặc \(1\), tùy hộp tương ứng chắc chắn trống, chưa biết, hay chắc chắn có mèo. Sau đó, khi mô phỏng chó đi qua hộp \(i\), ta thêm một cạnh vào rừng và hợp nhất hai cây. Cho tới thời điểm này, xác suất tại hai gốc của hai cây là độc lập, nên ta có thể tính xác suất đường hầm được dùng bằng tích của xác suất hộp \(i\) có mèo và xác suất hộp đích không có mèo. Tiếp theo, ta cập nhật mọi xác suất thành trung bình có trọng số của kết quả trong hai trường hợp (có mèo chạy qua đường hầm mới hoặc không).

Để cách trên hoạt động với một functional graph thực sự thay vì một cây, ta phải xử lý chu trình duy nhất. Ta có thể phân nhánh khi thêm cạnh đầu tiên của chu trình vào rừng (tức là khi chó chạy qua hộp có số nhỏ nhất trong số các hộp thuộc chu trình). Thay vì hợp nhất hai thành phần đó, ta xét cả \(4\) trường hợp trạng thái của hai hộp tại hai đầu đường hầm. Với mỗi trường hợp, ta có thể tính xác suất của nó bằng một phép nhân như trước, vì tại thời điểm này xác suất ở hai đầu mút độc lập. Sau đó, thay vì hợp nhất hai thành phần, ta bắt đầu \(4\) phép tính, mỗi phép tính ứng với một trường hợp, và trong tất cả chúng hai thành phần vẫn được giữ tách biệt. Cuối cùng, ta thu được \(4\) kết quả cho hộp cuối. Kết quả chung cuộc là trung bình có trọng số của bốn kết quả đó, với trọng số là xác suất của từng trường hợp đã tính tại thời điểm phân nhánh.

Nguồn

Google Code Jam 2022, Chung kết thế giới, bài Schrödinger and Pavlov.

Phân tích chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.