Test Set 1

Vì có nhiều nhất ba đảng và chín thượng nghị sĩ, nhiều cách vét cạn đều dùng được. Một chiến lược đầy đủ là sinh mọi thứ tự sơ tán khác nhau, coi các thượng nghị sĩ cùng đảng là không phân biệt, rồi thử mọi cách chia từng thứ tự thành các nhóm một hoặc hai người.

Một chiến lược khác đơn giản hơn là liên tục chọn ngẫu nhiên và thử một trong chín bước A, B, C, AA, AB, AC, BB, BC, CC, miễn là những người được chọn vẫn còn và bước đó không tạo ra đa số tuyệt đối mới. Ta có thể lo chiến lược này bị mắc 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 bộ test khả dĩ khác của bài toán, mà đề bảo đảm mọi bộ test đều có lời giải. Tuy nhiên, khi có nhiều đảng và nhiều người hơn, cách này có thể chậm vì phải kiểm tra tính hợp lệ của nhiều bước; do đó cần một cách hiệu quả hơn.

Test Set 2

Theo trực giác, an toàn nhất là mỗi lần đưa ra một người thuộc đảng hiện đông nhất (nếu hòa thì chọn bất kỳ đảng đông nhất nào). Nhưng chiến lược này không phải lúc nào cũng đúng. Chẳng hạn, nếu chỉ có hai người A và hai người B, đưa riêng một người của bất kỳ đảng nào ra sẽ khiến đảng kia có đa số tuyệt đối.

Dẫu vậy, chiến lược trên luôn an toàn khi còn hơn hai đảng. Giả sử đảng 1 hiện là đảng đông nhất hoặc đồng hạng đông nhất trong ít nhất ba đảng, và ta đưa một người của đảng 1 ra. Rõ ràng làm đảng 1 nhỏ đi không thể khiến nó có một đa số tuyệt đối mà trước đó nó không có. Liệu đảng khác có thể giành đa số tuyệt đối không? Giả sử việc này khiến đảng 2, hiện có \(X\) người, giành đa số. Vì trước khi lấy người ra, đảng 1 không nhỏ hơn đảng 2, nên sau đó đảng 1 vẫn có ít nhất \(X-1\) người. Hơn nữa vẫn còn ít nhất một đảng khác, tức có ít nhất một người không thuộc đảng 1 hay 2. Vậy còn ít nhất \(X\) người không thuộc đảng 2; \(X\) người của đảng 2 không thể tạo đa số tuyệt đối, mâu thuẫn.

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

Nếu ngay từ đầu chỉ có hai đảng, vì đề bảo đảm không đảng nào ban đầu có đa số nên hai đảng phải có số người bằng nhau. Ta chỉ cần sơ tán theo từng cặp, mỗi đảng một người, cho tới khi hoàn tất.

Cách này dùng nhiều bước hơn cần thiết — phần lớn các bước đưa một người có thể ghép đôi — nhưng chắc chắn hoàn thành nhiệm vụ.

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 1C.