Phân tích

Cũng như nhiều bài toán về trò chơi khác, bài này xoay quanh việc đánh giá một trạng thái cho trước và xác định đó là trạng thái thắng hay thua. Bài toán định nghĩa sai lầm là sự chuyển tiếp từ trạng thái thắng sang trạng thái thua, vì vậy sau khi xác định được loại của từng trạng thái, ta có thể dễ dàng đếm các sai lầm.

Test Set 1

Trong mọi trò chơi hữu hạn hai người tổng bằng không và không có kết quả hòa, khuôn khổ cơ bản để xác định một trạng thái có phải trạng thái thắng hay không đều giống nhau. Ta gọi một trạng thái là A-thắng (tương đương B-thua) nếu người chơi A có thể đảm bảo chiến thắng từ đó; nếu không, trạng thái là B-thắng/A-thua. Với một trạng thái cho trước, nếu trò chơi đã kết thúc thì kiểm tra điều kiện thắng. Nếu chưa kết thúc và đang là lượt của người chơi X, hãy thử mọi nước đi có thể. Nếu có bất kỳ nước nào dẫn đến một trạng thái X-thắng thì trạng thái hiện tại cũng là X-thắng. Nếu không, trạng thái hiện tại là X-thua. Ta có thể cài đặt điều này bằng một hàm đệ quy, nhưng vì mỗi lượt có thể có \(O(N^2)\) nước đi, cách đó chỉ đủ nhanh khi N nhỏ.

Ta có thể thấy ngay phép đánh giá đệ quy ấy thực hiện rất nhiều công việc trùng lặp. Chẳng hạn, xét trạng thái S và trạng thái S' thu được sau khi thực hiện P nước đi trên S. Vì có P! thứ tự để thực hiện các nước đi đó, khi đánh giá S một lần, trạng thái S' có thể phải được đánh giá tới P! lần. Do đó, ghi nhớ kết quả của hàm hoặc chuyển sang quy hoạch động sẽ tiết kiệm rất nhiều lời gọi đệ quy.

Ngoài ra, có nhiều trạng thái có thể được đánh giá mà không cần gọi đệ quy. Một trường hợp đơn giản là trạng thái đã có hai quân cờ kề nhau mang hai số liên tiếp (điều kiện "đã thắng" của người chơi A). Ta có thể cắt tỉa cây đệ quy bằng cách trả về ngay rằng các trạng thái này là A-thắng. Có thể cắt tỉa thêm: nếu trong lượt của A tồn tại một nước tạo ra một cặp như vậy (điều kiện "có thể thắng ngay"), ta chỉ cần thực hiện nước đó thay vì thử mọi nước của A. Ta cũng có thể giới hạn B chỉ thử những nước không để lại một điều kiện A-thắng đã biết. Vẫn còn các cách cắt tỉa khác; một số cách sẽ được khảo sát trong phần Test Set 2 bên dưới.

Ta có thể vượt qua Test Set 1 bằng cách kết hợp cắt tỉa đơn giản với ghi nhớ/quy hoạch động, hoặc bằng cách cắt tỉa thật nhiều.

Test Set 2

Số trạng thái có thể có trong Test Set 2 quá lớn, đến mức không thể chứa trong bộ nhớ ngay cả sau khi cắt tỉa cẩn thận. Tuy nhiên, cắt tỉa đủ mạnh giúp ta tìm được các tập trạng thái tương đương, tức các nhóm trạng thái mà ta có thể chứng minh là có cùng người thắng. Nhờ đó, số trạng thái cần ghi nhớ giảm đi đáng kể.

Trước hết chỉ xét các lượt của A. Ta đã nhắc đến các điều kiện "đã thắng" và "có thể thắng ngay". Ngoài ra, nếu còn một tập ba quân cờ chưa dùng mang ba số liên tiếp và một đoạn ba ô liên tiếp còn trống, A có thể thắng bằng cách đặt số ở giữa vào ô ở giữa (ta gọi đây là điều kiện "có thể thắng trong 2 nước"). Bất kể B đi gì tiếp theo, lượt sau của A sẽ thỏa mãn điều kiện "đã thắng" hoặc "có thể thắng ngay".

Các điều kiện trên giúp ta tìm một số trạng thái chắc chắn là A-thắng. Lưu ý rằng trong bất kỳ trạng thái nào khác mà đến lượt A, không quân cờ đã đặt nào có thể kết thúc trò chơi bằng cách trở thành một phần của cặp kề nhau mang hai số liên tiếp. Vì vậy, có thể thay chúng bằng các ô "không khả dụng" mà không cần ghi số cụ thể. Khi đó, các ô còn lại có thể được biểu diễn bằng đa tập độ dài của các nhóm ô liên tiếp còn trống; gọi đa tập này là \(L_C\). Vị trí chính xác của các nhóm trên bàn cờ không ảnh hưởng đến kết quả cuối cùng. Tương tự, vì mỗi quân cờ chỉ có thể tạo cặp kề nhau và liên tiếp với các quân cờ còn lại khác, ta có thể biểu diễn các quân cờ còn lại bằng đa tập độ dài của các đoạn số liên tiếp; gọi là \(L_T\). Chẳng hạn, trạng thái

7 2 6 _ _ 3 _ 4 _ _ 5

có các quân cờ còn lại là 1, 8, 9, 10, 11, nên các ô còn lại được biểu diễn bởi đa tập \(L_C = \{1, 2, 2\}\) và các quân cờ còn lại bởi đa tập \(L_T = \{1, 4\}\).

Ngoài ra, vì điều kiện "có thể thắng trong 2 nước" đã được kiểm tra, ta biết ít nhất một trong hai đa tập \(L_C\) và \(L_T\) không chứa số nguyên nào lớn hơn hoặc bằng 3. Để đơn giản hóa thuật toán, lưu ý rằng trò chơi thu được khi hoán đổi số quân cờ với số ô là tương đương, vì điều kiện thắng có tính đối xứng. Do đó, các trạng thái hoán đổi \(L_C\) và \(L_T\) là tương đương. Ta có thể giả sử \(L_C\) luôn là đa tập chỉ chứa các số 1 và 2.

Sau phép nén này, số trạng thái giảm mạnh. Vì không có ba số còn lại liên tiếp, ta biết ít nhất \(N/3\) số đã được chơi. Điều đó có nghĩa tổng các số nguyên trong cả \(L_C\) lẫn \(L_T\) (hai tổng này bằng nhau) không vượt quá \(2N/3\). Vì vậy, tổng số đa tập \(L_T\) có thể có dưới các điều kiện ấy bị chặn bởi tổng \(partitions(K)\) với mọi K từ 0 đến \(2N/3\), tức \(partitions(2N/3+1)\). Với một đa tập \(L_T\) như vậy, số đa tập \(L_C\) chỉ gồm 1 và 2, đồng thời có tổng bằng tổng của \(L_T\), bị chặn bởi \(N/3\) (số lượng số 2 tối đa). Do đó, số trạng thái không lớn hơn \((N/3) \times partitions(2N/3+1)\), một con số khá nhỏ với giới hạn N đã cho. Hơn nữa, ta chỉ cần một bảng ghi nhớ hoặc quy hoạch động dùng chung cho mọi bộ test.

Có nhiều cách đủ nhanh để cài đặt các lượt của người chơi thứ hai (đây là những lượt chậm nhất), và còn có thể đặt thêm các giới hạn lên những nước cần xét để tối ưu chiến thuật hơn nữa. Một số lựa chọn cho ra thuật toán có độ phức tạp đủ rõ ràng để biết chắc sẽ chạy kịp. Một số lựa chọn khác có độ phức tạp lý thuyết quá lớn hoặc khó ước lượng đủ chặt để tin rằng chúng đủ nhanh. May mắn là ta có thể tính hàm đệ quy cho mọi trạng thái có thể có mà không cần đọc dữ liệu vào, qua đó chắc chắn chương trình chạy kịp trước khi nộp.

Test Set 3 đã không xuất hiện

Chúng tôi từng cân nhắc thêm một test set thứ ba đòi hỏi lời giải đa thức. Chúng tôi lần lượt tìm ra các lời giải chạy trong \(O(N^3)\), \(O(N^2)\), và thậm chí một lời giải chỉ cần \(O(N \log N)\). Cuối cùng, chúng tôi quyết định không thêm test set này vì rất lo ngại khả năng thí sinh đoán đúng định lý mà không chứng minh. Việc tăng thử thách mà không buộc thí sinh đọc thêm cả một đề bài mới rõ ràng là lợi ích đáng kể, nhưng lợi ích ấy giảm đi vì theo ước tính của chúng tôi, khả năng test set được giải một cách chính đáng là thấp. Nếu chỉ cho nó ít điểm, công sức tương đối để giải sẽ không đáng. Nhưng nếu cho nhiều điểm, điều đó lại làm giảm giá trị của công sức cần thiết cho phần chúng tôi yêu thích nhất trong bài: giải Test Set 2.

Nếu muốn thử một thử thách bổ sung mà không bị tiết lộ lời giải, hãy dừng đọc tại đây. Nếu muốn xem vài gợi ý về các lời giải đó, hãy đọc tiếp!

Định lý thứ nhất tiếp tục nén các trạng thái được xét trong lời giải Test Set 2 ở lượt của A. Xét một trạng thái không thỏa các điều kiện "đã thắng", "có thể thắng ngay" hoặc "có thể thắng trong 2 nước", được biểu diễn bởi hai đa tập \(L_C\) và \(L_T\), trong đó chỉ \(L_T\) có thể chứa số nguyên lớn hơn 2. Trạng thái đó là A-thắng khi và chỉ khi trạng thái được biểu diễn bởi \(L_C\) và \(L'_T\) là A-thắng, trong đó \(L'_T\) thu được từ \(L_T\) bằng cách thay mỗi số nguyên X trong \(L_T\) bằng \(\lfloor X/2 \rfloor\) bản sao của số 2, cộng thêm một số 1 nếu X lẻ. Điều này giảm số trạng thái của quy hoạch động xuống \(O(N^3)\); ta có thể xử lý mỗi trạng thái trong thời gian hằng số vì chỉ có một số hữu hạn bị chặn các nước đi thực sự khác nhau.

Nếu tiếp tục hướng suy luận đó, ta có thể xác định trạng thái A-thắng chỉ bằng một số ít trường hợp. Gọi \(L_{Ci}\) là số lần i xuất hiện trong \(L_C\), và \(L_{Ti}\) là số lần i xuất hiện trong \(L_T\). Vì đã giả sử \(L_C\) không có số nguyên lớn hơn 2, \(L_{Ci}=0\) với mọi \(i \ge 3\). Đặt

là số lượt còn lại, và đặt

là số lần số 2 xuất hiện trong \(L'_T\) như mô tả ở đoạn trước. Khi đó, định lý thứ hai mà ta có thể chứng minh là:

• Nếu \(K=2\), trạng thái là A-thắng khi và chỉ khi \(L_{C2}=L_{T2}=1\).
• Nếu \(K>2\), trạng thái là A-thắng khi và chỉ khi K lẻ và \(2(L_{C2}+Z)>K\).

Từ yêu cầu tránh các điều kiện "đã thắng", "có thể thắng ngay" và "có thể thắng trong 2 nước", ta có thể thu gọn các nước trong lượt của B thành một tập gồm số lượng lựa chọn bị chặn, nhưng luôn chứa một nước thắng nếu nước thắng tồn tại. Kết hợp điều này với việc các điều kiện trên có thể được kiểm tra trong thời gian hằng số, ta được thuật toán xác định một trạng thái bất kỳ là thắng hay thua trong \(O(N)\), khiến toàn bộ quá trình cho một bộ test mất \(O(N^2)\). Với một số kỹ thuật bổ sung, ta có thể biểu diễn bàn cờ sao cho việc cập nhật và sử dụng nó để kiểm tra mọi điều kiện cần thiết chỉ mất \(O(\log N)\), từ đó xử lý trọn vẹn một bộ test trong \(O(N \log N)\).

Các chứng minh cho những định lý trong các đoạn trên được dành lại như một bài tập cho người đọc. Một gợi ý là chứng minh định lý thứ hai tổng quát hơn trước vì nó đã được phát biểu theo một dạng thuận tiện, rồi suy ra định lý thứ nhất như một hệ quả.

Chúng tôi khuyên bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Chung kết thế giới trực tuyến — Adjacent and Consecutive.