PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: watoac2001
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Alice and Bob play a game on a circular binary string of length N.
Each turn,
- If the string doesn’t contain any palindromic substring of length \gt 1, the game ends.
- Otherwise, the player chooses any palindromic substring of length \gt 1, and deletes one character from it.
The winner is whoever makes the last move.
Find the winner under optimal play.
EXPLANATION:
The fact that the string is a binary string is important here.
It can be observed that any binary string of length \geq 3 will always contain a palindromic substring of length \gt 1; meaning the game can only possible end with the length of S being either 1 or 2.
Proof
Suppose S has length \geq 3, and look at the first three characters of S.
- If S_1 = S_2, those two characters form a palindrome of length 2.
- If S_2 = S_3, again those two characters form a palindrome of length 2.
- Otherwise, we have S_1 \neq S_2 and S_2 \neq S_3.
But S is a binary string, which forces S_1 = S_3. This then makes the first three characters form a palindrome!
In fact, this fact tells us something even stronger: when the string has length \geq 3, every character will be part of a palindromic substring (just take any length 3 substring containing it, which always exists since S is circular), so each player can freely delete whatever character they want!
Let’s look at two cases now: even N and odd N.
Even N
Suppose N is even.
If the final string is of length 1, Alice would’ve made the last move and she will win; otherwise Bob will win.
Note that when the string is of length 2, then it’s only possible to make it have length 1 if S_1 = S_2, i.e, when S = 00 or S = 11.
So, Alice’s aim is to get it into one of these forms.
If S initially contains an equal number of zeros and ones, this is impossible - whenever Alice removes a 0, Bob will remove a 1 and vice versa; so when the string reaches length 2 it’ll have one 0 and one 1; and Alice will lose.
If S doesn’t contain an equal number of zeros and ones, Alice can always win!
Suppose there are fewer zeros than ones.
Then, Alice will always delete a 0 on her move; and no matter what Bob does the zeros will all disappear - so when the string reaches length 2 it’ll be 11; and Alice will be able to move.
tl;dr Alice wins if the counts of 0 and 1 are different, and loses otherwise.
Odd N
We know how to solve the even case already.
When N is odd, after Alice’s move the string will be of even length, so we can use that information.
Alice can win only if, after her move, the resulting even-length string is a win for the second player (since Bob starts first on the even-length string).
From our analysis above, we know the second player wins only if the number of ones and zeros are equal.
So, if Alice can ensure this after her first move, she’ll win; otherwise she’ll lose.
This translates to Alice winning if and only if the counts of 0 and 1 differ by exactly 1 (in the original string).
The only exception here is N = 1, which Alice always loses.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input().strip()
if n%2 == 0:
if s.count('0') == n//2: print('Bob')
else: print('Alice')
else:
if n > 1 and (s.count('0') == n//2 or s.count('1') == n//2): print('Alice')
else: print('Bob')
