STRAME - Editorial


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

Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093






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?


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.


\mathcal{O}(N) per test case.


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!!