Test Set 1

Vì mỗi tour chỉ được đi một lần, hai tour đến một trại phải lần lượt nối với hai tour rời trại khác nhau. Mỗi trại có hai tour đến và hai tour đi, nên có đúng hai cách “ghép”: tour đến thứ nhất với tour đi thứ nhất và tour đến thứ hai với tour đi thứ hai, hoặc ghép chéo hai cặp đó. Có thể xem một nghiệm ứng viên là một lựa chọn Boolean tại mỗi trại. Tổng thời gian bằng tổng thời lượng mọi tour cộng tổng thời gian chờ tại các trại.

Khi đánh giá một lựa chọn, phải kiểm tra đường đi bắt đầu bằng tour xuất phát có chứa mọi tour hay không. Một đường đi trong đồ thị có thể tạo thành chu trình với ít hơn \(2C\) cạnh. Chẳng hạn, hình ở phần dưới cho thấy một cấu hình gồm ba chu trình rời nhau.

Thời gian chờ tại trại gốc được tính khác các trại còn lại, nên phải xử lý riêng. Có thể đơn giản chạy thuật toán bốn lần, ứng với bốn cặp tour “bắt đầu” và “kết thúc”.

Toàn bộ không gian lựa chọn được duyệt trong \(O(2^C)\), đủ cho \(C\le15\) của bộ nhỏ.

Cũng có thể nhìn bộ nhỏ như một trường hợp của bài toán người bán hàng (TSP). Dựng đồ thị có hướng mà mỗi tour là một đỉnh; tại mỗi trại có bốn cạnh biểu diễn các cách nối giữa tour đến và tour đi, trọng số là thời gian phải chờ để thực hiện phép chuyển đó. Ví dụ, nếu tour A đến trại \(1\) lúc 02:00 và tour B rời trại \(1\) lúc 06:00, có cạnh A đến B trọng số \(4\). Chạy TSP trên đồ thị này, vẫn xử lý riêng trại gốc, cũng cho lời giải đúng.

Test Set 2

Xét kỹ hai cách ghép tour đến và tour đi tại mỗi trại. Giả sử các tour đến lúc 13:00 và 21:00, các tour đi lúc 22:00 và 07:00, nghĩa là giữa hai giờ đến không có giờ khởi hành nào. Ghép 13:00 với 22:00 và 21:00 với 07:00 cho tổng chờ

Ghép theo cách còn lại cho

Hai cách có cùng tổng chờ; ta gọi đây là các trại tự do.

Bây giờ xét trại có tour đến lúc 11:00 và 23:00, tour đi lúc 17:00 và 08:00; sau mỗi giờ đến đều có một tour khởi hành trước giờ đến còn lại. Ghép 11:00 với 17:00 và 23:00 với 08:00 cho

Ghép ngược lại cho

lâu hơn đúng \(24\) giờ.

Trong lời giải nhỏ, ta phải bảo đảm mọi tour nằm trên đường đi bắt đầu từ trại gốc. Nếu có tour không nằm trên đường ấy, đồ thị là một tập các chu trình rời nhau. Có hai đường đi xuyên qua mỗi trại. Nếu chúng thuộc hai chu trình khác nhau, đổi cách ghép tại trại sẽ hợp nhất hai chu trình.

Ví dụ sau có \(5\) trại. Trại \(2\) và \(5\) là trại tự do; đổi ghép tại trại \(3\) hoặc \(4\) tốn thêm \(24\) giờ. Đồ thị ban đầu có ba chu trình rời. Để hợp nhất chúng, cần đổi ghép miễn phí ở trại \(5\) và đổi ghép ở trại \(3\) hoặc \(4\) với phạt \(24\) giờ. Đường màu đỏ bắt đầu và kết thúc ở trại gốc chưa đi qua trại \(5\) trước khi đổi ghép, nhưng vẫn bắt buộc phải đổi ghép tại trại \(5\).

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_aa96181e.png

Ở trạng thái ban đầu, thời gian chờ nhỏ nhất nhưng tồn tại nhiều chu trình rời nhau.

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_c8a11451.png

Sau khi đổi ghép, chỉ còn một chu trình.

Vì vậy, để giải hiệu quả, đưa mỗi tour vào cấu trúc tập hợp rời (DSU). Duyệt từng trại. Nếu trại tự do, hợp nhất cả bốn tour nối với trại vào cùng một tập — tương đương cho phép trại tự do dùng bất kỳ cách ghép nào. Nếu không, chỉ hợp nhất mỗi tour đến với tour đi tương ứng trong cách ghép có thời gian chờ nhỏ hơn. Kết quả có một tập rời cho mỗi chu trình của đồ thị.

Nếu có \(Q>1\) tập rời, vì mọi trại tự do đã được tính đến, cần đổi cách ghép ở \(Q-1\) trại, mỗi lần chịu phạt \(24\) giờ. Đề bảo đảm luôn tồn tại \(Q-1\) trại như vậy. Trại gốc vẫn cần xử lý đặc biệt; có thể chạy thuật toán cho mỗi trong bốn cách chọn tour bắt đầu và kết thúc. Tổng thời gian bằng tổng thời lượng mọi tour, cộng thời gian chờ nhỏ nhất tại mỗi trại, cộng \(24(Q-1)\) giờ phạt.

Độ phức tạp là \(O(C\alpha(C))\), trong đó \(\alpha(C)\) là hàm Ackermann ngược và cũng là chi phí khấu hao mỗi thao tác DSU.

Nội dung trên được chuyển ngữ đầy đủ từ phân tích chính thức của Google Code Jam 2017, Vòng 3, bài Mountain Tour.