Dạng của hành trình tối ưu

Chiến lược tối ưu gồm việc chạy sang trái hoặc phải cho đến khi bắt một con chim cụ thể, đổi hướng, chạy cho đến khi bắt một con cụ thể ở phía bên kia, lại đổi hướng, và cứ thế cho đến khi bắt hết. Đổi hướng tại một thời điểm không bắt được chim nào chỉ gây lãng phí.

Xét một lời giải bộ phận trong đó ta đã bắt một số chim ở mỗi phía rồi quay về gốc. Với mỗi phía, gọi \(Q\) là con nhanh nhất chưa bị bắt. Để đơn giản hóa phân tích, nếu có nhiều con cùng phía và cùng tốc độ, ta bỏ qua tất cả trừ con ở xa nhất. Mọi con \(R\) khác ở cùng phía phải thuộc một trong các trường hợp:

• \(R\) nhanh hơn \(Q\). Khi đó \(R\) đã bị bắt.
• \(R\) chậm hơn \(Q\) và ở xa hơn. Khi đó \(R\) chưa thể bị bắt, vì muốn đến được \(R\) ta phải chạy qua \(Q\).
• \(R\) chậm hơn \(Q\) và không ở xa hơn. Ta có thể đã bắt hoặc chưa bắt \(R\), nhưng điều đó không ảnh hưởng đến lời giải: nếu chưa bắt, ta sẽ chạy qua \(R\) khi đi bắt \(Q\).

Quy hoạch động

Vì vậy, có thể giải bài toán bằng quy hoạch động mà trạng thái chỉ cần chứa danh tính của con nhanh nhất chưa bị bắt ở mỗi hướng. Với mỗi trạng thái được tạo ra, lưu thời điểm sớm nhất có thể đạt trạng thái ấy.

Từ trạng thái ban đầu chưa bắt con nào, với mỗi trạng thái ta thử chạy theo từng hướng cho đến khi bắt con nhanh nhất chưa bị bắt ở hướng đó rồi quay về gốc. Ta cũng thử chạy để bắt từng con nằm xa hơn con nhanh nhất chưa bị bắt ở mỗi hướng, rồi quay về. Với mỗi lựa chọn, tính con nhanh nhất chưa bị bắt mới ở hướng vừa chạy; con này xác định trạng thái mới khi ta trở về gốc. Nếu đạt trạng thái mới sớm hơn thời gian đã lưu thì cập nhật.

Mỗi khi tạo ra trạng thái mà mọi con chim đều đã bị bắt, xét thời điểm bắt con cuối cùng. Giá trị nhỏ nhất trong các thời điểm đó là đáp án; không cần tính thời gian quay về sau lần bắt cuối.

Cách biểu diễn này có \(O(N^2)\) trạng thái và có thể thử \(O(N)\) chuyển tiếp cho mỗi trạng thái, nên thời gian là \(O(N^3)\) và bộ nhớ là \(O(N^2)\).

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