Tổng quan

Có nhiều cách tiếp cận. Ta trình bày hai phương pháp dựng đúng cây giải đấu và một phương pháp sắp xếp cây để thu được hàng nhỏ nhất theo thứ tự từ điển. Có thể gộp hai phần thành một thuật toán, nhưng tách ra sẽ dễ giải thích hơn.

Dựng cây từ đầu giải

Ở bất kỳ thời điểm nào, ta có một số R, P, S còn lại và chỉ được tạo các trận RP, RS, PS; mọi cặp khác đều hòa. Gọi \(x\) là số trận RP, tức ghép \(x\) người R với \(x\) người P. Mọi R còn lại phải gặp S, nên có \(R-x\) trận RS. Còn \(P-x\) người P và \(S-(R-x)\) người S; hai số này phải bằng nhau để ghép hết mà không hòa:

Nếu \(x\) gây ra tình huống bất khả thi — chẳng hạn cần nhiều trận RP hơn số R hoặc P — đáp án là IMPOSSIBLE. Nếu không, ghép các đấu thủ theo đó và ghi lại người thắng: RP cho P, RS cho R, PS cho S. Ta thu được một phiên bản nhỏ hơn của cùng bài toán. Chiến lược này cho biết giải có kết thúc không và phải ghép thế nào; nếu lưu thông tin cẩn thận qua các vòng, ta dựng được toàn bộ cây.

Dựng cây từ cuối giải

Thay vào đó, hãy bắt đầu từ cuối. Giả sử nhà vô địch là P. Trận tạo ra người thắng đó buộc có một P và đối thủ mà P đánh bại là R. Người R ấy trước đó buộc phải thắng một S, v.v. Nói cách khác, từ bất kỳ nút nào của cây giải đấu, kể cả nút cuối cùng, ta có thể tái tạo toàn bộ phần cây dẫn tới nó.

Điều này còn cho thấy với một \(N\) cố định, chỉ có đúng một bộ ba số lượng (R, P, S) tạo được giải thành công kết thúc bằng R; tương tự cho P và S. Gần như mọi bộ ba đều thất bại! Với mỗi \(N\) chỉ có ba bộ hợp lệ, và chúng có ba nhà vô địch khác nhau.

Vì vậy, với từng \(N\) từ 1 đến 12, thử cả ba nhà vô địch R, P, S, lưu cây thu được cùng số lượng R, P, S. Với mỗi bộ test, nếu \(N,R,P,S\) khớp một cây đã lưu thì dùng cây đó; nếu không khớp cả ba thì IMPOSSIBLE.

Tìm hàng nhỏ nhất theo thứ tự từ điển

Có cây giải đấu vẫn chưa đủ vì một cây có thể sinh nhiều hàng ban đầu. Ở mỗi nút trong, có thể đổi chỗ hai nhánh; cây không đổi nhưng hàng ban đầu đổi. Ví dụ, PSRS, PSSR, RSPS, RSSP, SPRS, SPSR, SRPS, SRSP đều biểu diễn cùng một cây. Cây có \(2^N-1\) nút trong, nên không thể thử cả \(2^{2^N-1}\) cách chọn đổi hoặc không đổi từng nút.

May mắn là không cần làm vậy. Xét hai người gặp nhau ở vòng đầu, dùng nước X và Y, trong đó X đứng trước Y theo bảng chữ cái. Hai người tạo hai ký tự liên tiếp trong hàng: XY hoặc YX tùy việc đổi nút. Đổi các nút khác có thể di chuyển cả cặp trong hàng cuối, nhưng không thể đảo ngược hay tách hai ký tự. Vì thế luôn chọn XY mà không mất gì; quyết định này độc lập với các nút khác. Tổng quát hơn, ở mỗi nút ta đặt nhánh nhỏ hơn theo thứ tự từ điển trước nhánh lớn hơn. Cần tối ưu các nút sâu hơn trước các nút nông hơn để lúc so sánh, bản thân mỗi nhánh đã được tối ưu.

Do đó, có thể bắt đầu từ bất kỳ hàng nào ứng với cây. Trước tiên chia thành \(2^{N-1}\) khối dài 2 và đổi hai ký tự khi làm khối nhỏ hơn. Sau đó chia thành \(2^{N-2}\) khối dài 4, trong mỗi khối đổi hai nửa dài 2 nếu làm khối nhỏ hơn. Tiếp tục như vậy cho tới khi xét hai khối dài \(2^{N-1}\). Hàng cuối cùng chính là đáp án nhỏ nhất theo thứ tự từ điển.

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.