Test Set 1 (Hiển thị)

Trước hết, hãy phân tích chính xác bài toán yêu cầu tìm gì. Ta cần xác định các tập biển báo liên tiếp, trong đó mỗi tập được định nghĩa bởi bốn biến:

1. Chỉ số của biển đầu tiên trong tập, \(i\) (lấy vào).
2. Chỉ số của biển cuối cùng trong tập, \(j\) (không lấy vào).
3. Đích đến dành cho người đi về hướng đông, \(M\).
4. Đích đến dành cho người đi về hướng tây, \(N\).

Để một tập hợp lệ, mỗi biển trong tập phải nói đúng với người đi về hướng đông, người đi về hướng tây, hoặc cả hai. Với bốn biến trên, ta có thể kiểm tra tính hợp lệ của một tập biển trong \(O(j-i)\) thời gian. Ta có thể chặn số giá trị khả dĩ của \(M\) và \(N\) bởi \(S\), bằng cách lấy tập hợp tất cả đích đến hướng tây hoặc hướng đông được ít nhất một biển hiển thị. Vì \(i\) và \(j\) cũng bị chặn bởi \(S\), lời giải này cần \(O(S^5)\) thời gian, chưa đủ cho Test Set 1.

Để cải thiện vét cạn, ta có thể chọn \(M\) và \(N\) khéo léo hơn. Biển đầu tiên trong một tập cung cấp rất nhiều thông tin: cụ thể, nó xác định một trong \(M\) hoặc \(N\) phải bằng gì (một trong hai đích trên biển, nếu không biển đó không thể thuộc tập). Giả sử cố định \(M\) theo biển đầu tiên. Ta đi qua các biển còn lại trong tập cho đến khi gặp một biển có đích hướng đông khác \(M\); dùng đích hướng tây của biển đó làm \(N\). Tiếp tục đi cho đến khi gặp một biển không chia sẻ cả \(M\) lẫn \(N\), khi đó tập không hợp lệ, hoặc đến cuối tập, khi đó tập hợp lệ. Ta thực hiện quy trình đối xứng bằng cách cố định \(N\) theo biển đầu tiên. Thuật toán đánh giá tập “hai lượt” này chạy trong \(O(S)\) thời gian, vì kích thước mỗi tập là \(O(S)\).

Vì có \(O(S^2)\) tập biển báo và có thể kiểm tra tính hợp lệ của mỗi tập trong \(O(S)\) thời gian, ta thu được thuật toán \(O(S^3)\), đủ nhanh cho Test Set 1.

Test Set 2 (Ẩn)

Rõ ràng lời giải bậc ba không dùng được cho Test Set 2. Thực ra, một lời giải bậc hai viết bằng ngôn ngữ nhanh và cắt tỉa đủ mạnh có thể vượt qua Test Set 2. Tuy nhiên, phân tích này sẽ mô tả một lời giải \(O(S\log S)\), rồi một lời giải tuyến tính \(O(S)\); cả hai đều xử lý Test Set 2 thoải mái.

Lời giải \(O(S\log S)\) là một ứng dụng kinh điển của chia để trị. Chia đôi danh sách biển báo, ngoại trừ một biển duy nhất ở giữa mà ta gọi là biển “trung điểm”. Áp dụng đệ quy thuật toán cho nửa phía tây và nửa phía đông. Sau đó, dùng phiên bản sửa đổi của thuật toán hai lượt ở trên để tìm tập tốt nhất chứa trung điểm: trước hết, cố định \(M\) bằng đích hướng đông của biển trung điểm. Vì đang tìm các đoạn dài, ta có thể tham lam thêm nhiều biển nhất có thể vào tập. Đi từ trung điểm về cả phía tây lẫn phía đông cho đến khi ở mỗi đầu gặp một biển không có cùng đích hướng đông (giá trị \(M\)) với trung điểm. Đặt \(N_1\) bằng đích hướng tây tại biên phía tây (biển đầu tiên về phía tây không khớp \(M\)), và \(N_2\) bằng đích hướng tây tại biên phía đông (biển đầu tiên về phía đông không khớp \(M\)). Tìm \(M_1\) và \(M_2\) bằng quy trình đối xứng: quay lại trung điểm, đi về phía tây và phía đông đến khi gặp các biển không có cùng đích hướng tây (giá trị \(N\)) với trung điểm, rồi đặt \(M_1\), \(M_2\) lần lượt bằng đích hướng đông của biển tại biên phía tây và phía đông. Bây giờ có bốn cặp \(M/N\) khả dĩ: \((M,N_1)\), \((M,N_2)\), \((M_1,N)\) và \((M_2,N)\). Với mỗi cặp, ta tham lam đi về đông và tây từ trung điểm để tìm tập dài nhất chứa trung điểm. Bước “bốn lượt” của chia để trị này chạy trong thời gian tuyến tính. Khi đã tìm được tập hoặc các tập dài nhất chứa trung điểm, đồng thời tìm đệ quy được các tập dài nhất trong nửa tây và nửa đông, ta kết hợp các kết quả để thu được những tập dài nhất của toàn bộ dữ liệu. Do đó, số phép toán \(T(S)\) cần cho đầu vào kích thước \(S\) thỏa

Theo Định lý Master, \(T(S)=O(S\log S)\).

Lời giải tuyến tính thực hiện một lượt duyệt để xác định mọi đoạn dài có thể. Bắt đầu bằng cách đi xuôi từ biển đầu tiên. Duy trì hai “ứng viên”, gọi là “ứng viên \(M\)” và “ứng viên \(N\)”, với các thuộc tính sau:

• Hai đích đến \(M\) và \(N\).
• Một chỉ số start ứng với biển ở xa nhất về phía tây trong đoạn biển liên tiếp chứa biển hiện tại và thỏa \(M\) hoặc \(N\).
• Một chỉ số xstart ứng với biển ở xa nhất về phía tây trong đoạn biển liên tiếp chứa biển hiện tại mà tất cả đích hướng đông đều bằng \(M\) (đối với ứng viên \(M\)), hoặc tất cả đích hướng tây đều bằng \(N\) (đối với ứng viên \(N\)).

Với các bất biến này, tập biển bắt đầu tại start và kết thúc ngay sau chỉ số hiện tại được đảm bảo là một tập hợp lệ.

Để duy trì bất biến khi đọc một biển mới, ta dùng quy trình sau để tạo ứng viên \(M\) mới (quy trình tạo ứng viên \(N\) mới hoàn toàn đối xứng):

• Nếu đích hướng đông của biển mới bằng đích hướng đông của biển trước, sao chép ứng viên \(M\) trước đó thành ứng viên \(M\) mới.
• Nếu đích hướng đông của biển mới bằng giá trị \(M\) của ứng viên \(N\) trước đó, sao chép ứng viên \(N\) trước đó thành ứng viên \(M\) mới, rồi đặt xstart bằng chỉ số biển mới.
• Nếu không thuộc hai trường hợp trên, sao chép ứng viên \(N\) trước đó thành ứng viên \(M\) mới, đặt \(M\) bằng đích hướng đông của biển mới, đặt start bằng xstart, rồi đặt xstart bằng chỉ số biển mới.

Xét hình minh họa sau:

Hình minh họa cho thấy sáu biển được đánh chỉ số từ 0 và các đích đến của sáu biển đó. Các biển được nối bằng những đường cho biết ứng viên nào được dùng khi tính ứng viên ở bước tiếp theo. Những ứng viên sau khi đọc biển thứ sáu (chỉ số 5) được thể hiện ở cuối. Phía trên là ứng viên \(M\) với \(M=9\), \(N=2\). Ứng viên bắt đầu tại chỉ số 3 vì biển ở chỉ số 2 không có đích hướng tây hoặc hướng đông tương thích với ứng viên đó. Hình cũng cho thấy xstart=5 là đầu của chuỗi khớp đích \(M\) gần nhất, trong trường hợp này chỉ gồm biển hiện tại. Ứng viên \(N\) kéo dài ngược về chỉ số bắt đầu 1, với \(M=8\), \(N=0\).

Vì việc tính các ứng viên mới mất thời gian hằng số và ta phải đọc tuần tự từng biển, đây là lời giải \(O(S)\).

Có thêm hai mẹo hữu ích cho các lời giải bài này. Thứ nhất, ta không bao giờ cần nhớ trực tiếp \(A_i\), \(B_i\), \(D_i\); ta chỉ quan tâm đến các đích hướng tây và hướng đông. Vì vậy, có thể tính các đích đó ngay khi đọc dữ liệu rồi lưu chúng dưới dạng danh sách các cặp. Thứ hai, có rất nhiều cơ hội cắt tỉa: nếu duy trì một danh sách toàn cục các tập biển tốt nhất đã biết, ta không bao giờ phải xét các tập ứng viên nhỏ hơn tập tốt nhất hiện tại, nhờ đó có thể loại bỏ nhiều đoạn không còn cần đánh giá. Mọi lời giải được mô tả ở đây, ngoại trừ lời giải \(O(S)\), đều có thể tận dụng việc cắt tỉa.

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2018, Round 1B, bài Mysterious Road Signs.