Trong cả hai lời giải dưới đây, ta mô hình hóa tình huống thành một đồ thị phẳng \(G\), trong đó các đầu mút là đỉnh và các hàng rào là cạnh. Có thể dựng biểu diễn danh sách kề của đồ thị này trong thời gian gần tuyến tính theo kích thước input. Lý do là ta phải nhận diện các đầu mút trùng nhau; thao tác đó có thể thêm một thừa số logarit nếu dùng cây hoặc sắp xếp, hay một thừa số kỳ vọng là hằng số nếu dùng bảng băm.

Test Set 1

Trước hết, tạm giả sử không có thứ tự một phần bắt buộc nào (chẳng hạn khi \(K=1\)). Có nhiều thuật toán tham lam có thể tìm ra một thứ tự đúng. Ta có thể xử lý các hàng rào từ ngoài vào trong hoặc từ trong ra ngoài, khéo léo sử dụng những thuật toán kiểu bao lồi.

Mỗi cách có ưu và nhược điểm riêng, nhưng nhiều cách còn có tính chất rằng thứ tự đảo ngược của thứ tự chúng tạo ra cũng hợp lệ. Điều này đủ để xử lý \(K\) không quá 2: tìm một thứ tự tham lam; nếu nó tuân theo thứ tự một phần thì trả về nó, nếu không thì trả về thứ tự đảo ngược. Một trong hai thứ tự chắc chắn hợp lệ.

Một hướng khác, áp dụng được với một số lựa chọn tham lam, là cố định một hàng rào làm hàng rào đầu tiên rồi tiếp tục từ đó. Nếu cố định hàng rào 1 được xây đầu tiên thì thứ tự một phần chắc chắn được tôn trọng.

Sau đây là một phương án khác với các phương án vừa nêu, vì nó dễ mô tả, chứng minh và cài đặt hơn. Hãy dựng một cây khung \(T\) bất kỳ của \(G\) có chứa hàng rào 1. Xây trước tất cả hàng rào trong \(T\), theo bất kỳ thứ tự nào bắt đầu bằng hàng rào 1. Như vậy thứ tự một phần được tôn trọng.

Cho đến lúc này, các hàng rào đã xây không khép kín chu trình nào, nên việc di chuyển máy in không bị hạn chế: có thể đi tới mọi điểm không nằm trên hàng rào.

Với mỗi hàng rào \(f\) còn lại, xét chu trình được tạo thành khi thêm \(f\) vào \(T\). Chu trình đó biểu diễn một đa giác đơn. Nếu xây các hàng rào còn lại theo thứ tự tăng dần của diện tích đa giác tương ứng (phá hòa tùy ý), ta thu được một thứ tự hợp lệ.

Lý do là ta luôn có thể giữ máy in ở "phía ngoài" mọi chu trình đã khép kín. Ở bất kỳ thời điểm nào, chu trình sắp được khép kín có diện tích không nhỏ hơn mọi chu trình đã khép kín, nên nó không thể nằm bên trong bất kỳ chu trình nào trong số đó. Do đó, hàng rào dùng để khép kín nó cũng nằm ở "phía ngoài"; máy in có thể tiến sát tùy ý đến vị trí hàng rào và tìm được một điểm để xây hàng rào ấy.

Thuật toán này có thể được cài đặt trong thời gian bậc hai. Dựng cây khung mất thời gian tuyến tính. Với mỗi hàng rào ngoài cây khung, ta dùng thời gian tuyến tính để tính diện tích đa giác, nên tổng thời gian là bậc hai. Cuối cùng chỉ cần sắp xếp các hàng rào còn lại, nhanh hơn bậc hai.

Test Set 2

Test Set 2 đòi hỏi một ít kiến thức lý thuyết. Hãy dựng đồ thị đối ngẫu của \(G\) và gọi nó là \(H\). Hơn nữa, với một tập hàng rào \(S\), ký hiệu \(G(S)\) là đồ thị tương ứng và \(H(S)\) là đồ thị đối ngẫu của nó.

Theo quy ước thông thường, khi nói đến các mặt của \(G\) hoặc các đỉnh của \(H\), ta tính cả mặt ngoài, tức mặt duy nhất có diện tích vô hạn.

Khi công việc kết thúc, máy in nằm lại trong một mặt của \(G\), tức tại một đỉnh của \(H\), và hàng rào cuối cùng được xây là một trong các cạnh kề với mặt đó. Bây giờ xét thứ tự xây theo chiều ngược. Ngay trước khi xây hàng rào cuối cùng \(f\), máy in nằm trong một mặt của \(G(F-\{f\})\), với \(F\) ở đây là tập tất cả hàng rào.

Với mọi tập \(S\) và mọi hàng rào \(f\), \(G(S)\) có quan hệ chặt chẽ với \(G(S-\{f\})\), và tương ứng \(H(S)\) có quan hệ chặt chẽ với \(H(S-\{f\})\). Đồ thị \(G(S-\{f\})\) thu được bằng cách xóa \(f\) khỏi \(G(S)\), đồng thời có thể xóa cả các đầu mút của \(f\) nếu chúng trở thành đỉnh cô lập. Tương ứng, \(H(S-\{f\})\) hoặc bằng \(H(S)\), hoặc thu được bằng cách nhập hai đỉnh của \(H(S)\) thành một: trong \(G(S)\), \(f\) có thể chỉ kề một mặt hoặc kề hai mặt, lần lượt dẫn đến việc \(H\) không đổi hoặc hai đỉnh của \(H\) được nhập lại.

Quay lại \(G(F-\{f\})\), hàng rào áp chót \(g\) phải là một hàng rào kề với một mặt kề \(f\). Hàng rào ngay trước \(g\) phải kề với một mặt kề \(f\) hoặc \(g\), và cứ tiếp tục như vậy.

Vì thế, mọi thứ tự hàng rào khả dĩ tương ứng với một phép tìm kiếm trên đồ thị \(X\): mỗi hàng rào là một đỉnh của \(X\), và hai hàng rào kề nhau trong \(X\) nếu chúng cùng kề với một mặt của \(G\). Một phép tìm kiếm trên đồ thị là một thứ tự các đỉnh sao cho mọi tiền tố của thứ tự đều liên thông. Tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu là hai ví dụ, nhưng không phải là những phép tìm kiếm duy nhất.

Sau khi đồng nhất các thứ tự hợp lệ với các phép tìm kiếm trên đồ thị, ta có thể tham lam dựng một thứ tự tôn trọng thứ tự một phần. Từ đây trở đi, ta sẽ dựng thứ tự đảo ngược của output. Cố định hàng rào đầu tiên \(f\) của thứ tự đang dựng, rồi duy trì các hàng rào đã với tới được.

Mọi hàng rào đã với tới nhưng không nằm trong thứ tự một phần có thể được thêm ngay vào thứ tự: thao tác này chỉ làm thêm nhiều hàng rào trở nên với tới được và không thể vi phạm thứ tự một phần. Còn các hàng rào nằm trong thứ tự một phần phải được thêm đúng thứ tự; việc này cũng có thể thực hiện tham lam. Nếu ở một thời điểm nào đó, tất cả hàng rào với tới được đều thuộc thứ tự một phần nhưng không hàng rào nào là phần tử cần lấy tiếp theo, lựa chọn \(f\) đã thất bại và ta phải thử một \(f\) khác.

Các lập luận trên cho thuật toán bậc hai. Dựng \(G\) rồi \(H\) mất thời gian gần tuyến tính. Dựng \(X\) từ \(H\) mất thời gian bậc hai vì \(X\) có thể có số cạnh bậc hai. Thuật toán tham lam mất thời gian hằng số cho mỗi hàng rào được thêm vào thứ tự; ta có thể phải thử số lượng tuyến tính các hàng rào bắt đầu \(f\), nên phần này cũng mất tổng thời gian bậc hai.

Thực ra có thể cải thiện toàn bộ thuật toán xuống gần tuyến tính. Không cần dựng \(X\) tường minh: có thể dùng \(H\) để biểu diễn \(X\) ngầm và chỉ duyệt các quan hệ kề dẫn đến những hàng rào chưa được với tới; nhờ đó loại bỏ chi phí bậc hai của việc dựng \(X\).

Đối với việc thử mọi \(f\), ta có thể chứng minh rằng cố định \(f\) là hàng rào đầu tiên trong thứ tự một phần — tức hàng rào \(K\), vì ta đang dựng thứ tự đảo ngược — luôn là tối ưu. Trong một phép tìm kiếm hợp lệ trên \(X\) tôn trọng thứ tự một phần, đảo ngược tiền tố kết thúc tại hàng rào \(K\) vẫn tạo thành một phép tìm kiếm hợp lệ, vẫn tôn trọng thứ tự một phần và có hàng rào \(K\) đứng đầu.

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