PASCRO - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093






Chef and Chefina play rock-paper-scissors.
Chef’s moves are encoded in the string A, and Chefina’s in string B.
How many moves should Chef have made differently if he was to win?


Each turn can be classified into one of three types: a win for Chef, a loss for Chef, or a draw.
For Chef to win the entire game, he should have strictly more wins than losses.

So, let’s compute the initial counts of each type, as variables \texttt{W, L,} and \texttt{D} respectively.
For Chef to win, he need \texttt{W} \gt \texttt{L} in the end; in other words, \texttt{W}-\texttt{L} \gt 0.
If Chef changes his move on some turn, it’s clearly best to change a non-win to a win.
The following are possible:

  • A loss can be converted into a win.
    This increases \texttt{W} by 1 and decreases \texttt{L} by 1.
    The overall change to \texttt{W}-\texttt{L} is thus +2.
  • A draw can be converted into a win.
    This increases \texttt{W} by 1, but doesn’t change \texttt{L}.
    The overall change to \texttt{W}-\texttt{L} is thus +1.

Clearly, it’s best to do the first type of move as long as possible.
So, Chef can change his moves greedily:

  • If \texttt{W}-\texttt{L} \gt 0, stop: he’s already won.
  • Otherwise, \texttt{W} - \texttt{L} \leq 0.
    • If \texttt{L}\gt 0, do the first type of move.
    • Otherwise, do the second type of move.

In the end, output the number of moves made.


\mathcal{O}(N) per testcase.


Editorialist's code (Python)
wins = set([('P', 'R'), ('R', 'S'), ('S', 'P')])
for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()
    win, lose, draw = 0, 0, 0
    for i in range(n):
        if (a[i], b[i]) in wins: win += 1
        elif (b[i], a[i]) in wins: lose += 1
        else: draw += 1
    ans = 0
    while True:
        if win > lose: break
        if lose > 0:
            win += 1
            lose -= 1
            win += 1
        ans += 1
1 Like