# PASCRO - Editorial

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

1226

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