Test Set 1

Trong Test Set 1, số điểm đủ nhỏ để thử mọi cách chia chúng thành các tam giác. Với tối đa \(N=12\) điểm, có \(12!/(3!^4\cdot4!)=15400\) cách tạo \(3\) hoặc \(4\) tam giác, còn ít cách hơn để tạo \(1\) hoặc \(2\) tam giác, và đúng một cách tạo \(0\) tam giác. Vì vậy, số trường hợp cần thử nhỏ hơn \(4\cdot15400+1=61601\).

Với mỗi trường hợp, cần kiểm tra từng tam giác có hợp lệ hay không, tức các đỉnh không thẳng hàng, và từng cặp tam giác có thỏa định nghĩa trong đề hay không. Do số tam giác rất nhỏ, phần cài đặt khá dài nhưng thời gian tính toán không lớn.

Test Set 2

Ta giải bài bằng cách chứng minh mang tính xây dựng định lý sau: một tập \(S\) gồm \(3t\) điểm có thể được chia thành \(t\) tam giác thỏa các điều kiện của đề khi và chỉ khi nó không chứa một tập con gồm \(2t+1\) điểm thẳng hàng.

Trường hợp \(t=1\) là hiển nhiên. Với \(t>1\), xét ba trường hợp. Gọi \(C\) là tập con lớn nhất của \(S\) gồm các điểm thẳng hàng.

• Nếu \(|C|<2t-1\), ta tìm một tam giác được một đường thẳng ngăn cách khỏi mọi điểm còn lại, rồi giải đệ quy trên ít điểm hơn. Một tam giác dùng nhiều nhất hai điểm của \(C\), nên sau khi bỏ nó, số điểm thẳng hàng còn lại không vượt giới hạn cho phép.

Một cách tìm tam giác như vậy là lấy hai điểm lớn nhất theo thứ tự từ điển (sắp theo hoành độ, nếu bằng nhau thì theo tung độ), gọi là \(v\) và \(w\). Sau đó tìm hai điểm thứ ba \(x_1\) và \(x_2\) lần lượt làm nhỏ nhất và lớn nhất góc \(vwx_i\), phá hòa bằng khoảng cách \(|wx_i|\). Chọn \(x_1\) nếu góc nhỏ hơn \(\pi\), ngược lại chọn \(x_2\); trong trường hợp sau, góc \(vwx_2\) chắc chắn lớn hơn \(\pi\). Đường thẳng \(wx_i\) tách ba điểm này khỏi mọi điểm khác. Có thể có thêm điểm nằm trên đường thẳng đó, nhưng \(w\) và \(x_i\) là hai điểm cực biên trên nó, nên mọi tam giác dựng từ các điểm còn lại sẽ không cản trở tam giác này.

• Nếu \(|C|\ge2t-1\) và \(|C|\ne3\), gọi \(B,D\subseteq S\) là các tập điểm ở hai phía của đường thẳng đi qua \(C\). Nếu cả hai đều không rỗng, giả sử không mất tính tổng quát rằng \(|B|\le|D|\). Lấy \(2|B|\) điểm lớn nhất theo thứ tự từ điển trong \(C\), gọi tập này là \(C'\), rồi ghép chúng với \(B\) để giải đệ quy hai tập \(B\cup C'\) và \(D\cup(C\setminus C')\). Có một đường phân cách hai tập đó, nên hai lời giải đệ quy không cản trở nhau.

Nếu một trong \(B,D\) rỗng, lấy hai điểm lớn nhất theo thứ tự từ điển trong \(C\) và ghép với một điểm còn lại như ở bước trước, rồi giải phần còn lại bằng đệ quy. Nếu \(|C|=2\), thao tác này tạo đúng một tam giác. Nếu không, \(|C|>3\); sau khi bỏ hai điểm khỏi \(C\) và một điểm khỏi \(S\setminus C\), điều kiện của định lý vẫn đúng cho các điểm còn lại.

• Trường hợp còn lại là \(|C|=3\) và \(t=2\). Nếu bao lồi của \(S\) có \(3\) đỉnh, dùng ba đỉnh đó làm một tam giác và ba điểm còn lại làm tam giác kia. Nếu bao lồi có \(5\) hoặc \(6\) đỉnh, nó chứa ít nhất hai điểm của \(C\); dùng hai điểm đó cùng một điểm trung gian hoặc kề để tạo một tam giác, rồi dùng phần còn lại tạo tam giác kia. Nếu bao lồi của \(S\) có \(4\) đỉnh, cần xét một vài trường hợp tùy vị trí hai điểm còn lại, nhưng trường hợp nào cũng giải được. Khi cài đặt, do số lượng rất nhỏ, chỉ cần thử mọi cách ghép.

Từ chứng minh trên, làm như sau: tìm một tập điểm thẳng hàng lớn nhất \(C\) trong dữ liệu vào. Nếu \(|C|\) lớn hơn \(\lceil2N/3\rceil\), bỏ qua một số điểm của \(C\) để kích thước còn đúng bằng giá trị đó. Tiếp theo, bỏ qua một số điểm không thuộc \(C\) để tổng số điểm không bị bỏ qua là bội của \(3\). Ghép toàn bộ các điểm này thành tam giác theo cách xây dựng ở trên. Nếu luôn giữ các điểm theo thứ tự từ điển, mỗi bước tìm tam giác mới có thể thực hiện trong thời gian tuyến tính, ngoại trừ việc sau mỗi bước thuộc trường hợp thứ nhất có thể phải tính lại \(C\).

Có thể tăng tốc việc tìm tập thẳng hàng lớn nhất bằng ba kỹ thuật. Hai kỹ thuật đầu cải thiện độ phức tạp nhưng có thể khá chậm trong thực tế vì hằng số lớn và nhiều thừa số logarit, tùy cách cài đặt:

• Tính tất cả các tập điểm thẳng hàng, duy trì chúng và một hàng đợi ưu tiên để nhanh chóng lấy tập lớn nhất. Có \(N\) lần xóa điểm, mỗi lần cập nhật nhiều nhất \(N-1\) tập, nên tổng cộng có \(O(N^2)\) cập nhật. Nếu các tập là danh sách liên kết và hàng đợi ưu tiên được cài trên mảng (kích thước chỉ từ \(1\) đến \(N\)), về lý thuyết tổng thời gian là \(O(N^2)\). Tuy nhiên, riêng việc tính \(C\) ban đầu cho toàn bộ dữ liệu đã cần \(O(N^2\log N)\) phép toán, nên người cài đặt có thể bị hấp dẫn bởi những cấu trúc kém hiệu quả hơn nhưng nhanh viết hơn.

• Nếu \(|C|\) nhỏ hơn nhiều so với ngưỡng khiến ta rời trường hợp thứ nhất, có thể thực hiện nhiều bước của trường hợp thứ nhất mà chưa tính lại \(C\). Có thể chứng minh cách này chỉ cần tính lại một số lần theo logarit. Dù vậy, tổng độ phức tạp vẫn là \(O(N^2\log^2N)\) và hằng số lớn, vì kích thước dữ liệu trước mỗi lần tính lại không giảm một nửa mà trong trường hợp xấu nhất chỉ giảm khoảng \(1/5\).

Cách thứ ba đơn giản và nhanh hơn nhiều: hoàn toàn không tính \(C\) một cách tường minh. Cứ thực hiện trường hợp thứ nhất cho đến khi phát hiện mọi điểm còn lại thẳng hàng; điều này xảy ra khi cả \(vwx_1\) và \(vwx_2\) đều là góc phẳng. Khi đó, hoàn tác vừa đủ số tam giác được tạo gần nhất để tập điểm thẳng hàng vừa nhận diện đủ lớn và không còn thuộc trường hợp thứ nhất, rồi tiếp tục bằng trường hợp thứ hai và thứ ba. Tổng độ phức tạp là \(O(N^2)\); vì không dùng cấu trúc phức tạp hay logarit cơ số nhỏ, cận này cũng không che giấu hằng số lớn.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2022, World Finals.