Phân tích

Trong bài toán này, chúng ta quan tâm đến việc tìm thời gian tối đa chúng ta có thể lái xe ngược chiều trong một vòng xuyến giao thông. Đối với các bộ test nhỏ, kích thước của dữ liệu đầu vào đủ nhỏ để thử tất cả các giao lộ có thể, thời gian bắt đầu, và kiểm tra độ dài quãng đường lái xe mà không chạm vào bất kỳ xe nào khác.

Đối với các bộ test lớn, cách tiếp cận trên không đủ tốt do \(N\) và \(X\) cực lớn (lên đến \(10^{10}\)). Do đó, để giải quyết các bộ test lớn, chúng ta chuyển đổi bài toán sang mặt phẳng 2 chiều với các trục là giao lộ và thời gian. Khi đó, mỗi chiếc xe có thể được biểu diễn dưới dạng các đoạn thẳng; chiếc xe của bạn sẽ được biểu diễn dưới dạng một đoạn thẳng vuông góc với các đoạn thẳng tạo bởi các xe khác. Hình 1 cho thấy trường hợp mẫu thứ hai. Các đoạn thẳng tương ứng với các xe khác nhau được ký hiệu bằng các màu khác nhau trong khi đoạn thẳng đứt nét màu đen tương ứng với xe của bạn. Lưu ý rằng vì các giao lộ nằm trong một vòng xuyến, chúng ta thể hiện nó bằng cách lặp lại giao lộ 5 và 1 ở hai đầu trong Hình 1.

Hình 1

Vì vậy, bài toán có thể được phát biểu lại như sau: cho một tập hợp các đoạn thẳng, hãy tìm độ dài tối đa có thể của một đoạn thẳng vuông góc mà không chạm vào bất kỳ đoạn thẳng nào khác. Lưu ý rằng nếu hai đoạn thẳng có một điểm chung thì các xe tương ứng sẽ chạm nhau.

Để giải quyết bộ test lớn, cần nhận thấy rằng một đoạn thẳng có độ dài tối đa có thể được chọn sao cho nó đi gần một trong các điểm đầu mút của một đoạn thẳng khác. Bằng cách "gần", chúng ta có nghĩa là khoảng cách \(= 1\) trong một trong các trục. Thật vậy, nếu chúng ta có một đoạn thẳng có độ dài tối đa mà không đi gần một trong các điểm đầu mút, chúng ta luôn có thể di chuyển nó sao cho nó đạt được điều đó, xem Hình 2 để biết ví dụ.

Hình 2

Hình 3

Khẳng định này cũng đúng trong các ví dụ như trong Hình 3 vì các giao lộ được sắp xếp theo kiểu vòng tròn và đoạn thẳng nghiệm nằm gần điểm đầu mút trên cùng bên phải được chỉ ra bằng mũi tên.

Hình 4

Do đó, chúng ta lưu ý rằng những thay đổi về độ dài của các đoạn thẳng xảy ra gần các điểm đầu mút này. Vì vậy, để giải quyết bài toán, chúng ta cần duyệt qua tất cả các điểm đầu mút của các đoạn thẳng xe và xem xét vùng lân cận của nó (\(-1\) và \(+1\) trong cả hai trục). Lưu ý rằng chúng ta cũng cần xem xét các đoạn thẳng đi qua các điểm đầu mút \(+/-(1,1)\), một ví dụ được trình bày trong Hình 4. Sau đó, chúng ta có thể tính toán tất cả các đoạn thẳng đi qua các điểm gần này và chọn đoạn thẳng dài nhất làm câu trả lời.

Đối với mỗi điểm ứng viên như vậy, chúng ta cần kiểm tra xem một đoạn thẳng đi qua điểm ứng viên có thể kéo dài bao xa lên trên và xuống dưới mà không chạm vào các đoạn thẳng khác. Điều này có thể được thực hiện đơn giản bằng cách duyệt qua tất cả các đoạn thẳng xe và kiểm tra xem đoạn thẳng ứng viên của chúng ta có giao với chúng hay không và ở đâu.

Độ phức tạp

Độ phức tạp của thuật toán này là \(O(C^2)\), đủ để giải quyết trường hợp lớn với \(C \le 1000\).

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