C - Large RPS Tournament Editorial by evima


The problem is easier in both implementation and theory when \(n\) is even, so let us concatenate two copies of \(s\) and call it \(s\) (without changing the answer).

After every player ends his/her first round, what is the \(i\)-th (\(0\)-indexed) hand from the left among the hands still surviving? From the way the rounds are arranged, we can see that this is the winner of the match between Player \(2i\) and Player \(2i+1\). This state is the same as the one with \(2^{k-1}\) players where the hands are represented by the string \(t\) defined below:

for i = 0, 2, ... ,n-2
    t[i/2] = the non-loser of a match between s[i] and s[i+1]

Thus, we can find the answer as the first character of the string obtained by repeating this process \(k\) times.

Sample Implementation in C++

posted:
last update: