Test Set 1 (công khai)

Ở Test Set 1, ta cần chuẩn bị mọi ô bên trong một hình chữ nhật song song với lưới có diện tích ít nhất 20. Trước khi triển khai chuột, hãy chọn một vùng mục tiêu hình chữ nhật diện tích ít nhất 20 và cố chuẩn bị tất cả các ô trong đó. Một lựa chọn là vùng \(4\times5\); ta cũng có thể chọn \(3\times7\), \(5\times5\), v.v., miễn là vùng không quá lớn. Vị trí của vùng trong ma trận \(1000\times1000\) ban đầu không quan trọng, nên hãy đặt hai góc đối diện của nó tại \((1,1)\) và \((4,5)\). Ở đây \((r,c)\) chỉ ô thuộc hàng \(r\), cột \(c\) của ma trận gốc. Câu hỏi còn lại là liệu có chiến lược nào chuẩn bị được mọi ô trong vùng mục tiêu này mà không chuẩn bị ô nào khác hay không.

Ta minh họa vùng mục tiêu \(4\times5\) như sau; số hàng và cột được ghi kèm cho tiện theo dõi:

  12345
1 xxxxx
2 x@@@x
3 x@@@x
4 xxxxx

Các ô bên trong được đánh dấu @, còn các ô biên là x. Không nên triển khai chuột tại ô biên vì làm vậy có thể khiến nó chuẩn bị một ô ngoài vùng mục tiêu. Ta chỉ triển khai tại sáu ô bên trong được đánh dấu @. Tổng cộng có 1000 lần triển khai, nên hãy triển khai chuột tại mỗi ô bên trong \(\lfloor1000/6\rfloor=166\) lần. Liệu như vậy đã đủ để giải Test Set 1 chưa?

Để trả lời câu hỏi quan trọng này, hãy tính xác suất ô \((1,1)\) vẫn chưa được chuẩn bị sau khi triển khai theo cách trên. Ô này chỉ có thể được chuẩn bị khi chuột được triển khai tại \((2,2)\). Mỗi lần như vậy, xác suất chuột chuẩn bị \((1,1)\) là \(1/9\), hay nhìn theo chiều ngược lại, xác suất nó không chuẩn bị \((1,1)\) là \(8/9\). Do đó, sau 166 lần triển khai tại \((2,2)\), xác suất \((1,1)\) vẫn chưa được chuẩn bị là \((8/9)^{166}=3{,}226\times10^{-9}\), một giá trị rất nhỏ. Trên thực tế, ta không cần lo điều này xảy ra với bất kỳ góc nào trong bốn góc, vì xác suất ít nhất một góc gặp tình huống ấy là \(1-(1-3{,}226\times10^{-9})^4=1{,}29\times10^{-8}\). Các ô khác kề với nhiều hơn một ô bên trong nên còn có khả năng được chuẩn bị cao hơn các góc. Vì thế, lời giải này đủ để vượt qua Test Set 1.

Để củng cố kết luận, nhóm ra đề đã chạy một mô phỏng: liên tục triển khai chuột vào tâm một vùng \(3\times3\) cho đến khi cả chín ô đều được chuẩn bị, rồi lặp lại thí nghiệm này 100.000 lần và thu được kết quả sau.

Biểu đồ phía trên cho biết có bao nhiêu trong số 100.000 lần mô phỏng (trục tung) cần từng số lần triển khai có thể xảy ra (trục hoành). Trong 100.000 lần mô phỏng, số lượt lớn nhất cần dùng không vượt quá 120. Vì vậy, 166 lần là dư sức để chuẩn bị một ô bên trong cùng toàn bộ các ô xung quanh nó. Hơn nữa, một khi một ô bên trong và cả tám ô kề nó đều đã chuẩn bị, không có lý do gì triển khai tại đó nữa; gần như chắc chắn ta sẽ còn nhiều hơn 166 lượt để lấp ô ngoan cố cuối cùng nếu cần.

Test Set 2 (ẩn)

Bây giờ ta phải tạo một vùng hình chữ nhật có diện tích ít nhất 200. Nếu áp dụng chiến lược cũ cho một hình chữ nhật \(10\times20\), chẳng hạn, ta chỉ có thể triển khai \(\lfloor1000/(18\times8)\rfloor=6\) lần tại mỗi ô bên trong. Khi ấy, xác suất ô \((1,1)\) chưa được chuẩn bị là \((8/9)^6=0{,}49327\), lớn đến mức không thể chấp nhận!

Làm thế nào để cải thiện chiến lược? Ta nhận thấy phần lớn các ô có thể được chuẩn bị từ nhiều vị trí. Chẳng hạn, ô \((2,2)\) có thể được chuẩn bị khi triển khai tại bất kỳ ô bên trong nào xung quanh nó, hoặc ngay tại chính nó. Hãy chia vùng hình chữ nhật thành các vùng \(3\times3\) rời nhau và chỉ triển khai chuột tại tâm của từng vùng. Khi đó, mỗi ô chỉ có thể được chuẩn bị từ đúng một tâm. Tóm lại, kế hoạch là:

• Chọn một hình chữ nhật đủ lớn, chẳng hạn \(3\times69\).
• Để thuận tiện, đặt một góc của hình chữ nhật \(3\times69\) tại \((1,1)\).
• Chia vùng \(3\times69\) thành \(69/3=23\) vùng \(3\times3\) rời nhau. Ta chỉ triển khai chuột tại \((2,2),(2,5),(2,8),\ldots,(2,68)\), tức các ô tâm của những vùng đó.
• Tiếp tục triển khai tại \((2,2)\) cho đến khi mọi ô trong lưới \(3\times3\) tâm \((2,2)\) đều được chuẩn bị.
• Sau đó chuyển sang triển khai tại \((2,5)\), rồi tiếp tục tương tự.

Liệu như vậy đã đủ chưa? Mô phỏng phía trên cho thấy đôi khi cần 120 lần triển khai để chuẩn bị trọn một vùng \(3\times3\). Trong trường hợp xấu nhất, chuẩn bị cả vùng \(3\times69\) sẽ cần \(23\times120=2760\) lượt, vượt quá giới hạn 1000. Tuy nhiên, tình huống xấu nhất như vậy không phải lúc nào cũng xảy ra. Nhóm ra đề đã chạy thêm một mô phỏng để khảo sát chiến lược mới.

Biểu đồ phía trên cho biết có bao nhiêu trong số 100.000 lần mô phỏng (trục tung) cần từng số lượt triển khai (trục hoành) để chuẩn bị mọi ô trong vùng mục tiêu \(3\times69\). Số lượt lớn nhất quan sát được không vượt quá 850, trong khi giới hạn là 1000. Vì vậy, ta có thể tin tưởng rằng chiến lược này đủ để vượt qua Test Set 2.

Còn nhiều chiến lược khác. Một cách là luôn triển khai chuột tại ô có số ô chưa chuẩn bị lớn nhất trong vùng \(3\times3\) lấy ô đó làm tâm. Kết quả mô phỏng 100.000 lần của chiến lược này trông còn tốt hơn kết quả trước.

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2018, Vòng loại, bài Go, Gopher!; kho Google Coding Competitions Archive (Apache-2.0).