# STRAME - Editorial

Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093

1413

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')

1 Like

I am such a such a fool. I created freaking Linked List to solve this problem and was wondering why it was TLE!!

Anyways, Nice Problem!! I liked it!!