Contest Duration: - (local time) (120 minutes) Back to Home

## 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: