# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* notsoloud

*yash_daga*

**Tester:***iceknight1093*

**Editorialist:**# 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)
```