Phân tích: The Killer Word

Hằng năm, có những thí sinh nói với chúng tôi rằng họ đã cài đặt chương trình đúng nhưng chương trình chạy quá chậm. Đáng tiếc, quá chậm cũng đồng nghĩa với sai. Google Code Jam là một cuộc thi thuật toán, và sau khi vượt qua những câu đầu tiên, việc tìm ra một thuật toán nhanh thường chính là toàn bộ trọng tâm của bài toán.

Tại sao chúng tôi nhắc đến điều này? Vì bài này là một cái bẫy. Thoạt nhìn, nó giống hệt hai bài đầu của Vòng loại. Chúng tôi đưa cho bạn một thuật toán, và bạn cài đặt chính xác như mô tả:

• Lặp qua từng danh sách của Sean.
• Lặp qua từng từ trong từ điển.
• Xem Sean mắc bao nhiêu lỗi khi đoán từ này.

Vì bước cuối đòi hỏi phải duyệt lại mọi từ, thời gian chạy của cách này là \(O(N^2M)\).

Chúng tôi sẽ luôn đưa cho bạn những dữ liệu khó nhất có thể đặt vừa trong các giới hạn đã nêu, nghĩa là bạn sẽ gặp \(N=10000\) và \(M=100\). Cả máy tính nhanh lẫn ngôn ngữ nhanh đều không cứu được bạn ở đây — toàn bộ cách tiếp cận đơn giản là quá chậm. Chẳng hạn, bản cài đặt C++ của chúng tôi mất hơn 20 phút cho một test case. Để thành công trong một cuộc thi thuật toán, bạn cần nhận ra trước những vấn đề như vậy, bằng cách xem xét độ phức tạp Big O hoặc tự thử một dữ liệu xấu nhất.

Một khi đã thấy vấn đề, việc tăng tốc đáng kể không quá khó. Ý tưởng chính là kết hợp hai bước cuối:

• Lặp qua từng danh sách của Sean.
• Chia các từ thành những lớp khác nhau theo độ dài. Nếu chỉ xét một lớp, Sean sẽ đưa ra cùng một lần đoán đầu tiên cho mọi từ trong lớp ấy, bởi trong mỗi trường hợp cậu có lượng thông tin hoàn toàn giống nhau.
• Với mỗi lớp, xác định chữ cái Sean sẽ đoán, rồi tiếp tục chia lớp theo từng câu trả lời khác nhau mà bạn có thể đưa ra cho lần đoán của Sean.
• Lặp lại với từng lớp con cho đến khi chỉ còn một từ; lúc đó Sean sẽ hoàn tất mà không mắc lỗi.

Thời gian chạy ở đây là \(O(NM)\), nhanh hơn cách trực tiếp hàng trăm lần.

Kỹ thuật này tương tự Quy hoạch động: trò chơi bắt đầu giống nhau đối với nhiều từ khác nhau, nên ta không cần làm lại toàn bộ công việc đó mỗi lần.

Một vài sự thật vui: ban đầu bài này có tên là Bloodthirsty Executioner Man, nhưng đã được đổi tên vì hình người treo cổ làm bằng giấy và không có máu. Chính Sean cũng đã trả lời một số câu hỏi làm rõ cho bài này.