Phân tích: Apocalypse Soon

Bài toán này giống như một "con cừu trong lốt sói". Mặc dù cách giải thực sự khá đơn giản, nhưng số lượng thí sinh giải được nó lại ít hơn bất kỳ bài nào khác trong vòng thi. Vì đây là một vòng thi trực tiếp, các thí sinh đều là những người có kinh nghiệm; và theo một nghĩa nào đó, kinh nghiệm đó lại phản tác dụng với họ.

Tại sao bài toán này trông có vẻ khó? Với một người có kinh nghiệm, nó mang đầy đủ các đặc điểm của một bài tìm kiếm tổ hợp (exponential search) kinh khủng. Bạn có 5 lựa chọn hành động mỗi ngày, và kết quả của những hành động đó không có xu hướng chồng lấp, dẫn đến số lượng trạng thái khả thi tăng theo cấp số nhân. Hơn nữa, ngay cả một thay đổi nhỏ nhất trong sức mạnh của một quốc gia cũng có thể ảnh hưởng lớn đến kết quả cuối cùng, vì vậy ở mỗi bước, toàn bộ trạng thái của thế giới đều quan trọng. Điều này làm cho giải pháp dựa trên Quy hoạch động (Dynamic Programming) có vẻ không khả thi. Và do tính chất hỗn loạn của các quy tắc, khó có thể có một chiến thuật tham lam nào hoạt động trong mọi trường hợp.

Vì vậy, một cuộc tìm kiếm tổ hợp có vẻ là điều tất yếu. Trên một lưới \(50 \times 50\) với các con số từ 0 đến 1000, điều này rõ ràng là không thể thực hiện được! Nhưng khoan đã... bài toán này chắc chắn phải giải được bằng cách nào đó, đúng không?

Nếu bạn thử một vài trường hợp bằng tay, bạn sẽ sớm nhận ra lý do: mọi quốc gia đều tiêu diệt hàng xóm của họ rất, rất nhanh. Một bản đồ ngẫu nhiên có xu hướng ổn định (không còn hàng xóm nào còn sống) chỉ trong 4-6 ngày. Thực tế rất khó để tạo ra một trường hợp kéo dài lâu hơn. Bạn càng thử, bạn càng nhận ra nó khó khăn thế nào; kích thước quân đội cần thiết tăng theo cấp số nhân, và bạn càng xếp chúng chặt chẽ thì chúng càng nhanh chết. Kích thước bản đồ hóa ra không quan trọng lắm - chính giới hạn sức mạnh quân đội là 1000 mới thực sự đặt ra giới hạn cho thời gian bạn cần tìm kiếm.

Chính xác thì giới hạn này là bao nhiêu? Đó là một câu hỏi thực sự khó. Ví dụ, nếu sức mạnh quân đội không bị giới hạn, thì sẽ không có giới hạn nhỏ nào cả. Đây là một trường hợp đơn giản \((2n-2) \times 2\) mất \(n\) ngày để ổn định:

1 2 4 8 ... 2^(2n-3)
1 2 4 8 ... 2^(2n-3)

Tuy nhiên, sức mạnh quân đội phải tăng theo cấp số nhân so với số ngày. Đây là một chứng minh đơn giản: vào ngày \(n\), gọi \(S_n\) là sức mạnh của quốc gia mạnh nhất vẫn còn hàng xóm đang sống. Gọi \(N\) là bất kỳ quốc gia nào có sức mạnh \(\ge S_n/2\). Giả sử sau 8 ngày \(N\) vẫn có sức mạnh \(\ge S_n/2\). Khi đó nó phải đã tiêu diệt tất cả hàng xóm của mình, vì không có hàng xóm nào có sức mạnh \(\ge S_n\) (tức là bất kỳ hàng xóm nào cũng sẽ chết sau tối đa 2 lần bị tấn công). Vì vậy, mỗi quốc gia \(N\) như vậy hoặc kết thúc trong tình trạng bị cô lập hoặc yếu hơn \(S_n/2\) sau 8 ngày. Do đó, \(S_{n+8} \le S_n/2\). Điều này đặt ra một giới hạn nghiêm ngặt là \(8(\log_2 S_n + 1)\) ngày nữa trước khi tất cả các quốc gia chết hoặc bị cô lập.

Rất tiếc, với sức mạnh quân đội tối đa là 1000, giới hạn 80 ngày này vẫn không giúp ích nhiều. Giới hạn có thể được cải thiện bằng các lập luận chặt chẽ hơn, nhưng do tính chất nhỏ gọn và bị ràng buộc của lưới, giới hạn "thực sự" có lẽ nhỏ hơn nhiều - khoảng 9-10 ngày! Tuy nhiên, chúng tôi không biết cách chứng minh một giới hạn nào gần mức đó.

Bộ dữ liệu kiểm tra tệ nhất của chúng tôi có kết quả là "9 day(s)". Vì vậy, hóa ra ngay cả một giải pháp vét cạn trực tiếp (với độ phức tạp cỡ \(50 \times 50 \times 5^9\)) cũng đủ để giải quyết nó. Việc thêm các kỹ thuật cắt tỉa đơn giản và ghi nhớ (memoization) cũng có thể giúp ích, nhưng không nhất thiết.

Một sai lầm tiềm ẩn khi lập trình là giả định rằng các hiệu ứng chỉ có thể lan truyền một ô lưới mỗi ngày. "Tốc độ ánh sáng" (như cách gọi trong các trò chơi ô tự động - cellular automata) thực tế là hai ô lưới mỗi ngày, bởi vì nếu hàng xóm của một đội quân thay đổi, nó có thể chọn tấn công hàng xóm đối diện thay thế. Trong bộ test "9 day(s)", có những quốc gia cách xa quốc gia của bạn 13 ô vẫn có thể ảnh hưởng đến kết quả. Vì vậy, nếu bạn cố gắng tăng tốc giải pháp bằng cách chỉ xem xét vùng địa phương xung quanh quốc gia của mình, bạn phải cẩn thận đừng để nó quá địa phương.

Cuối cùng, tất cả những gì cần thiết để giải quyết bài toán này là sự dũng cảm (hoặc liều lĩnh). Nếu bạn lập trình nó đúng cách và thử chạy, nó sẽ hoạt động! Đó chỉ là câu hỏi về việc bạn có thể thuyết phục bản thân rằng giải pháp đơn giản có hy vọng thành công hay không. Chắc chắn bạn sẽ không muốn tải bộ dữ liệu Lớn xuống rồi sau đó mới nhận ra lời giải của mình quá chậm...

Dựa trên phân tích chính thức của Google Code Jam.