Phân tích: Revenge of GoroSort

Trong bài GoroSort gốc năm 2011, Goro có thể giữ nguyên tùy ý nhiều phần tử; theo thuật ngữ bài này, anh có thể tạo tùy ý nhiều nhóm màu hộp, mỗi nhóm chứa một bóng. Nhưng khác bài này, anh chỉ được dùng nhiều nhất một nhóm màu có kích thước lớn hơn \(1\). Vì thế chiến lược tối ưu khá trực tiếp: liên tục hoán vị mọi phần tử chưa nằm đúng chỗ.

Theo kỳ vọng, mỗi lượt của chiến lược đó đưa thêm một phần tử về đúng chỗ, rõ ràng quá chậm cho bài này. Phiên bản của nhóm tác giả mất gần \(100000\) lượt. Đáng ngạc nhiên hơn, trọng tâm của bài cũ — suy nghĩ theo số phần tử kỳ vọng sẽ về đúng chỗ sau một lần đập — thậm chí có thể gây hiểu lầm trong bài mới.

Hiểm họa của việc ghép cặp

Theo trực giác, mọi phần tử đã đúng chỗ nên được để yên, tức mỗi phần tử vào nhóm màu riêng. Có vẻ cũng hợp lý khi không tách những cặp phần tử đang đổi chỗ cho nhau. Ta có thể đoán việc tách cặp như vậy là vô ích, còn đưa thêm phần tử vào nhóm của chúng sẽ tệ hơn xử lý các phần tử kia trong nhóm riêng.

Vậy các phần tử còn lại thì sao? Một chiến lược rất hấp dẫn là ghép chúng thành những “cặp xâm nhập”, sao cho một thành viên đang đứng ở vị trí đúng của thành viên kia. Có thể không làm được với mọi phần tử, nhưng chẳng hạn ta có thể gắn các phần tử dư vào những cặp xâm nhập đã có.

Xét cặp xâm nhập \((x,y)\), trong đó \(x\) thuộc về vị trí hiện có \(y\), còn \(y\) thuộc về một vị trí khác hẳn. Phép đập, tức phép hoán vị của bộ chấm, đưa \(x\) về đúng chỗ với xác suất \(1/2\). Nếu tạo được khoảng \(N/2\) cặp như vậy, mỗi lần đập sẽ đưa khoảng \(N/4\) phần tử về đúng chỗ. Điều này khá tốt và đủ qua Test Set 1, nhưng không qua hai bộ còn lại. Các lời giải dựa trên cặp xâm nhập của nhóm tác giả mất từ \(15000\) tới \(16300\) lượt tùy mức cẩn thận khi cài đặt.

Suy nghĩ theo chu trình

Mọi hoán vị, do đó mọi trạng thái của bài, có thể mô tả bằng một đa tập các chu trình với những độ dài nhất định. Mỗi phần tử đúng chỗ là một chu trình độ dài \(1\); mỗi cặp phần tử đổi chỗ là một chu trình độ dài \(2\).

Nếu cài đặt ý tưởng ghép cặp một cách tham lam, ta có thể bỏ lỡ cơ hội tạo cặp xâm nhập. Để tạo nhiều nhất có thể, trước tiên tìm mọi chu trình, rồi cắt từng chu trình thành các cặp xâm nhập và có thể thêm một “bộ ba xâm nhập” ở cuối. Bộ ba xâm nhập là tập \(x,y,z\) theo một thứ tự nào đó, sao cho \(y\) đang ở chỗ của \(x\), \(z\) đang ở chỗ của \(y\), còn \(z\) thuộc về một vị trí ngoài nhóm. Những cải tiến này, đặc biệt việc tạo bộ ba khi cần, giúp rất nhiều nhưng vẫn không đủ qua Test Set 2: lời giải dùng các cặp cộng một bộ ba mất khoảng \(13100\) lượt.

Nếu giữ nguyên các chu trình và dùng mỗi chu trình làm một nhóm hoán vị thì sao? Ta làm tốt hơn nhiều và qua cả Test Set 2, nhưng chưa qua Test Set 3 vì mất khoảng \(11800\) lượt. Tại sao chiến lược theo chu trình tốt hơn hẳn ghép cặp xâm nhập?

Khi kỳ vọng không đáp ứng kỳ vọng

Vấn đề của việc cắt thành cặp xuất hiện ngay ở chu trình độ dài \(4\), chẳng hạn \(2\ 3\ 4\ 1\). Nếu chia thành hai cặp xâm nhập \(2\ 3\) và \(4\ 1\), theo kỳ vọng sẽ đưa một phần tử về đúng chỗ. Nhưng như sẽ thấy, nếu để nguyên cả chu trình thành một nhóm, kỳ vọng cũng bằng \(1\).

Điều đó có nhất thiết nghĩa là hai chiến lược tốt như nhau không? Thứ thật sự cần tối ưu là kỳ vọng tổng số lượt để sắp xếp xong, nên hãy tính đại lượng này. Trước hết:

• Nếu chia chu trình \(4\) thành hai cặp xâm nhập:
• Xác suất \(1/4\): cả hai phần tử liên quan trở về đúng chỗ trong nhóm, tạo hai chu trình \(1\) và một chu trình \(2\).
• Xác suất \(1/4\): không phần tử nào về đúng chỗ trong nhóm, và vẫn mắc kẹt ở một chu trình \(4\).
• Xác suất \(1/2\) còn lại: tạo một chu trình \(1\) và một chu trình \(3\).
• Nếu không chia trước khi hoán vị:
• Xác suất \(1/24\): tạo bốn chu trình \(1\).
• Xác suất \(1/4\): tạo hai chu trình \(1\) và một chu trình \(2\).
• Xác suất \(1/3\): tạo một chu trình \(3\) và một chu trình \(1\).
• Xác suất \(1/8\): tạo hai chu trình \(2\).
• Xác suất \(1/4\): vẫn mắc kẹt ở một chu trình \(4\).

So sánh trực tiếp hai phân phối và triệt tiêu các phần giống nhau, ta cần biết lựa chọn nào tốt hơn: xác suất \(1/6\) nhận một chu trình \(3\) cùng một chu trình \(1\); hay xác suất \(1/8\) nhận hai chu trình \(2\) cộng xác suất \(1/24\) nhận bốn chu trình \(1\).

Ta đánh giá các trạng thái ấy bằng kỳ vọng số lượt còn lại. Một chu trình \(3\) cần kỳ vọng \(3\) lượt để trở thành toàn chu trình \(1\). Kết quả đến từ việc giải

và dùng \(E[2]=2\). Phân tích tương tự cho thấy hai chu trình \(2\) cần kỳ vọng \(8/3\) lượt để trở thành toàn chu trình \(1\). Nếu may mắn tới thẳng bốn chu trình \(1\), cần thêm \(0\) lượt.

Do đó, cắt một chu trình \(4\) thành hai cặp xâm nhập thực sự tệ hơn để nguyên. Chỉ nhìn kỳ vọng số phần tử đúng chỗ sẽ không phát hiện điều này; trạng thái bị bỏ lại cũng quan trọng. Theo trực giác, phần tử xâm nhập chỉ có thể được xử lý sau khi bạn đồng hành của nó đã đúng chỗ, nên chiến lược cắt cặp khó song song hóa hơn. Tuy vậy, không nên cho rằng mọi cách cắt đều luôn xấu.

Cắt không phải lúc nào cũng tệ

Thực hiện phép phân tích trên cho các chu trình dài hơn \(4\) khá tẻ nhạt, nhưng chưa nên bỏ cuộc. Hai chiến lược có cùng kỳ vọng với chu trình \(4\); liệu điều đó có còn đúng nói chung?

Hãy xét số chu trình kỳ vọng trong một hoán vị ngẫu nhiên độ dài \(N\). Có một bài toán quen thuộc: mọi người cùng mất mũ, rồi mỗi người đội ngẫu nhiên một chiếc; kỳ vọng bao nhiêu người lấy lại đúng mũ của mình? Mỗi người nhận đúng mũ với xác suất \(1/N\), nên theo tính tuyến tính của kỳ vọng, tổng số người nhận đúng là \((1/N)\cdot N=1\).

Đó là kỳ vọng số chu trình \(1\). Lập luận tương tự với chu trình \(2\): có \({N\choose2}\) cặp phần tử có thể tạo chu trình \(2\), và mỗi cặp tạo chu trình với xác suất \((1/N)\cdot(1/(N-1))\). Kết quả rút gọn thành \(1/2\). Tổng quát, kỳ vọng số chu trình độ dài \(k\) là \(1/k\).

Vậy kỳ vọng tổng số chu trình là \(1/1+1/2+\ldots+1/N\), chính là số điều hòa thứ \(N\). Các số điều hòa tăng rất chậm; chẳng hạn \(H_{100}\) chỉ lớn hơn \(5\) một chút.

Vì thế, nếu hoán vị ngẫu nhiên ban đầu với \(N=100\) chỉ có khoảng \(5\) chu trình, ta kỳ vọng đưa khoảng \(5\) phần tử về đúng chỗ. Nhưng nếu cắt các chu trình thành khoảng \(50\) cặp xâm nhập, ta kỳ vọng đưa khoảng \(25\) phần tử về đúng chỗ. Làm sao để nguyên các chu trình lớn lại có thể tốt hơn? Liệu lập luận về việc để lại một mớ hỗn độn vẫn còn đúng?

Một vấn đề của việc cắt cặp là theo trực giác, nhiều con đường tới trạng thái hoàn thành phải đi qua một hoặc nhiều chu trình \(4\), và ta đã thấy chiến lược cắt cặp xử lý sai chúng. Giờ ta cũng có lý do nghi ngờ nó xử lý sai các chu trình lớn hơn.

Nếu cắt thành các khúc lớn hơn cặp thì sao? Chẳng hạn, chia chu trình \(6\) thành hai bộ ba xâm nhập: mỗi bộ ba cho kỳ vọng \(2\cdot(1/3)=2/3\) phần tử đúng chỗ, tổng là \(4/3\), ít hơn \(3\cdot(1/2)=3/2\) khi cắt thành cặp. Nhưng các bộ ba để lại ít hỗn độn hơn: mỗi bộ chỉ để lại tối đa một phần tử cần dọn về sau, tổng là hai thay vì ba.

Khó cân trực tiếp chi phí dọn phần dư với lợi ích đưa nhiều phần tử về đúng chỗ theo kỳ vọng. Phép tính cho chu trình \(4\) đã khá cồng kềnh trong một vòng thi, và càng ít lý do làm thêm khi công cụ kiểm thử cục bộ nhanh chóng cho biết chiến lược hoạt động ra sao, còn cả ba Test Set đều có phán quyết hiển thị. Thực nghiệm cho thấy giữ nguyên mọi chu trình ngắn hơn \(6\), đồng thời cắt mọi chu trình dài ít nhất \(6\) thành các bộ ba xâm nhập, hoặc bộ bốn hay năm khi có phần tử dư, tốt hơn nhiều so với giữ nguyên tất cả. Cách này qua Test Set 3 với khoảng \(10950\) lượt.

Có thể tốt hơn nữa bằng cách chọn độ dài khúc khác, chẳng hạn chia chu trình độ dài \(c\) thành các khúc cỡ \(\sqrt c\) để giảm xuống khoảng \(10500\) lượt, nhưng điều đó không cần thiết cho bài này.

Phân tích chính thức của Google Code Jam 2022, Vòng 3, bài Revenge of GoroSort.