Phương pháp

Lời giải chủ đích có thể tóm thành các bước sau:

1. Coi đây là một bài toán đồ thị. Có \(N\) đỉnh và mỗi cạnh chỉ khả dụng trong một khoảng thời gian.
2. Với mỗi đỉnh, sắp các cạnh, chẳng hạn theo thời điểm bắt đầu khả dụng. Chừng nào còn ít nhất một cạnh mở, ta có thể nhảy qua lại; hơn nữa, hiển nhiên chỉ có thể đến một tiểu hành tinh khi có ít nhất một cạnh mở. Vì vậy sẽ có những “khoảng trống” không cạnh nào khả dụng, và ta phải rời tiểu hành tinh trước khoảng trống đó. Tách mỗi đỉnh thành nhiều đỉnh theo các khoảng trống này. Số cạnh không tăng, nên toàn đồ thị vẫn có kích thước \(O(N^2)\).
3. Chạy Dijkstra trên đồ thị mới. Khi đến một đỉnh, chỉ có thể dùng các cạnh đi ra chưa đóng; thời điểm đi cạnh là giá trị lớn hơn giữa thời điểm hiện tại và thời điểm cạnh mở.
4. Khi tới tiểu hành tinh 1, ta đã tìm được hành trình cần thiết.

Để kiểm tra một ngưỡng khoảng cách \(D\), với mỗi cặp tiểu hành tinh ta giải bất đẳng thức khoảng cách giữa hai điểm chuyển động tuyến tính không vượt quá \(D\); bình phương khoảng cách là một tam thức bậc hai theo thời gian, nên tập thời gian hợp lệ là một khoảng, có thể rỗng. Có thể tìm nhị phân \(D\) và áp dụng đồ thị thời gian ở trên cho mỗi lần kiểm tra. Việc nhảy qua lại trên một cạnh đang mở đặt lại giới hạn \(S\), còn các khoảng trống xác định lúc bắt buộc phải rời đi.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 3.