Với \(A\) đối thủ, có \(A!\) cách sắp xếp ban đầu có thể có cho nhánh đấu, mà bản thân \(A\) lại tăng theo hàm mũ của số vòng đấu. Chỉ riêng giai thừa của một đại lượng mũ đã đủ đáng sợ, trong khi chúng ta thậm chí còn chưa bắt đầu xét diễn biến giải đấu!

May thay, ta có thể bỏ qua gần như toàn bộ cấu trúc của giải đấu. Với mỗi đối thủ, luôn tồn tại ít nhất một cách sắp xếp ban đầu khiến ta đấu trận đầu tiên với đối thủ đó. Vì phải đảm bảo vô địch bất kể cách sắp xếp ban đầu, ta phải có khả năng đánh bại mọi đối thủ. Ta không thể hòa một đối thủ, bởi lần tung đồng xu đó có thể không cho kết quả có lợi cho ta!

Vì vậy, tất cả những gì cần làm là tìm một chương trình thắng chương trình của mọi đối thủ. Để kiểm tra một chương trình, ta chỉ cần cho nó đấu với từng đối thủ mà không phải quan tâm đến cách sắp xếp giải đấu.

Test Set 1

Trong Test Set 1, có nhiều nhất \(7\) đối thủ và chương trình của họ dài nhiều nhất \(5\) ký tự. Chương trình của ta có thể dài hơn nếu cần, nhưng nó cần dài đến mức nào? Ta nhận thấy một chương trình chiến thắng tối ưu không bao giờ nên lãng phí một lượt bằng cách hòa với tất cả đối thủ còn lại, bởi khi đó nó đã có thể chọn nước thắng tất cả họ; do đó, mỗi nước đi phải loại được ít nhất một đối thủ. Vì vậy, trong Test Set 1, nếu tồn tại một chương trình chiến thắng thì nó dài nhiều nhất \(7\) nước. Ta hoàn toàn có thể kiểm tra tất cả \(3^7 + 3^6 + \dots + 3\) chương trình có độ dài không quá \(7\).

Khi mô phỏng một trận, ta không thể ngồi chờ suốt một googol nước; theo đúng lập luận trên, một chương trình chiến thắng tối ưu chỉ cần nhiều nhất \(7\) nước để đánh bại tất cả đối thủ, nên ta chỉ phải mô phỏng tối đa \(7\) nước. Nếu đến lúc đó ta vẫn hòa với đối thủ, ta có thể yên tâm loại bỏ chương trình đang xét.

Nếu không tìm được chương trình nào dài không quá \(7\) nước mà thắng chương trình của mọi đối thủ, ta có thể kết luận bộ test là IMPOSSIBLE.

Test Set 2

Trong Test Set 2, có thể có đến \(255\) đối thủ, và ta không thể sinh rồi kiểm tra tất cả chương trình có độ dài không quá \(255\). Ta phải tìm cách xây dựng một chương trình chiến thắng nếu nó tồn tại.

Hãy tưởng tượng ta đấu với tất cả đối thủ cùng một lúc. Ta chọn nước đầu tiên trong chương trình của mình như thế nào? Ta phải thắng hoặc hòa với mọi đối thủ, nên sẽ xét tập hợp các nước đầu tiên của họ. Nếu tập này chứa đủ cả ba nước có thể có, ta đã hết cách: bất kể chọn gì, ít nhất một đối thủ sẽ đánh bại ta. Nếu nó chỉ chứa một nước (chẳng hạn mọi đối thủ đều bắt đầu bằng R), ta có thể chọn nước thắng nước đó (trong trường hợp này là P) và lập tức đánh bại tất cả. Nếu không, tập hợp chứa hai trong ba nước có thể có, và ta nên chọn nước hòa với một loại đồng thời thắng loại còn lại. Ví dụ, nếu tất cả đối thủ đều mở đầu bằng S hoặc P, ta nên chọn S.

Sau khi loại mọi đối thủ đã bị đánh bại và chuyển sang nước tiếp theo của "trận đấu" tổng hợp này, ta có thể áp dụng cùng chiến lược, nhưng lần này xét tập hợp nước thứ hai của các đối thủ còn lại (lặp lại chương trình của họ khi cần), rồi cứ tiếp tục như vậy. Mỗi nước đi sẽ loại ít nhất một đối thủ, nên sau \(A\) nước, ta sẽ thu được chương trình chiến thắng hoặc biết rằng bộ test là IMPOSSIBLE. Lưu ý rằng giới hạn này đúng bất kể độ dài chương trình của các đối thủ.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 1C — Robot Programming Strategy.