P5209 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Alice and Bob play a game on a binary string S.
On their turn, a player must remove one character from either the front or the back of S.

Alice’s goal is to make S a non-empty string with an equal count of 01 and 10 substrings.
Bob’s goal is to make the string empty without the above ever happening.

With optimal play, who wins?

EXPLANATION:

Let’s understand what it means for a string to have an equal number of 01 and 10 substrings.

Suppose S_1 = 0.
Then, as we go left to right, the following can be seen:

  • We’ll see several zeros; which don’t create any 01 or 10 substrings.
  • Then, we’ll see a 1 for the first time.
    This will create a 01 substring.
  • After that, there will be several ones; but again no 01 or 10 substrings will be present while this happens.
  • Next, we’ll encounter a 0, which creates a 10 substring.
    After this, again no 01 or 10 substrings will be created, till we reach another 1, and so on.

More generally, as we move left to right, a 10 or 01 substring will be created exactly each time we “change” characters.
Further, changing from 0 to 1 creates an occurrence of 01, and changing from 1 to 0 creates an occurrence of 10.

Because of this, observe that we’ll actually alternate between seeing a 01 and a 10.
This means, in the end, the counts of 01 and 10 will either be equal, or they will differ by 1.

Let’s use this observation to solve the problem.

Alice wants the counts of 01 and 10 to be equal and positive.
Let c_{01} and c_{10} be the counts of substrings 01 and 10, respectively.
Observe that if a player deletes the leftmost character S_1,

  • If S_1 = S_2, then both c_{01} and c_{10} don’t change.
  • Otherwise, the count corresponding to the substring S_1S_2 reduces by 1.

Similarly, if S_N is deleted, either both counts don’t change, or exactly one count reduces by 1 (depending on how S_N compares to S_{N-1}.

In particular, if c_{01} = 0 or c_{10} = 0 initially, it’s impossible for Alice to achieve her goal of making both be \ge 1, since deletion cannot increase counts.

That leaves us with the case of c_{01} \ge 1 and c_{10} \ge 1.
Here, Alice will always win, because:

  • If c_{01} = c_{10} initially, Alice wins without even having to make a move.
  • If not, then the counts must differ by 1.
    Suppose c_{01} = c_{10} + 1.
    As Alice and Bob delete characters, eventually a point will be reached where either c_{01} or c_{10} must decrease by 1.
    However, if c_{10} decreases by 1, the difference between it and c_{01} will equal 2; which is impossible.
    So, c_{01} must decrease by 1 instead; and now the counts are equal.

This gives us a simple solution: compute the initial counts c_{01} and c_{10}, and check if they’re both positive or not.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = list(input())
    t = sorted(s)
    
    if s == t or s == t[::-1]: print('Bob')
    else: print('Alice')
2 Likes