Hướng dẫn cho Google Code Jam 2021 - Minimum Sort
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Thuật toán
Truy vấn càng dài càng rẻ, nên selection sort phù hợp. Với \(i=1..N-1\), hỏi M i N để lấy vị trí \(j\) của phần tử nhỏ nhất trong hậu tố; nếu \(i\ne j\), gửi S i j. Cuối cùng gửi D.
for i := 1 to N-1
j = minimum_index_of(i, i+1, ..., N)
if i != j:
swap(i, j)
Các đoạn truy vấn dài \(N,N-1,\ldots,2\), nên tổng chi phí chính xác
\[\sum_{i=2}^N\left\lceil\frac{10^8}{i}\right\rceil.\]
Với \(N=100\), giá trị là 418737795, nhỏ hơn \(6\cdot10^8\). Có \(N-1\) truy vấn và tối đa \(N-1\) phép đổi; thời gian cục bộ \(O(N)\) ngoài giao tiếp.
Nguồn
Dựa trên phân tích chính thức của Google Code Jam 2021, Round 2 — Minimum Sort.
Bình luận