Phân tích

Đây là bài về lý thuyết thông tin. Có \(N!/2\) kết quả thực chất khác nhau, nên cần ít nhất \(\log_2(N!/2)\) bit thông tin; với \(N=50\), con số hơi lớn hơn \(213\). Vì vậy Test Set 2 có thể dùng trung bình dưới một bit mỗi truy vấn, nhưng Test Set 3 thì không. Test Set 1 không cần phân tích này.

Test Set 1

Có \(300\) truy vấn mỗi bộ, nhiều hơn số bộ ba \({N\choose3}=120\). Hỏi mọi bộ ba và ghi nhớ. Khi không còn áp lực truy vấn, bất kỳ cách sắp dựa trên trung vị đều dùng được.

Hai phần tử duy nhất không bao giờ là trung vị chính là đầu và cuối; tìm chúng rồi tùy ý chọn hướng. Loại hai phần tử đó, tìm hai phần tử không bao giờ là trung vị trong phần còn lại — chúng là vị trí thứ hai và áp cuối. Hỏi thêm với phần tử đã chọn làm đầu và hai ứng viên: ứng viên là trung vị sẽ đứng thứ hai, ứng viên kia đứng áp cuối. Lặp từ ngoài vào tới khi đặt hết.

Các thuật toán phía dưới cũng dùng được, nhưng ở Test Set 1 có thể hỏi trước toàn bộ để cài đặt đơn giản hơn, kể cả với thuật toán vốn cần thêm truy vấn. Các Test Set khác phải làm trực tuyến.

Test Set 2

Vì một bit mỗi truy vấn đủ, dùng thuật toán so sánh tối ưu như Merge Sort hoặc Heap Sort. Insertion Sort cũng dùng được nếu tìm kiếm nhị phân vị trí chèn: dù có \(O(N^2)\) thao tác, nó chỉ dùng \(O(N\log N)\) phép so sánh.

Để mô phỏng so sánh \(i,j\), hỏi trung vị của \(i,j,k\) khi biết \(k\) không thể là trung vị. Ta tìm một cực tiểu/cực đại toàn cục làm \(k\). Có hai phần tử cực trị và cả hai không bao giờ là trung vị. Hỏi ba phần tử đầu, bỏ trung vị, giữ hai ứng viên; lần lượt thêm mỗi phần tử chưa xét, hỏi trung vị và lại bỏ trung vị. Sau \(N-2\) truy vấn, hai ứng viên còn lại là cực tiểu và cực đại.

Test Set 3

Insertion Sort có thể lấy hơn một bit mỗi truy vấn. Thay vì tìm cực trị trước, dùng “cực tiểu hiện tại” của đoạn tìm kiếm làm \(k\). Nó có thể trở thành trung vị; nếu vậy, ta biết chính xác vị trí chèn và dừng. Truy vấn hoạt động như so sánh nhị phân kèm chút thông tin bổ sung. Lợi ích quan trọng là tránh chi phí lớn để tìm cực trị; nếu cẩn thận không vượt ngân sách, cách này có thể qua.

Để dư dả hơn, cần gần mức tối ưu \(\log_2 3\approx1{,}58\) bit mỗi truy vấn: sử dụng đủ ba kết quả với xác suất xấp xỉ nhau.

Cải tiến Insertion Sort bằng tìm kiếm tam phân: ở mỗi bước, hỏi phần tử ở vị trí \(1/3\), vị trí \(2/3\) của đoạn hiện tại cùng phần tử cần chèn. Kết quả thu hẹp xuống một trong ba phần (đầu, giữa, cuối). Các truy vấn xử lý biên như chèn đầu/cuối không đạt \(1{,}58\) bit, nên phải tránh hoặc dùng thưa.

Một lựa chọn khác là quicksort ngẫu nhiên hai chốt. Với hai chốt, mỗi truy vấn gồm hai chốt và một phần tử khác dùng đầy đủ ba kết quả, tương ứng ba nhóm. Khó khăn là mỗi kết quả đệ quy có hơn một phần tử có hai hướng. Truy vấn định hướng cho nhất quán với thứ tự chốt chỉ cho một bit; may mắn, việc này thưa, chỉ tỷ lệ với số nhánh cây đệ quy chứa hơn một phần tử.

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