Test Set 1

Ở lượt của một người chơi, lưới ở một trạng thái nào đó, tùy theo các khuẩn lạc đã được đặt và cách chúng lan. Ta xác định một trạng thái là thua bằng định nghĩa đệ quy sau:

• Người chơi không có nước đi vì không còn ô trống; hoặc
• mọi nước đi đều gây đột biến hoặc đưa đối thủ đến một trạng thái thắng.
• Trạng thái thắng là trạng thái có ít nhất một nước thắng, tức một nước để lại cho đối thủ trạng thái thua.

Nếu một trạng thái không thua thì nó phải thắng, vì khi đó tồn tại ít nhất một nước vừa không gây đột biến, vừa không trao cho đối thủ trạng thái thắng.

Để tìm số nước mở đầu thắng của Becca (nếu có), ta kiểm tra từng nước xem nó có phải nước thắng hay không. Muốn vậy phải xét đệ quy trạng thái thu được theo định nghĩa trên. Tuy nhiên, mỗi trạng thái có thể có đến hai nước trên mỗi ô trống, nên cách ngây thơ đệ quy đếm số nước thắng ở mọi trạng thái có thể chưa đủ nhanh ngay cả với lưới \(4 \times 4\) của Test Set 1; ta cần tối ưu.

Tính thắng/thua của trạng thái không phụ thuộc người đang chơi hay các nước trước đó. Vì cùng một trạng thái có thể xuất hiện nhiều lần, ta nên memo hóa kết quả. Dù tổng số trạng thái có vẻ rất lớn, trong một bộ test chỉ có nhiều nhất 16 ô ban đầu trống và mỗi ô hoặc đã được vi khuẩn lấp, hoặc chưa. Sau khi khuẩn lạc được đặt và lan xong, loại của nó không còn quan trọng. Do đó số trạng thái mỗi bộ test không quá \(2^{16}\); trên thực tế còn ít hơn vì không phải trạng thái nào cũng tới được.

Ta còn có thể tiết kiệm thời gian bằng cách không tính chính xác số nước thắng cho mọi trạng thái. Chỉ trạng thái ban đầu cần con số đó; với mỗi trạng thái khác, chỉ cần biết thắng hay thua. Khi đang xét các nước của một trạng thái không ban đầu mà tìm thấy một nước thắng, ta kết luận ngay trạng thái ấy thắng và dừng. Chỉ riêng tối ưu này cũng có thể đủ cho Test Set 1.

Test Set 2

Khi thực hiện nước hợp lệ, vi khuẩn lan hết chiều rộng của hàng hoặc chiều dài của cột, cho đến khi dải vi khuẩn gặp biên lưới hoặc ô đã nhiễm. Vì vậy mỗi nước tạo ra nhiều nhất hai bài toán con độc lập: nước trong bài toán con này không ảnh hưởng trạng thái bài toán con kia.

Mỗi bài toán con biểu diễn được bằng một hình chữ nhật nằm trong toàn lưới, nên có nhiều nhất \(O(R^2C^2)\) bài toán con. Ta cần dùng kết quả của chúng để xác định người thắng toàn trò chơi.

Mục tiêu là buộc đối thủ vào tình huống không có nước nào dẫn họ tới chiến thắng. Đây là trò chơi công bằng (impartial): hai người có cùng tập nước đi. Vì vậy có thể so sánh Bacterial Tactics với trò Nim cổ điển, một trò chơi công bằng có kiểu quyết định tương tự. Theo định lý Sprague–Grundy, mọi trò chơi công bằng có thể ánh xạ thành một trạng thái Nim. Mỗi trạng thái Nim ứng với một số Grundy không âm, hay nimber; nimber khác 0 biểu thị trạng thái có thể thắng.

Theo phép cộng nimber, nimber của trạng thái sau khi đặt khuẩn lạc bằng XOR nimber của hai bài toán con. Nimber của trạng thái trước khi đặt là số nguyên không âm nhỏ nhất không thuộc tập (minimum excludant, MEX) các nimber có thể thu được sau mọi cách đặt:

let solve(state) be a function:
  let s = Ø
  for each legal colony placement:
    add [solve(first subproblem) XOR solve(second subproblem)] to s
  return MEX(s)

Từ khuôn khổ này, ta tối ưu cài đặt như sau.

Thứ nhất, giống Test Set 1, memo hóa các trạng thái; giờ mỗi trạng thái là một hình chữ nhật với kích thước và vị trí khác nhau trong lưới gốc. Một bài toán con không thể chứa vi khuẩn từ nước trước, vì ta luôn cắt hình chữ nhật dọc theo hàng hoặc cột vừa bị khuẩn lạc lấp. Ta cũng có thể tính trước nimber của mọi kích thước hình chữ nhật rỗng (không có ô phóng xạ), dùng chung cho mọi bộ test.

Thứ hai, nếu hợp lệ khi đặt khuẩn lạc V tại một ô thì cũng hợp lệ tại mọi ô cùng cột trong biên hình chữ nhật hiện tại; tương tự với khuẩn lạc H trên một hàng. Vì thế chỉ cần kiểm tra từng hàng và cột có cho phép đặt hay không, không cần kiểm tra từng ô.

Thứ ba, có thể xây dựng cấu trúc kiểm tra một cách đặt trên bất kỳ hàng hoặc cột nào trong một hình chữ nhật có hợp lệ hay không trong \(O(1)\), nhờ đó đánh giá trạng thái trong \(O(R+C)\). Với mỗi hàng và cột của toàn lưới, tạo một mảng. Duyệt các ô theo thứ tự tăng dần, tại mỗi vị trí lưu vị trí đánh số từ 1 của ô phóng xạ gần nhất đã gặp, hoặc 0 nếu chưa gặp. Chẳng hạn hàng .#..# cho [0, 2, 2, 2, 5]. Giả sử hình chữ nhật chứa ô thứ ba và thứ tư của hàng đó. Phần tử thứ tư là 2; vì ô 2 không nằm trong hình chữ nhật (chỉ có ô 3 và 4), ta kết luận đặt khuẩn lạc H trên hàng này là an toàn. Cấu trúc được tiền xử lý cho mỗi bộ test trong \(O(RC)\).

Tóm lại, có \(O(R^2C^2)\) bài toán con và mỗi bài toán cần \(O(R+C)\) phép toán. Đặt \(N=\max(R,C)\), độ phức tạp thời gian tổng cộng là \(O(N^5)\), đủ cho Test Set 2. Các lời giải kém hiệu quả hơn vẫn có thể đạt, tùy cách cài đặt.

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2019, Round 1C, bài Bacterial Tactics; kho Google Coding Competitions (Apache-2.0).