Không cần mô phỏng các lần bắt kịp

Câu hỏi chớp nhoáng: bài có vẻ khá phức tạp, phải làm gì? Một hướng tự nhiên là tìm kiếm nhị phân tốc độ của Annie, nhưng không dễ kiểm tra trực tiếp một tốc độ có gây vượt hay không: input không cho vị trí từng ngựa theo thời gian vì chúng có thể làm nhau chậm lại. Về lý thuyết, ta có thể tính mọi lần ngựa nhanh bắt ngựa chậm, dựng chính xác từng quỹ đạo rồi kiểm tra quỹ đạo Annie có cắt chúng không. Với nhiều nhất hai ngựa ở Test Set 1 điều này khả thi, nhưng ở Test Set 2 sẽ rất rườm rà.

Ta tránh được toàn bộ việc đó bằng vài nhận xét. Để tối đa tốc độ, Annie phải tới đích đúng lúc một con ngựa phía trước — gọi là A — tới nơi; không có lý do để chừa khoảng thời gian trống. Hoặc A tới đích mà không giảm tốc và trực tiếp giới hạn Annie, hoặc A bị con B phía trước làm chậm. Với B cũng vậy: hoặc B không giảm tốc và là giới hạn cuối cùng, hoặc bị con phía trước nữa làm chậm, cứ thế tiếp tục. Vì vậy tồn tại một ngựa giới hạn duy nhất quyết định thời gian sớm nhất Annie có thể tới đích. Ta sẽ chứng minh chỉ con này có ý nghĩa.

Các ngựa ở phía đông ngựa giới hạn có thể bỏ qua vì chúng vượt qua đích trước khi ngựa giới hạn tới. Với những ngựa trung gian giữa Annie và ngựa giới hạn, theo định nghĩa mỗi con sẽ bắt kịp ngựa giới hạn trước đích; nếu không, chính nó mới là ngựa giới hạn. Giả sử Annie chọn tốc độ để tới đích cùng lúc ngựa giới hạn. Cô chắc chắn không thể đi nhanh hơn. Tốc độ ấy cũng an toàn: nếu Annie đủ nhanh để vượt một ngựa trung gian, cô cũng phải đủ nhanh để vượt ngựa giới hạn mà con trung gian sẽ bắt kịp, mâu thuẫn. Do đó không cần quan tâm các ngựa trung gian hay tương tác giữa chúng.

Công thức và thuật toán

Nếu ngựa \(i\) không bị cản, thời gian từ vị trí \(K_i\) tới đích là

Có thể xác định trực tiếp ngựa giới hạn theo chuỗi lập luận trên, nhưng vẫn là việc thừa. Thay vào đó, lần lượt giả sử từng ngựa là ngựa giới hạn và tính tốc độ mà nó áp đặt. Thời gian Annie bắt buộc phải dành cho chuyến đi là

nên tốc độ lớn nhất là

Tương đương, với mỗi ngựa tính \(D/T_i\) rồi lấy nhỏ nhất. Ngựa cho phép tốc độ lớn hơn không thể là giới hạn thật, vì tốc độ ấy sẽ khiến Annie vượt ngựa giới hạn thật. Thuật toán tốn \(O(N)\) thời gian, \(O(1)\) bộ nhớ ngoài input. Dùng số thực đủ chính xác và in nhiều chữ số sau dấu thập phân.

Dựa trên phân tích chính thức của Google Code Jam 2018, Vòng luyện tập, bài Steed 2: Cruise Control.