PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
1413
PREREQUISITES:
None
PROBLEM:
Two players (Zlatan and Ramos) play a game on a binary string of length N.
On their turn, a player chooses two adjacent unequal characters from the string and deletes them both.
Under optimal play, who wins?
EXPLANATION:
The string is a binary string, and each move deletes an adjacent pair of unequal characters.
So, each move will delete exactly one \texttt{1} and one \texttt{0} from the string.
Further, if the string contains at least one \texttt{1} and at least one \texttt{0}, then there will definitely exist some pair of adjacent unequal characters, so a move can always be made.
Turning this around, the only time a move cannot be made is when the string consists of only a single character.
So, suppose S contains c_0 zeros and c_1 ones.
Each move decreases c_0 and c_1 by one each. This means that \min(c_0, c_1) moves can certainly be made, no matter what those moves are.
On the other hand, after \min(c_0, c_1) moves, one of the characters will be fully exhausted and no more moves can be made, so the game always lasts exactly \min(c_0, c_1) moves!
This means that the first player (Zlatan) wins if \min(c_0, c_1) is odd, and loses if it’s even.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
zeros, ones = s.count('0'), s.count('1')
moves = min(zeros, ones)
print('Zlatan' if moves%2 == 1 else 'Ramos')