Test Set 1

Có thể xem mê cung Wonderland là một đồ thị vô hướng. Nếu Alice đến được một chu trình trước khi Nữ hoàng đến được chỗ cô, Alice sẽ an toàn, vì cô luôn có thể chọn một chiều chạy quanh chu trình để rời xa Nữ hoàng. Ngược lại, nếu Alice không thể đến một chu trình trước Nữ hoàng, Nữ hoàng sẽ bắt cô sau nhiều nhất \(2J\) nước đi. Cứ mỗi hai nước đi Alice có thể chuyển sang một đỉnh, nên sau \(2J\) nước đi, Alice buộc phải đi vào một chu trình; nếu không thì Nữ hoàng đã bắt được cô.

Từ các nhận xét đó, ta xây dựng quy hoạch động. Định nghĩa hàm đệ quy solution(alice, queen, total_moves) bằng đúng nếu Nữ hoàng có thể bắt Alice trong nhiều nhất total_moves khi cả hai chơi tối ưu, và bằng sai nếu không. Đáp án là giá trị nhỏ nhất của total_moves sao cho solution(A, Q, total_moves) đúng. Nếu không có giá trị nào như vậy, Alice an toàn.

Ta tính solution(alice, queen, total_moves) bằng một hệ thức truy hồi: thử mọi nước đi của Nữ hoàng và mọi nước đi của Alice trong hai vòng lặp lồng nhau, rồi gọi đệ quy solution. Nữ hoàng luôn cố làm kết quả thành đúng, còn Alice luôn cố làm nó thành sai.

Cận trên độ phức tạp là \(O(J^5)\): có \(O(J^3)\) trạng thái và việc tính một trạng thái cần nhiều nhất \(O(J^2)\) thời gian. Có thể phân tích chặt hơn, nhưng cận này đã đủ nhanh cho Test Set 1.

Test Set 2

Test Set 2 cần lời giải nhanh hơn. Gọi một đỉnh là tốt nếu, một khi Alice đến được đó trước khi bị bắt, cô sẽ luôn an toàn. Nói cách khác, bất kể Nữ hoàng đang ở đâu, từ một đỉnh tốt Alice luôn có cách di chuyển an toàn. Ta sẽ tìm tất cả các đỉnh tốt.

Giả sử đồ thị liên thông. Các lá, tức đỉnh bậc \(1\), không bao giờ tốt vì Alice có thể bị dồn vào đường cùng ở đó, nên ta bắt đầu bằng cách xóa chúng. Thực ra, nếu liên tục xóa lá cho đến khi không còn lá, mọi đỉnh còn lại đều tốt vì Alice không thể bị dồn vào đường cùng. Có thể cài đặt tuyến tính bằng một hàng đợi các lá và duy trì bậc của từng đỉnh trong quá trình xóa.

Định nghĩa \(DA_u\) là độ dài đường đi ngắn nhất từ vị trí ban đầu của Alice đến đỉnh \(u\), và \(DQ_u\) tương tự cho Nữ hoàng. Nếu với một đỉnh \(j\) ta có \(DA_j<DQ_j\), Alice có thể đến đó an toàn trước khi bị bắt. Chứng minh phản chứng: nếu Nữ hoàng chặn được Alice ở đâu đó trên đường đi, bà phải đến một đỉnh trên đường đi ngắn nhất của Alice trước Alice; điều đó kéo theo Nữ hoàng cũng có thể đến \(j\) trước. Hai bảng \(DA,DQ\) được tính bằng hai lần tìm kiếm theo chiều rộng (BFS), mỗi lần lưu lại các khoảng cách.

Từ đó, Alice an toàn trong một trong các trường hợp:

• Đồ thị không liên thông và Alice cùng Nữ hoàng bắt đầu ở hai thành phần liên thông khác nhau. Có thể kiểm tra điều này từ \(DA\) hoặc \(DQ\).

• Alice có thể đi vào một đỉnh tốt \(j\) thỏa \(DA_j<DQ_j\).

Nếu không thuộc hai trường hợp trên, Alice sẽ bị bắt. Vì chiến lược của Alice là tối đa hóa số nước đi trước khi bị bắt, cô chọn giao lộ có khoảng cách đến Nữ hoàng lớn nhất trong số các giao lộ mà cô có thể đến trước, tức thỏa \(DA_j<DQ_j\).

Lời giải chỉ cần ba lượt duyệt tuyến tính trên đồ thị: một lượt tìm các đỉnh tốt và hai lượt BFS. Tổng độ phức tạp là \(O(J+C)\).

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2022, World Finals.