Test Set 1 (Visible)

Ta có \(2N\) điểm cần ghép thành \(N\) đoạn thẳng sao cho mọi đoạn đôi một giao nhau; khi đó tập đoạn là tráng lệ.

Kéo dài một đoạn \(S\) thành đường thẳng \(L\) chia mặt phẳng thành hai nửa. Trong một tập tráng lệ, vì \(S\) giao mọi đoạn khác, mỗi đoạn kia có một đầu ở mỗi phía của \(L\); không điểm nào khác nằm trên \(L\) do không có ba điểm thẳng hàng. Vì vậy, nếu chọn điểm đầu vào \(P\), nó phải ghép với điểm \(Q\) sao cho đường qua \(P,Q\) để lại đúng cùng số điểm ở hai phía. Điều đó gợi ý: chọn \(P\), tìm một \(Q\) thỏa điều kiện, ghép chúng, rồi lặp. Nhưng nếu có nhiều \(Q\) thì sao?

Ta xử lý bằng cách chọn \(P\) thông minh. Chọn một điểm trái nhất. Mọi ứng viên \(Q\) nằm trong nửa mặt phẳng bên phải của đường thẳng đứng qua \(P\) (có thể có nhiều nhất một điểm khác trên đường này). Xét một đường qua \(P\) quay theo chiều kim đồng hồ từ phương thẳng đứng đến phương thẳng đứng sau khi quay \(180^\circ\). Ban đầu không có điểm nào ở phía trái vì \(P\) là điểm trái nhất. Trong lúc quay, đường lần lượt quét qua mọi điểm, mỗi lần chuyển đúng một điểm từ phía này sang phía kia vì không có ba điểm thẳng hàng. Do đó có đúng một thời điểm đường chứa \(P\) và thêm một điểm, đồng thời để \(N-1\) điểm ở mỗi phía.

Nếu sắp mọi điểm khác \(P\) theo góc mà chúng tạo với \(P\), lấy phương thẳng đứng làm góc 0, thì điểm nằm trên đường cân bằng chính là trung vị. Như vậy điểm trái nhất \(P\) có đúng một lựa chọn \(Q\). Xóa cả hai và tiếp tục.

Thuật toán có \(N\) vòng; mỗi vòng tìm điểm trái nhất và sắp \(O(N)\) điểm theo góc. Có thể so sánh góc bằng cosin mà không làm mất độ chính xác trong thời gian hằng số. Chọn trung vị và xóa cặp tốn \(O(N)\) hoặc tốt hơn. Tổng thời gian là \(O(N^2\log N)\), đủ cho Test Set 1. Dùng thuật toán tìm trung vị tuyến tính thay cho sắp xếp sẽ giảm thành \(O(N^2)\), nhưng trên thực tế sắp xếp có thể nhanh hơn do hằng số nhỏ.

Một hệ quả của lập luận là nghiệm thực ra duy nhất. Hơn nữa, bất kỳ điểm nào trên bao lồi cũng có tính chất như điểm trái nhất, vì định nghĩa bất biến qua phép quay và có thể quay hệ tọa độ để một điểm bao lồi trở thành trái nhất. Dù vậy, điểm trái nhất dễ tìm nhất.

Test Set 2 (Hidden)

Có một hướng khác cần thêm một chứng minh, cho thuật toán Test Set 1 hơi đơn giản hơn và quan trọng nhất là tiến gần hơn tới Test Set 2.

Quan sát then chốt: nếu một tập \(2N\) điểm có cách ghép tráng lệ thì với mọi điểm \(P\) trong tập, không riêng điểm trên bao lồi, có đúng một \(Q\) sao cho đường qua \(P,Q\) chia đều các điểm còn lại. Sự tồn tại theo ngay từ bố trí tráng lệ. Ta cần chứng minh không thể có hơn một.

Giả sử \(P\) có hai điểm \(Q_1,Q_2\) sao cho cả hai đường \(PQ_i\) đều chia đều các điểm khác. Không mất tính tổng quát, \(Q_1\) là điểm thực sự ghép với \(P\) trong bố trí tráng lệ. Hai đường chia mặt phẳng thành bốn miền; gọi tập điểm trong các miền theo thứ tự là \(A,B,C,D\), không tính \(P,Q_1,Q_2\).

Mọi điểm trong \(A\) phải ghép với một điểm trong \(C\) để đoạn tạo ra cắt \(PQ_1\); tương tự, mọi điểm trong \(D\) phải ghép với một điểm trong \(B\). Vì thế \(|A|\le|C|\) và \(|B|\le|D|\). Một phía của đường \(PQ_2\) có \(|A|+|D|\) điểm, phía kia có \(|B|+|C|+1\) điểm. Nhưng

mâu thuẫn với giả sử \(PQ_2\) chia đều. Vậy \(Q\) là duy nhất với mọi \(P\).

Quan sát này tự nó chỉ loại bước “tìm điểm trái nhất”, không đổi độ phức tạp. Cải tiến quyết định là thu nhỏ nhanh tập điểm cần xét. Sau khi ghép \(M\) cặp, các đường qua mỗi cặp chia mặt phẳng thành \(2M\) miền; chỉ các miền ngoài, tức miền không bị chặn, còn có thể chứa điểm chưa ghép. Mỗi điểm phải ghép với một điểm ở miền đối diện để đoạn mới cắt mọi đường cũ — đây là điều kiện cần để cắt mọi đoạn.

Khi tạo một cặp mới, đúng hai miền bị chia đôi. Thay vì xóa cặp rồi tiếp tục trên toàn bộ tập, ta đệ quy trên hai bài toán riêng. Nếu hai tập \(X,Y\) ở các miền đối diện, sau khi ghép một cặp chúng tách thành \(X_1,X_2\) và \(Y_1,Y_2\). Khi các miền xuất hiện theo thứ tự kim đồng hồ \(X_1,X_2,Y_1,Y_2\), ta giải \(X_1\) với \(Y_1\) độc lập với \(X_2\) với \(Y_2\).

Còn phải bảo đảm đường mới chia \(X,Y\) tương đối cân bằng. Nếu buộc chọn \(P\) trên bao lồi của \(X\), \(Y\) hoặc \(X\cup Y\), điều đó có thể bất khả thi: mọi cặp như vậy có thể để gần như toàn bộ điểm về một phía. Đây là lý do cần tính chất “mọi điểm” vừa chứng minh.

Sắp mọi cặp khả dĩ nối một điểm của \(X\) với một điểm của \(Y\) theo hệ số góc đoạn nối. Cặp đầu và cuối chia chúng thành một tập rỗng và một tập \(|X|-1\) điểm, vì \(|X|=|Y|\). Cặp thứ hai và áp cuối chia thành 1 và \(|X|-2\); tổng quát, cặp thứ \(i\) chia thành \(i-1\) và \(|X|-i\). Vì vậy, nếu chọn ngẫu nhiên, cây đệ quy giống quicksort và kỳ vọng đủ cân bằng.

Phần không đệ quy trên một tập kích thước \(M\) tốn \(O(M\log M)\); tính các phân hoạch chỉ thêm thời gian tuyến tính. Do đó độ phức tạp kỳ vọng của toàn thuật toán đệ quy là \(O(N\log^2N)\).

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2019, Chung kết thế giới, bài Juggle Struggle: Part 1; kho Google Coding Competitions (Apache-2.0).