Giới thiệu

Bài toán yêu cầu xác định phần nào của một lộ trình \(E_1, E_2, \dots, E_k\) có thể là tiền tố của một con đường ngắn nhất từ thành phố 1 đến thành phố 2. Điều này sẽ dễ dàng nếu chúng ta biết chi phí chính xác của các cạnh - nhưng chúng ta chỉ biết các khoảng giá trị mà chúng thuộc về.

Small dataset

Hãy tập trung vào bất kỳ tiền tố cố định \(E_1, E_2, \dots, E_p\) nào của lộ trình được đề xuất và cố gắng biến nó thành tiền tố của một con đường ngắn nhất. Nếu chúng ta chọn một ứng cử viên đường ngắn nhất (bao gồm tiền tố của chúng ta), rõ ràng là có lợi khi giả định các cạnh trên lộ trình của chúng ta ngắn nhất có thể, và các cạnh khác dài nhất có thể.

Lưu ý rằng hệ quả của việc này là chúng ta có thể giới hạn bản thân trong việc xem xét các đồ thị mà trong đó mỗi cạnh có độ dài ngắn nhất hoặc dài nhất có thể. Do đó, vì trong tập dữ liệu nhỏ số lượng cạnh chỉ là 20, chúng ta có thể kiểm tra tất cả các khả năng - đặt một số cạnh là ngắn, số còn lại là dài, tìm đường ngắn nhất trong đồ thị kết quả (ưu tiên lộ trình được đề xuất bằng cách, ví dụ, giảm chi phí các cạnh trên lộ trình này đi một lượng epsilon nhỏ), sau đó trong tất cả các khả năng, chọn khả năng đi được nhiều bước nhất dọc theo lộ trình đề xuất.

Large dataset

Cách tiếp cận trên rõ ràng không khả thi cho tập dữ liệu lớn. Một lần nữa, chúng ta cố định một tiền tố \(E_1, E_2, \dots, E_p\) của lộ trình đề xuất và cố gắng biến nó thành tiền tố của đường ngắn nhất. Giả sử \(E_p\) kết thúc tại Tokyo. Như vậy, chúng ta sẽ cố gắng đi từ Tokyo đến London nhanh nhất có thể, trong khi vẫn không cho phép một con đường ngắn hơn từ Mountain View đến London mà không bắt đầu bằng tiền tố của chúng ta. Để tối ưu tốc độ, chúng ta có thể tìm kiếm nhị phân cho tiền tố dài nhất có thể là bắt đầu của một con đường ngắn nhất; nếu tối ưu cho sự đơn giản, chúng ta có thể chỉ cần lặp qua tất cả các tiền tố.

Hãy tưởng tượng hai robot cố gắng đến London nhanh nhất có thể. Một robot bắt đầu từ Tokyo, và có một "khoản chấp" là chi phí di chuyển từ Mountain View đến Tokyo dọc theo lộ trình đề xuất (chúng ta gọi đây là robot "tốt"). Khi robot này đi qua một cạnh, nó sẽ luôn lấy chi phí tối thiểu - robot này đại diện cho con đường ngắn nhất mà chúng ta hy vọng xây dựng. Robot kia bắt đầu từ Mountain View và cố gắng đến London qua một con đường khác. Chúng ta gọi đây là robot "xấu" và sẽ cố gắng ép nó mất nhiều thời gian nhất có thể. Câu hỏi là liệu chúng ta có thể làm cho robot tốt nhanh ít nhất bằng robot xấu hay không (robot xấu rõ ràng có thể nhanh bằng cách chỉ cần đi theo robot tốt).

Chúng ta đã đặt chi phí cho các cạnh \(E_1\) đến \(E_p\) thành các giá trị thấp nhất (\(a_i\)). Vì mục tiêu của chúng ta là làm cho robot tốt di chuyển nhanh và robot xấu di chuyển chậm, một cách tiếp cận ngây thơ là chỉ đơn giản cho robot tốt trả chi phí thấp cho tất cả các cạnh khác, và robot xấu trả chi phí cao (\(b_i\)). Tuy nhiên, chúng ta vẫn sẽ gặp vấn đề trong mô hình này: Nếu hai robot đi qua cùng một cạnh, chúng thực tế đang lấy các chi phí khác nhau, điều này không thể xảy ra trong một cấu hình cố định.

Tuy nhiên, lưu ý rằng hai robot đang đi trên cùng một đồ thị. Do đó, nếu chúng đến cùng một nút ở các thời điểm khác nhau, robot đến sớm hơn sẽ luôn đánh bại robot kia nếu đường ngắn nhất đi qua nút đó, vì nó luôn có thể đi theo lộ trình của robot kia. Điều này có nghĩa là robot đến sau không có mục đích gì khi thăm nút này cả. Vì các trường hợp hòa được giải quyết có lợi cho robot tốt, chúng ta có thể chỉ cần giảm khoản chấp của robot tốt đi \(0.5\) để tránh bất kỳ trường hợp hòa nào.

Vì vậy, chúng ta có thể giải quyết bài toán bằng một lần chạy thuật toán Dijkstra duy nhất cho mỗi tiền tố. Chúng ta bắt đầu với hai điểm xuất phát - một ở Mountain View tại thời điểm \(0\), và điểm kia ở Tokyo với thời điểm bằng chi phí di chuyển dọc theo lộ trình đề xuất đến Tokyo trừ đi \(0.5\). Khi xử lý một nút, chúng ta tính toán chi phí của các cạnh đi ra như sau:

• Nếu cạnh là một trong \(E_1, \dots, E_p\), chúng ta lấy chi phí thấp (\(a_i\)).
• Nếu nút hiện tại được xử lý vì robot tốt đã đến đó (chúng ta biết điều này vì chi phí của nút hiện tại không phải là số nguyên, nó kết thúc bằng \(.5\)), chi phí là chi phí thấp (\(a_i\)).
• Ngược lại, chúng ta đang xử lý nút vì robot xấu đã đến đó, và chi phí là chi phí cao (\(b_i\)).

Vì thuật toán Dijkstra chỉ thăm một nút một lần để xử lý các cạnh đi ra, chúng ta sẽ không bao giờ có trường hợp một robot thăm một nút mà robot kia đã đến sớm hơn.

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