PASCRO - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

1226

PREREQUISITES:

None

PROBLEM:

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?

EXPLANATION:

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.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE

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
        else:
            win += 1
        ans += 1
    print(ans)
1 Like