Test Set 1

Trong Test Set 1, các thành phố nằm trên một đường thẳng, ta biết khoảng cách giữa chúng và cần đi từ thành phố đầu tới thành phố cuối. Tuy nhiên, mục tiêu là tối thiểu hóa thời gian chứ không phải khoảng cách; cách chuyển đổi hiển nhiên là chia cho vận tốc không áp dụng trực tiếp vì các con ngựa có vận tốc khác nhau. Giống nhiều bài tối ưu trên đường đi chỉ tiến về phía trước, ta dùng quy hoạch động.

Đặt \(f(i)\) là thời gian nhanh nhất để đi từ thành phố \(i\) tới cuối đường, với giả thiết bắt đầu dùng ngựa ở thành phố \(i\). Khi đó \(f(1)\) là đáp án của truy vấn duy nhất.

Ta chưa biết cần đổi ngựa ở đâu, nhưng có thể thử mọi thành phố trung gian \(j\) làm nơi đổi tiếp theo. Như vậy:

và \(f(N)=0\).

Miền của \(f\) có \(N\) giá trị; nếu ghi nhớ kết quả, mỗi giá trị thử \(O(N)\) thành phố, nên tổng thời gian \(O(N^2)\). Các cách quy hoạch động khác với cùng độ phức tạp cũng hoạt động.

Test Set 2

Trong Test Set 2, thay vì một đường thẳng, ta có đồ thị thành phố \(G\) với khoảng cách trên các tuyến; những phần còn lại không đổi.

Một đặc điểm khá lạ là đại lượng cần tối ưu (thời gian) không cùng đơn vị với trọng số cạnh (khoảng cách). Hơn nữa, phép chuyển hiển nhiên bằng vận tốc không dùng một hằng số. Điều này dẫn tới ý tưởng chính: dựng một đồ thị mới có trọng số là thời gian thay vì khoảng cách, rồi áp dụng thuật toán đường đi ngắn nhất.

Định nghĩa \(G'\) có cùng tập đỉnh với \(G\), còn trọng số cạnh \((i,j)\) là thời gian đi từ thành phố \(i\) đến \(j\). Không có vận tốc cố định toàn cục, nhưng với một cạnh ta có thể cố định vận tốc: cạnh \((i,j)\) biểu diễn thời gian đi từ \(i\) tới \(j\) bằng đúng một con ngựa, hiển nhiên chọn ngựa ở thành phố xuất phát \(i\); gọi nó là \(h\).

Như vậy, cạnh \((i,j)\) trong \(G'\) biểu diễn một đường đi trong \(G\) được đi hoàn toàn bằng \(h\). Cạnh tồn tại khi và chỉ khi có một đường từ \(i\) đến \(j\) trong \(G\) với tổng khoảng cách không vượt sức bền của \(h\). Trọng số của cạnh là khoảng cách ngắn nhất từ \(i\) đến \(j\) trong \(G\) chia cho vận tốc của \(h\). Một đường đi tối thiểu từ \(a\) tới \(b\) trong \(G'\) là một chuỗi cạnh của \(G'\), tức một chuỗi chặng dùng đúng một con ngựa trong \(G\) — chính xác là hình thức của một lời giải hợp lệ.

Các giới hạn đủ nhỏ; ta cần mọi đường đi ngắn nhất trong \(G\) để dựng \(G'\), rồi nhiều đường đi ngắn nhất trong \(G'\) để trả lời truy vấn. Vì thế lựa chọn tốt nhất là thuật toán đường đi ngắn nhất mọi cặp. Floyd–Warshall dễ và nhanh cài đặt nhất, nhưng thuật toán khác cũng được. Để biểu diễn cạnh/đường không tồn tại, đặt trọng số bằng “vô cực”, tức một khoảng cách lớn hơn mọi đường ngắn nhất thật sự (lớn hơn khoảng cách tối đa nhân tổng số cạnh). Khoảng cách vô cực khi ấy có nghĩa là không có cạnh hoặc đường.

Tóm lại:

1. Chạy Floyd–Warshall trên \(G\) để lấy khoảng cách giữa mọi cặp đỉnh.
2. Dựng \(G'\): thêm cạnh \((i,j)\) nếu khoảng cách từ \(i\) đến \(j\) trong \(G\) không vượt sức bền ngựa ở \(i\); đặt trọng số bằng khoảng cách đó chia vận tốc ngựa ở \(i\).
3. Chạy Floyd–Warshall trên \(G'\) để lấy thời gian nhỏ nhất giữa mọi cặp đỉnh.
4. Đọc truy vấn và trả lời ngay bằng kết quả bước trước.

Độ phức tạp là \(O(N^3)\). Mỗi lần Floyd–Warshall tốn \(O(N^3)\), còn dựng ma trận kề của \(G'\) chỉ tốn \(O(N^2)\).

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1B, bài Pony Express.