Test Set 1

Trong Test Set 1, số lượng cột đủ nhỏ để dùng vét cạn. Đề bài bảo đảm có ít nhất một thứ tự đúng, nên ta có thể thử mọi thứ tự khả dĩ — nhiều nhất \(10! = 3628800\) — cho đến khi tìm được một thứ tự đúng.

Để kiểm tra một thứ tự, ta xét mọi tiền tố có độ dài ít nhất 3, dựng mái được xác định bởi ba cột cuối cùng của tiền tố, rồi kiểm tra rằng tất cả cột còn lại đều ở phía dưới mái. Vì đề bài bảo đảm không có ba điểm thẳng hàng, mọi tập gồm ba điểm xác định duy nhất một mặt phẳng.

Có nhiều cách kiểm tra một mái có hợp lệ hay không. Sau đây là một cách chỉ dùng số học số nguyên. Gọi \(p_1,p_2,\ldots,p_k\) là \(k\) điểm trong tiền tố, và gọi \(q\) là mặt phẳng chứa \(p_{k-2}\), \(p_{k-1}\) và \(p_k\). Với mỗi \(i\) từ 1 đến \(k-3\), ta cần kiểm tra xem \(p_i\) có nằm phía trên \(q\) hay không.

Ta có thể trừ \(p_k\) khỏi tất cả các điểm mà không làm thay đổi câu trả lời, nên từ đây giả sử \(p_k=(0,0,0)\). Gọi \(v\) là một vector pháp tuyến của mặt phẳng \(q\). Chiếu \(p_i\) lên \(v\) bằng tích vô hướng, rồi kiểm tra xem \(v\) và hình chiếu có nằm cùng một phía của \(q\) hay không. Nếu có thì \(p_i\) nằm phía trên \(q\); nếu không thì không.

Kiểm tra một tiền tố mất \(O(N)\) thời gian. Có \(O(N)\) tiền tố cần kiểm tra cho mỗi một trong \(N!\) thứ tự, nên cách trực tiếp có độ phức tạp \(O(N!\times N^2)\). Cách này có thể đủ nhanh hoặc không, tùy ngôn ngữ và cách cài đặt. Có thể tăng tốc theo nhiều cách:

• Sinh hoán vị bằng cách thêm từng cột một và kiểm tra mỗi tiền tố ngay khi nó vừa được sinh. Như vậy độ phức tạp giảm xuống \(O(N!\times N)\) vì một tiền tố không còn bị kiểm tra lại cho mọi hoán vị bắt đầu bằng tiền tố đó. Ngoài ra, khi gặp một tiền tố không hợp lệ, ta không lãng phí thời gian kiểm tra các hoán vị khác bắt đầu bằng tiền tố ấy; trong thực tế điều này còn có thể giảm đáng kể không gian tìm kiếm.
• Dùng quy hoạch động trên tập con để đưa độ phức tạp về khoảng \(O(2^N\times N^4)\). Tuy nhiên, cách này có thực sự nhanh hơn hay không phụ thuộc rất nhiều vào chi tiết cài đặt.

Test Set 2

Trong Test Set 2, mọi lời giải có độ phức tạp hàm mũ hoặc giai thừa theo \(N\) đều thất bại ngay từ đầu, nên ta cần một chiến lược khác. Một khả năng là giải bài toán theo chiều ngược: bắt đầu với tất cả các cột, tìm một mái hợp lệ, xóa một cột rồi lặp lại.

Để mô tả chính xác hơn, trước tiên cố định hai điểm \(q\) và \(p\) trong tập các đầu cột làm hai cột cuối cùng, theo đúng thứ tự đó. Cách chọn hai điểm này sẽ được bàn sau. Tiếp theo, đặt \(S\) là tập tất cả đầu cột ngoại trừ \(p\) và \(q\), rồi lặp các bước sau cho đến khi \(S\) rỗng:

1. Tìm một điểm \(r\) sao cho mặt phẳng chứa \(p\), \(q\) và \(r\) nằm phía trên tất cả các điểm hiện tại.
2. Xóa \(r\) khỏi tập điểm hiện tại, rồi gán \(p=q\) và \(q=r\).

Output cuối cùng là thứ tự đảo ngược của thứ tự các điểm được lấy khỏi \(S\), với \(p\) và \(q\) ở cuối.

Để thực hiện bước đầu tiên — tìm \(r\) — ta có thể thử mọi điểm trong \(S\) và dùng quy trình kiểm tra ở trên để kiểm tra điều kiện. Cách đó khiến riêng bước này mất \(O(N^2)\) thời gian.

Để cải thiện, hãy hình dung mặt phẳng chứa mái cuối cùng, nhưng hiện tại nó chỉ được đỡ bởi hai cột cố định còn lại. Ở vòng lặp đầu tiên, "mái cuối cùng" này phải tồn tại thì thuật toán mới hợp lệ; cách định nghĩa nó phụ thuộc vào cách ta chọn \(p\) và \(q\). Với lựa chọn \(p,q\) được trình bày bên dưới, sự tồn tại của một "mái cuối cùng" phù hợp là hiển nhiên.

Ta có thể quay mặt phẳng quanh trục là đoạn nối đầu mút của hai cột đó và muốn tìm một trong các cột mà mặt phẳng chạm tới đầu tiên. Có thể có nhiều nhất hai cột như vậy vì mặt phẳng có thể quay theo một trong hai hướng. Nói cách khác, ta nên chọn đầu cột \(r\) làm cực tiểu góc quay. Điều này tương đương với việc chọn \(r\) làm cực đại góc giữa một pháp tuyến của mặt phẳng chứa \(p,q,r\) và pháp tuyến của "mái cuối cùng". Nhờ đó, bước này có thể được thực hiện trong thời gian tuyến tính.

Để chọn \(p\) và \(q\) ban đầu, ta có thể thử mọi khả năng, nhưng việc đó thêm một thừa số \(N^2\) vào độ phức tạp tổng thể; hoặc ta có thể làm tốt hơn.

Đầu mút \(p\) của cột cuối cùng luôn có thể được chọn là đầu mút của một trong các cột cao nhất. Hãy tưởng tượng một mặt phẳng song song với \(z=0\) đi qua \(p\). Mặt phẳng này rõ ràng nằm phía trên hoặc chạm mọi cột khác, nhưng không bị cột nào "đâm xuyên", nên ta có thể xoay chuyển nó để tạo một mái thích hợp.

Sau đó, có thể chọn \(q\) là một cột sao cho đoạn \(pq\) tạo với mặt phẳng góc nhỏ nhất. Việc này tương tự bước trên, chỉ khác rằng ta quay mặt phẳng quanh một điểm duy nhất \(p\) cho đến khi nó chạm một cột khác \(q\). Ta có thể dùng chính phương pháp so sánh góc với một mặt phẳng đã mô tả ở đoạn trước. Tìm \(q\) chỉ tốn một lần quét tuyến tính, rồi ta chỉ phải chạy quy trình lặp cho một cặp duy nhất. Với lựa chọn \(p,q\) này, "mái cuối cùng" có một lựa chọn tự nhiên rõ ràng: chính là mặt phẳng tưởng tượng đã được quay để tìm \(q\).

Cài đặt tối ưu các ý tưởng trên cho một thuật toán bậc hai, cũng là lời giải chủ đích. Tùy vào những tối ưu nào bị bỏ qua, độ phức tạp có thể nằm trong khoảng từ \(O(N^2)\) đến \(O(N^5)\). Cùng với hệ số hằng của cách cài đặt và ngôn ngữ được chọn, điều này quyết định lời giải vượt qua cả hai Test Set, chỉ Test Set 1, hay không Test Set nào.

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