Nhận xét mở đầu

Một số bài thi lập trình bắt nguồn từ đời thường. Bài Standing Ovation ở Vòng loại năm đó được viết trong một buổi hòa nhạc, còn Haircut ở Vòng 1A được viết khi tác giả xếp một hàng dài chờ mua bánh mì tại Google Go Cafe. Vì vậy có lẽ không bất ngờ khi bài này được lấy cảm hứng từ một chuyến đi trên đường tròn vào ngày có đông người đi bộ khác thường!

Gọi \(H\) là tổng số người đi bộ. Một nhận xét quan trọng là đáp án không thể lớn hơn \(H\): bất kể vị trí và tốc độ ban đầu của họ, Herbert có thể đi nhanh đến mức không ai kịp di chuyển xa, nhờ đó chú gặp mỗi người đúng một lần.

Một nhận xét then chốt khác: cho phép Herbert chờ hoặc thay đổi tốc độ không làm thay đổi đáp án. Nếu biết thời điểm chú đến đích, ta có thể đặt cận dưới cho số lần gặp dựa trên số người Herbert buộc phải vượt và số lần họ buộc phải vượt Herbert. Cận dưới đó đúng bằng kết quả khi Herbert đi với tốc độ không đổi, nên chờ hay đổi tốc độ không thể cải thiện lời giải.

Vì vậy, ta cần tìm một thời điểm kết thúc làm nhỏ nhất số lần gặp.

Các sự kiện của một người đi bộ

Xét một người. Vì đường đi là đường tròn và người đó đi mãi, họ liên tục trở lại điểm xuất phát của Herbert. Gọi \(X\) là thời điểm Herbert hoàn thành chuyến đi, và \(T_1,T_2,T_3,\ldots\) là các thời điểm người đó đến điểm xuất phát của Herbert.

• Nếu \(X\le T_1\), Herbert vượt người đó một lần.
• Nếu \(T_1<X<T_2\), không có lần gặp nào.
• Nếu \(T_2\le X<T_3\), người đó vượt Herbert một lần.
• Nếu \(T_3\le X<T_4\), người đó vượt Herbert hai lần.
• Và cứ tiếp tục như vậy.

Do đó, khi tăng thời điểm kết thúc của Herbert, ta đi qua nhiều "sự kiện" làm số lần gặp thay đổi: sự kiện đầu giảm số lần gặp đi 1, còn mỗi sự kiện sau tăng nó thêm 1.

Với nhiều người, mỗi người có một dãy sự kiện riêng có thể tăng hoặc giảm tổng số lần gặp.

Lời giải cho các bộ Nhỏ

Không bao giờ cần để Herbert đi lâu đến mức xét quá \(H\) sự kiện của một người: khi đó riêng số lần gặp người ấy đã ít nhất là \(H\). Vì vậy, lời giải đủ cho các bộ Nhỏ là tạo danh sách đã sắp xếp gồm \(H\) sự kiện đầu của mọi người, rồi làm như sau:

• Khởi tạo số lần gặp bằng \(H\).
• Duyệt sự kiện theo thứ tự thời gian; nếu đây là sự kiện đầu của người tương ứng thì trừ 1, ngược lại cộng 1.

Đáp án là giá trị nhỏ nhất của số lần gặp tại mọi thời điểm.

Lời giải cho bộ Lớn

Ta cần hiệu quả hơn. Chỉ có đúng \(H\) sự kiện giảm số lần gặp, còn tất cả sự kiện khác đều tăng. Vì vậy, sau khi xử lý \(2H\) sự kiện, ta sẽ không bao giờ tìm được thời điểm có ít hơn \(H\) lần gặp, và có thể dừng.

Để tránh lưu \(H^2\) sự kiện, dùng hàng đợi ưu tiên. Ban đầu đưa vào sự kiện \(T_1\) của từng người. Mỗi khi xử lý một sự kiện, thay nó trong hàng đợi bằng sự kiện kế tiếp của cùng người đó. Cách này chỉ cần \(O(H)\) bộ nhớ và \(O(H\log H)\) thời gian.

Một chi tiết tinh tế: nếu nhiều người đến điểm xuất phát của Herbert cùng thời điểm, phải xử lý các sự kiện tăng một lần gặp (các \(T_2,T_3,\ldots\)) trước các sự kiện giảm (các \(T_1\)), bởi số lần gặp chỉ thực sự giảm khi thời điểm kết thúc của Herbert lớn hơn \(T_1\).

Trong cuộc thi, 52 người đã giải thành công bộ Lớn. Lời giải của Belonogov trên bảng điểm là một ví dụ.

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