Phân tích: Cruise Control

Đây là một bài toán đầy thách thức đòi hỏi một số hiểu biết sâu sắc và cài đặt cẩn thận!

Giải quyết tập thử nghiệm nhỏ - Mô phỏng

Hãy xem xét một chiếc xe \(A\). Nếu không có chiếc xe nào chồng lấn với \(A\) (nghĩa là không có xe nào cách \(A\) ít hơn 5 mét phía trước hoặc phía sau), thì việc \(A\) hiện đang ở làn đường nào không quan trọng, vì nó có thể chuyển làn tức thời mà không bị cản trở. Do đó, thời điểm quan trọng khi chúng ta phải đưa ra quyết định là khi \(A\) vượt qua một chiếc xe \(B\) khác phía trước nó (tức là tại thời điểm \(A\) cách \(B\) 5 mét phía sau và đang tiến lại gần), hoặc khi một chiếc xe \(C\) khác vượt qua \(A\).

Vì tất cả các xe đều đi với tốc độ không đổi, sau khi bất kỳ chiếc xe \(A\) nào vượt qua xe \(B\), xe \(B\) sẽ không bao giờ vượt qua \(A\) nữa. Điều này có nghĩa là các xe sẽ không vượt nhau quá nhiều lần trong trường hợp nhỏ - tổng số lần sẽ tối đa là số cặp xe, tức là 15. Cũng lưu ý rằng khi một chiếc xe vượt qua chiếc xe khác, chỉ có hai khả năng chúng ta cần khám phá: hoặc xe nhanh hơn đi làn phải và xe chậm hơn đi làn trái, hoặc ngược lại. Nếu cả hai khả năng đều không khả thi (vì một trong các xe không thể chuyển sang làn chúng ta muốn), thì ai đó phải tắt kiểm soát hành trình. Hai quan sát này cho phép chúng ta mô phỏng trực tiếp tất cả các khả năng.

Để thực hiện việc này, chúng ta bắt đầu bằng cách tìm tất cả các thời điểm mà hai chiếc xe sẽ chặn nhau, sau đó xem xét chúng theo thứ tự từ sớm nhất. Bất cứ khi nào hai xe gặp nhau, chúng ta kiểm tra xem chúng hiện đang ở làn nào và liệu chúng có thể chuyển sang làn kia hay không. Nếu cả hai xe đều có thể chuyển làn, chúng ta có hai khả năng và rẽ nhánh để khám phá cả hai. Nếu một trong các xe bị chặn, chúng ta chỉ có một khả năng - chiếc xe tự do chuyển làn phải đi vào làn trống, và chúng ta tiếp tục mà không rẽ nhánh. Điều tương tự cũng xảy ra nếu cả hai xe đều bị chặn nhưng ở các làn khác nhau. Nếu hai xe bị chặn trong cùng một làn, chúng ta biết ai đó phải tắt kiểm soát hành trình và trả về thời gian hiện tại từ nhánh này. Cuối cùng, nếu chúng ta xử lý tất cả các sự kiện vượt xe mà vẫn không ai cần tắt kiểm soát hành trình, chúng ta đã tìm thấy cách để mọi người lái xe mãi mãi - chúng ta đã biết câu trả lời cho toàn bộ bộ thử nghiệm!

Vì chúng ta muốn mọi người tiếp tục mà không tắt kiểm soát hành trình càng lâu càng tốt, trong trường hợp có hai nhánh, chúng ta nên chọn nhánh trả về giá trị cao hơn. Vì chúng ta rẽ nhánh tối đa 15 lần và có thể kiểm tra xem một chiếc xe có thể chuyển làn hay không đơn giản bằng cách xem xét tất cả các xe khác, giải pháp của chúng ta sẽ dễ dàng chạy kịp thời gian.

Giải quyết tập thử nghiệm lớn - Trì hoãn lựa chọn

Chiến lược trước đó rõ ràng sẽ không hiệu quả cho tập thử nghiệm lớn. Với 50 xe, có thể có 1225 lần chặn nhau, và không đời nào bạn có thể thử \(2^{1225}\) khả năng khác nhau! Chúng ta sẽ phải trì hoãn việc đưa ra lựa chọn càng lâu càng tốt để tránh rẽ nhánh.

Giả sử chúng ta có hai xe: \(A\) và \(B\), và \(A\) vượt qua \(B\) tại một thời điểm nào đó. Bây giờ chúng chạy cạnh nhau với \(A\) dần vượt lên \(B\) theo thời gian. Một trong số chúng đang chiếm làn phải và một đang chiếm làn trái, nhưng chúng ta không biết cái nào là cái nào. Nếu \(A\) vượt lên trước \(B\) hoàn toàn 5 mét, nó lại tự do chuyển làn, và lựa chọn - nó đã vượt qua \(B\) ở phía nào - trở nên không còn quan trọng.

Mặt khác, hãy xem điều gì xảy ra khi một chiếc xe thứ ba, \(C\), xuất hiện và cố gắng vượt qua bất kỳ ai đang ở phía sau (giả sử vẫn là \(A\)); hơn nữa giả sử \(C\) đang lái ở làn phải và không thể chuyển sang làn trái. Điều này có nghĩa là nếu \(A\) ở làn phải, chúng ta sẽ phải tắt kiểm soát hành trình ngay bây giờ; mặt khác nếu \(A\) ở làn trái, chúng ta sẽ có thể tiếp tục lái xe thêm một lúc nữa. Điều này có nghĩa là đặt \(A\) vào làn trái là một lựa chọn tốt hơn hẳn.

Điều này dẫn đến ý tưởng về các lựa chọn trì hoãn. Mặc dù lựa chọn \(A\) đi làn nào đáng lẽ phải được thực hiện từ trước đó, nhưng nó chỉ trở nên quan trọng ngay bây giờ - vì vậy hãy nói rằng chúng ta chỉ tiết lộ lựa chọn của mình ngay bây giờ. Trước khi \(C\) xuất hiện, chúng ta coi \(A\) và \(B\) là ở trạng thái chưa xác định, với một trong hai xe có thể ở làn trái, và lựa chọn chính xác chỉ bị bắt buộc khi \(C\) đến (một thành viên Google làm việc cho bài toán này nói rằng nó gợi nhớ mạnh mẽ đến con mèo của Schrödinger).

Giải quyết tập thử nghiệm lớn - Các làn đường chưa xác định

Để hình thức hóa cách tiếp cận này, chúng ta sẽ nói rằng tại bất kỳ thời điểm nào, một chiếc xe hoặc ở trong một làn cố định hoặc ở trong một làn chưa xác định. Ví dụ, trong tình huống đã mô tả trước đó, xe \(C\) cố định ở làn phải, trong khi xe \(A\) và \(B\) ban đầu ở các làn chưa xác định. Khi \(C\) vượt qua \(A\), các làn của \(A\) và \(B\) trở nên cố định (tương ứng là làn trái và làn phải).

Lưu ý rằng chúng ta cũng có thêm thông tin - mặc dù \(A\) và \(B\) ở các làn chưa xác định, chúng ta vẫn biết rằng chúng ở các làn khác nhau. Trên thực tế, trạng thái của toàn bộ hệ thống có thể được mô tả tại bất kỳ thời điểm nào bằng các thông tin sau:

• Đối với mỗi xe, nó cố định ở làn phải, cố định ở làn trái hay ở làn chưa xác định.
• Đối với mỗi cặp xe ở làn chưa xác định, liệu chúng nhất thiết phải ở cùng một làn, ở các làn khác nhau hay chúng độc lập với nhau.

Tại thời điểm này, bạn có thể thắc mắc làm thế nào hai xe ở làn chưa xác định có thể bị buộc phải ở cùng một làn. Cách điều này xảy ra là có một chiếc xe thứ ba (cũng chưa xác định) chặn cả hai xe đó chuyển làn. Nếu bạn xem xét kỹ ví dụ thứ tư, bạn sẽ thấy đây chính xác là những gì xảy ra ở giây thứ 12. Các xe có vận tốc 2 và 4 ở các làn chưa xác định nhưng chúng nhất thiết phải ở cùng một làn, và vì vậy một trong số chúng phải tắt kiểm soát hành trình.

Trạng thái ban đầu của hệ thống rất dễ tính toán. Bất kỳ chiếc xe nào ban đầu nằm cạnh một chiếc xe khác đều ở trong một làn cố định (làn nó bắt đầu). Bất kỳ chiếc xe nào khác đều ở trong một làn chưa xác định và độc lập với tất cả những chiếc xe khác. Câu hỏi hóc búa là làm thế nào để cập nhật trạng thái này theo thời gian.

Giải quyết tập thử nghiệm lớn - Cập nhật trạng thái

Trạng thái thay đổi trong hai tình huống - khi hai xe đến gần nhau (và trạng thái của chúng không còn độc lập) và khi hai xe không còn gần nhau nữa. Chúng ta có thể tính toán trước tất cả các sự kiện này và sắp xếp chúng theo thời gian, giống như trong trường hợp nhỏ. Việc này mất \(O(N^2 \log N)\) thời gian.

Khi hai xe trở nên gần nhau, chúng trở nên phụ thuộc lẫn nhau - chúng phải ở các làn khác nhau. Nếu một trong số chúng có làn cố định, chiếc còn lại bây giờ cũng có làn cố định; nếu cả hai đều chưa xác định và độc lập, chúng vẫn chưa xác định, nhưng chúng phải ở các làn khác nhau. Trong các trường hợp khác, hoặc không có gì xảy ra - như khi một trong các xe cố định ở làn phải và xe kia cố định ở làn trái; hoặc ai đó phải tắt kiểm soát hành trình và chúng ta đã giải quyết xong bài toán - như khi cả hai xe bị buộc vào làn trái, hoặc cả hai đều chưa xác định nhưng chúng bị buộc phải ở cùng một làn.

Hơn nữa, khi một chiếc xe chưa xác định trở thành làn cố định, nó tác động đến tất cả các xe khác phụ thuộc vào nó - chúng cũng trở thành làn cố định. Tương tự, nếu hai xe độc lập \(A\) và \(B\) trở nên phụ thuộc lẫn nhau và chúng ta có xe \(C\) cùng làn với \(A\) và xe \(D\) khác làn với \(B\), chúng ta có thêm thông tin rằng \(C\) và \(D\) phải ở cùng một làn. Tổng quát hơn, bất cứ khi nào chúng ta có thêm thông tin do một cặp xe \(A\) và \(B\) trở nên gần nhau, chúng ta phải cập nhật thông tin về bất kỳ cặp xe \(C\) và \(D\) nào khác với \(C\) phụ thuộc vào \(A\) và \(D\) phụ thuộc vào \(B\). May mắn thay, việc cập nhật trạng thái rất đơn giản! Một mẹo hay là sử dụng \(+1\) và \(-1\) để biểu thị làn trái và làn phải; và sử dụng \(-1\) để nghĩa là hai xe ở khác làn, và \(+1\) để nghĩa là chúng ở cùng một làn (và \(0\) để nghĩa là "chưa xác định" và "độc lập"). Sau đó, ví dụ, nếu chúng ta biết rằng \(A\) ở làn phải (\(A = -1\)) và chúng ta biết rằng \(A\) và \(B\) ở các làn khác nhau (\(AB = -1\)), thì \(B\) ở làn \(A * AB = 1\) - làn trái. Hãy thử cách này và xem nó hoạt động như thế nào!

Điều gì xảy ra khi hai xe không còn gần nhau nữa? Nếu không xe nào trong số chúng có thể chuyển làn (do một số xe lân cận khác), thì không có gì xảy ra. Chúng vẫn phụ thuộc vào nhau như cũ. Thời điểm duy nhất mà điều gì đó thay đổi là khi một chiếc xe tự do chuyển làn - trạng thái của nó ngay lập tức trở thành chưa xác định và độc lập với tất cả các xe khác.

Giải quyết tập thử nghiệm lớn - Tổng hợp lại

Vậy hãy xem giải pháp sẽ hoạt động như thế nào. Đầu tiên chúng ta xác định danh sách các sự kiện (hai xe đến gần nhau hoặc rời xa nhau), được sắp xếp theo thời gian. Chúng ta cũng xác định trạng thái ban đầu của mỗi xe (ban đầu mỗi xe hoặc là làn cố định, hoặc chưa xác định và độc lập với tất cả những chiếc xe khác). Chúng ta giữ trạng thái của mỗi xe trong một mảng và thông tin phụ thuộc cho mỗi cặp xe trong một mảng hai chiều.

Đối với mỗi sự kiện khi hai xe đến gần nhau, chúng ta kiểm tra xem chúng có thể đi các làn ngược nhau hay không (nghĩa là - chúng không cùng cố định vào một làn và chúng không bị phụ thuộc để ở cùng một làn). Nếu có, chúng ta cập nhật sự phụ thuộc của chúng (và có thể cả tính cố định làn), đồng thời cập nhật sự phụ thuộc giữa tất cả các xe phụ thuộc của chúng. Việc này mất \(O(N^2)\) thời gian.

Đối với mỗi sự kiện khi hai xe không còn gần nhau, chúng ta kiểm tra xem một trong hai xe có thể chuyển làn tự do hay không. Nếu có, chúng ta đánh dấu xe đó là chưa xác định và độc lập với tất cả những chiếc xe khác. Việc này mất \(O(N)\) thời gian.

Vì chúng ta có tối đa \(O(N^2)\) sự kiện để xử lý, toàn bộ giải pháp sẽ chạy trong thời gian \(O(N^4)\), đủ nhanh cho giới hạn \(N=50\).

Giải quyết tập thử nghiệm lớn - Tối ưu hóa

Không khó để thấy rằng giải pháp chúng ta có thể được tối ưu hóa. Để làm điều này, hãy lưu ý rằng thay vì giữ (và cập nhật) ma trận phụ thuộc đầy đủ, chúng ta có thể nghĩ theo nhóm các xe, vì nếu \(A\) và \(B\) phụ thuộc và \(B\) và \(C\) phụ thuộc, thì \(A\) và \(C\) cũng phụ thuộc. Bản chất chính xác của sự phụ thuộc có thể được suy ra từ hai sự phụ thuộc kia. Do đó, chúng ta chỉ cần giữ một đại diện từ mỗi nhóm các xe phụ thuộc lẫn nhau và đối với mỗi xe trong nhóm, hãy nhớ xem nó ở cùng làn với đại diện hay ở khác làn. Khi hai nhóm hợp nhất, bây giờ chúng ta có thể hợp nhất chúng trong thời gian \(O(N)\): đầu tiên chúng ta kiểm tra xem các đại diện có ở cùng một làn hay không, sau đó chúng ta chuyển mọi người trong một trong các nhóm sang sử dụng đại diện từ nhóm kia. Điều này làm cho giải pháp của chúng ta chạy trong thời gian \(O(N^3)\). Để có thêm điểm cộng, bạn có thể muốn xem xét cách làm cho giải pháp chạy trong \(O(N^2 \log N)\).

Sự thật thú vị: Bài toán này được hình thành khi tác giả đang lái xe trên các đường cao tốc liên bang Hoa Kỳ và cảm thấy khó chịu vì phải thường xuyên tắt kiểm soát hành trình do những lựa chọn không tối ưu của những người lái xe khác, những người không thể giải quyết bài toán này.

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