Phân tích

Test Set 1

Đáp án là một hoán vị của các số từ \(1\) đến \(N\). Có thể tính chi phí của mỗi hoán vị bằng cách mô phỏng Reversort như trong phân tích bài Reversort, với độ phức tạp \(O(N^2)\).

Có \(N!\) hoán vị phân biệt kích thước \(N\) chứa mỗi số từ \(1\) đến \(N\) đúng một lần. Ta tính chi phí của từng hoán vị và trả về bất kỳ hoán vị nào có chi phí bằng \(C\). Nếu không có hoán vị như vậy, in IMPOSSIBLE. Tổng độ phức tạp là \(O(N!\cdot N^2)\).

Test Set 2

Vì \(N\) lớn trong Test Set 2, ta không thể sinh mọi hoán vị. Nhận xét chính là miền chi phí hợp lệ với một \(N\) cho trước nằm từ \(N-1\) — khi mọi thao tác đảo có chi phí nhỏ nhất là \(1\) — đến

khi mỗi thao tác đảo có chi phí lớn nhất có thể. Chi phí bằng \(N-1\) khi mảng ban đầu đã được sắp xếp. Như phần dựng dưới đây cho thấy, mọi chi phí nằm giữa hai cận này đều có thể đạt được.

Vì vậy, nếu \(C\) không nằm trong miền hợp lệ của \(N\), ta in IMPOSSIBLE. Nếu có, ta thực hiện phép dựng đệ quy sau; phép dựng đồng thời chứng minh rằng mọi chi phí trong miền đều khả thi.

Vòng lặp đầu tiên có chi phí từ \(1\) đến \(N\). Ta chọn chi phí \(x\) cho vòng này sao cho \(C-x\) nằm trong miền chi phí khả thi của một hoán vị kích thước \(N-1\). Có thể kiểm tra rằng luôn chọn được \(x\) như vậy; thậm chí có thể tính toàn bộ miền giá trị \(x\) hợp lệ bằng cách giải hệ bất đẳng thức tương ứng.

Tiếp theo, đệ quy sinh một hoán vị \(P\) kích thước \(N-1\) có chi phí \(C-x\). Cộng \(1\) vào mọi số trong \(P\), rồi chèn số \(1\) vào đầu bên trái, ta thu được một hoán vị các số từ \(1\) đến \(N\). Cuối cùng, đảo tiền tố độ dài \(x\), bởi chi phí của vòng lặp đầu tiên cần bằng \(x\).

Các bước không đệ quy cần \(O(N)\) để điều chỉnh \(P\). Ta thực hiện chúng cho mỗi kích thước, nên tổng độ phức tạp là \(O(N^2)\).

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng loại, bài Reversort Engineering.