Test Set 1: vét cạn

Với nhiều nhất ba đảng và chín người, nhiều cách vét cạn đều đủ nhanh. Có thể sinh mọi thứ tự sơ tán khác nhau, coi các thành viên cùng đảng là không phân biệt, rồi thử mọi cách chia thứ tự ấy thành nhóm một hoặc hai người.

Cách đơn giản khác là liên tục chọn ngẫu nhiên một trong chín chỉ dẫn A, B, C, AA, AB, AC, BB, BC, CC, miễn là những người được chọn còn trong phòng và bước đó không tạo đa số tuyệt đối. Ta có thể lo chiến lược bị kẹt, nhưng trạng thái sau bất kỳ bước hợp lệ nào cũng chỉ là một test khác của chính bài toán, mà đề bảo đảm mọi test đều có lời giải. Với nhiều đảng và nhiều người hơn, chi phí kiểm tra các bước sẽ cồng kềnh, nên cần cách hiệu quả hơn.

Test Set 2: luôn lấy từ đảng đông nhất

Theo trực giác, an toàn nhất là mỗi lần lấy một người từ một đảng đang đông nhất, tùy ý phá hòa. Nhưng quy tắc này không luôn hoạt động: nếu chỉ còn hai người đảng A và hai người đảng B, lấy một người của bên nào cũng khiến bên kia có đa số tuyệt đối.

Tuy nhiên, chiến lược luôn an toàn khi còn hơn hai đảng không rỗng. Giả sử đảng 1 đang đông nhất hoặc đồng hạng đông nhất trong ít nhất ba đảng, rồi ta lấy một người của đảng 1. Rõ ràng làm đảng 1 nhỏ đi không thể khiến chính nó mới có đa số. Giả sử đảng 2 có \(X\) người lại trở thành đa số sau bước ấy. Trước bước đó đảng 1 không ít hơn đảng 2, nên sau bước vẫn còn ít nhất \(X-1\) người đảng 1. Vì còn ít nhất một đảng khác, còn ít nhất một người không thuộc đảng 1 hay 2. Vậy tổng số người không thuộc đảng 2 ít nhất là \(X\), nên \(X\) người đảng 2 không thể chiếm hơn một nửa — mâu thuẫn.

Nếu bắt đầu với ít nhất ba đảng và cứ lấy một người từ đảng đông nhất, cuối cùng sẽ có bước chuyển từ ba đảng xuống hai. Hai đảng còn lại lúc đó phải chỉ có đúng một người mỗi đảng: người vừa được lấy là người cuối của đảng thứ ba, đảng ấy trước bước là một đảng đông nhất, nên hai đảng kia không thể lớn hơn. Ta đưa cặp cuối ra cùng một bước để hoàn tất.

Nếu ngay từ đầu chỉ có hai đảng, điều kiện không đảng nào có đa số buộc hai bên có số người bằng nhau. Khi ấy cứ đưa từng cặp, mỗi đảng một người, cho đến hết.

Cách này dùng nhiều bước hơn cần thiết — phần lớn bước một người có thể ghép đôi — nhưng luôn hoàn thành đúng yêu cầu. Nếu dùng heap để lấy đảng đông nhất, thời gian là \(O(S\log N)\) với \(S=\sum_iP_i\), bộ nhớ \(O(N)\); do \(N\le26\), quét tuyến tính mỗi bước cũng đủ nhanh.

Dựa trên phân tích chính thức của Google Code Jam 2018, Vòng luyện tập, bài Senate Evacuation.