Phân tích

Test Set 1

Gọi \(f(k)\) là số cách ván chơi kết thúc với điểm ít nhất \(k\). Số cách có điểm đúng \(k\) là \(f(k)-f(k+1)\). Do đó:

vì theo định nghĩa \(f(M+1)=0\).

Để tính \(f(k)\), với mỗi lá ta chỉ quan tâm giá trị có ít nhất \(k\) hay không. Cố định một tập con \(S\) các lá có giá trị ít nhất \(k\); duyệt đủ \(2^N\) tập. Gán điểm \(0\) cho lá ngoài \(S\), \(1\) cho lá trong \(S\), rồi tính điểm của mọi đoạn liên tiếp có thể được đưa cho người chơi theo độ dài tăng dần.

Chỉ các đoạn “căn chỉnh” có độ dài lũy thừa hai mới xuất hiện: các ô \(i2^j+1,\ldots,i2^j+2^j\) với \(0\le j\le L\), \(0\le i<2^{L-j}\). Có tổng \(2^L+2^{L-1}+\cdots+1=2^{L+1}-1\) đoạn.

Biết điểm hai nửa, điểm đoạn là max nếu tới lượt Alice, min nếu tới lượt Bob; là lượt Alice khi và chỉ khi \(j,L\) cùng tính chẵn lẻ. Nếu toàn bảng có điểm \(0\), tập \(S\) không tạo điểm ít nhất \(k\). Nếu điểm là \(1\), số cách ghi bài tạo đúng tập \(S\) bằng

với \(t=|S|\). Tổng độ phức tạp \(O(M2^N2^L)\).

Test Set 2

Biểu thức trên, khi chỉ coi \(k\) là biến, khai triển thành đa thức bậc không quá \(N\); do đó \(f(k)\) cũng là đa thức bậc không quá \(N\). Theo công thức Faulhaber,

là đa thức theo \(x\) bậc không quá \(N+1\). Vì thế xác định đầy đủ \(g\) bằng \(N+2\) giá trị \(g(0),g(1),\ldots,g(N+1)\). Tính các giá trị đó như Test Set 1, rồi nội suy để lấy \(g(M)\).

Phần đầu tốn \(O(N2^N2^L)\). Nội suy Lagrange trực tiếp tốn \(O(N^2)\); có cách nhanh hơn nhưng không ảnh hưởng tổng thời gian.

Để giảm thừa số \(2^N\), nhận xét lá có chỉ số xuất hiện nhiều nhất một lần trên bảng không cần cố định trước trạng thái \(\ge k\). Chỉ cố định các lá lặp lại. Khi chạy minimax, thay điểm \(0/1\) của đoạn bằng số cách gán các lá không lặp để đoạn có giá trị \(1\). Các quyết định vẫn được thực hiện tham lam; phần tổ hợp được tính tại từng nút thay vì ở cuối.

Với tối ưu này, mỗi giá trị cần của \(g\) chỉ chạy \(2^X\) lần, trong đó \(X\) là số chỉ số lá xuất hiện hơn một lần. Có nhiều nhất \(2^{L-1}\) chỉ số như vậy, nên thời gian bước đầu giảm thành

đủ vượt Test Set 2.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 3, bài Binary Search Game.