Tổng quan

Bài toán có hai thử thách: xác định những tập thành viên nào cần xét làm ủy ban, và tính xác suất hòa của mỗi ủy ban. Với Test Set nhỏ, vét cạn đủ cho cả hai phần. Với Test Set lớn, cả hai đều cần phương pháp hiệu quả hơn.

Nên chọn những ai?

Ta có thể nghĩ rằng để dễ hòa, nên chọn những thành viên “ôn hòa”, tức xác suất “Có” gần 0.5 nhất. Thực ra điều ngược lại mới đúng! Cách tốt nhất là chọn ở một hoặc cả hai đầu cực trị: chọn \(M\) người có xác suất “Có” thấp nhất (có thể \(M=0\)), và \(K-M\) người có xác suất cao nhất. Trực giác: ủy ban hai người với xác suất 0.00 và 1.00 luôn hòa, còn 0.50 và 0.50 chỉ hòa một nửa. Thử nghiệm cũng ủng hộ nhận xét này; sau đây là chứng minh.

Không mất tính tổng quát, sắp thành viên theo xác suất “Có” tăng dần. Giả sử đã chọn một ủy ban tối đa hóa xác suất hòa. Nếu có nhiều ủy ban như vậy, chọn trong số đó ủy ban có tổng chỉ số trong danh sách đã sắp là nhỏ nhất.

Ta chứng minh tập đó gồm \(M\) người ngoài cùng bên trái và \(K-M\) người ngoài cùng bên phải. Giả sử tồn tại người X được chọn, còn Y và Z không được chọn, và thứ tự từ trái sang phải là Y, X, Z. Cố định mọi thành viên khác, xét xác suất hòa như một hàm theo xác suất “Có” của X. Đây là hàm tuyến tính. Nếu hệ số góc bằng 0, thay X bằng Y cho kết quả tốt ngang nhau nhưng tổng chỉ số nhỏ hơn. Nếu hệ số góc dương, thay X bằng Z cho kết quả tốt hơn. Nếu hệ số góc âm, thay X bằng Y cho kết quả tốt hơn. Cả ba đều mâu thuẫn, nên X như vậy không thể tồn tại.

Vì thế ta thử mọi \(M\) và chỉ xét các ủy ban dạng này. Tìm tuyến tính theo \(M\) nhân thêm \(O(K)\) vào thời gian tính xác suất hòa. Việc sắp xếp một lần tốn \(O(N\log N)\).

Xác suất hòa là bao nhiêu?

Với một ủy ban lớn, không thể xét rõ ràng cả \(2^K\) kết quả bỏ phiếu. Nhiều kết quả rất giống nhau và sẽ lặp công việc; đây là tình huống lý tưởng cho quy hoạch động.

Lập bảng trong đó các cột biểu diễn số thành viên đã bỏ phiếu, các hàng biểu diễn tổng số phiếu “Có” tới lúc đó, còn mỗi ô là xác suất của trạng thái tương ứng. Bắt đầu bằng 1.00 ở ô trên cùng bên trái: trước khi ai bỏ phiếu, xác suất có 0 phiếu “Có” là 100%. Xét ủy ban có các xác suất 0.10, 0.20, 0.50, 1.00 theo thứ tự đó, dù thứ tự thực ra không quan trọng:

- init 0.10 0.20 0.50 1.00
0 1.00 ---- ---- ---- ----
1 ---- ---- ---- ---- ----
2 ---- ---- ---- ---- ----
3 ---- ---- ---- ---- ----
4 ---- ---- ---- ---- ----

Khi người đầu bỏ phiếu, họ bỏ “Có” với xác suất 10% và ta có một phiếu “Có”, hoặc bỏ “Không” với xác suất 90% và vẫn có 0 phiếu “Có”. Giá trị 1.00 được chia vào hai ô ở cột kế tiếp:

- init 0.10 0.20 0.50 1.00
0 1.00 0.90 ---- ---- ----
1 ---- 0.10 ---- ---- ----
2 ---- ---- ---- ---- ----
3 ---- ---- ---- ---- ----
4 ---- ---- ---- ---- ----

Xét ô “0 phiếu Có sau 1 người”, chiếm 90% các khả năng. Xác suất này đổ vào hai ô cột kế: ô ngay bên phải và ô chéo xuống phải. Người thứ hai bỏ “Không” với xác suất 80%, nên 80% của phần 90% đi tới “0 phiếu Có sau 2 người”; 20% còn lại đi tới “1 phiếu Có sau 2 người”:

- init 0.10 0.20 0.50 1.00
0 1.00 0.90 0.72 ---- ----
1 ---- 0.10 0.18 ---- ----
2 ---- ---- ---- ---- ----
3 ---- ---- ---- ---- ----
4 ---- ---- ---- ---- ----

Tiếp theo xét ô “1 phiếu Có sau 1 người”, chiếm 10%. Nó cũng đổ vào ô bên phải và chéo xuống phải. Ta cộng 0.08 vào giá trị 0.18 đã có ở ô “1 phiếu Có sau 2 người”, vì có nhiều cách tới cùng trạng thái. Sức mạnh của quy hoạch động là gộp các khả năng riêng biệt như vậy để xử lý chung về sau, tránh số trường hợp tăng theo hàm mũ:

- init 0.10 0.20 0.50 1.00
0 1.00 0.90 0.72 ---- ----
1 ---- 0.10 0.26 ---- ----
2 ---- ---- 0.02 ---- ----
3 ---- ---- ---- ---- ----
4 ---- ---- ---- ---- ----

Tiếp tục tương tự để điền toàn bảng. Đúng như kỳ vọng, tổng mỗi cột bằng 1:

- init 0.10 0.20 0.50 1.00
0 1.00 0.90 0.72 0.36 0.00
1 ---- 0.10 0.26 0.49 0.36
2 ---- ---- 0.02 0.14 0.49
3 ---- ---- ---- 0.01 0.14
4 ---- ---- ---- ---- 0.01

Xác suất hòa là ô “2 phiếu Có sau 4 người”: 0.49. Có thể tối ưu thêm bằng cách không xét các hàng nằm dưới số phiếu “Có” cần để hòa. Trong thực tế, ở các bài kiểu này nên lưu logarit xác suất thay vì giá trị thật, vì xác suất có thể nhỏ đến mức sai số dấu phẩy động trở nên đáng kể.

Số phép tính tỉ lệ với kích thước hai chiều của bảng, mỗi chiều tỉ lệ với \(K\), nên phần này tốn \(O(K^2)\). Kết hợp với \(O(K)\) cách chọn ủy ban, tổng thời gian là \(O(K^3)+O(N\log N)\). Vì \(K\le N\le200\) ở Test Set lớn, cách này đủ nhanh dù chưa tối ưu; chẳng hạn có thể tìm kiếm tam phân theo \(M\) thay vì duyệt tuyến tính.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 2.