DLSB - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: pols_agyi_pols
Testers: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Alice and Bob play a game on a binary string S. On their turn, a player removes some substring whose characters are equal. Alice moves first.
Alice wants to remove every 1 from the string, while Bob wants to remove every 0.

Before the game starts, Bob can modify individual positions of S.
What’s the minimum number of modifications he needs to ensure he wins?

EXPLANATION:

Alice wants to remove every 1, while Bob wants to remove every 0.
Clearly, on her turn Alice will remove some block of 1's, and Bob will remove some block of 0's.

Suppose S contains x blocks of 1's and y blocks of 0's.
For example, if S = \texttt{10011001}, we have x = 3 and y = 2.
Note that since blocks alternate between 0 and 1, we’ll have |x-y| \leq 1.
In particular,

  • x = y means that the starting and ending blocks are of different types.
  • x = y+1 or y = x+1 mean that the starting and ending blocks are of the same type.

Now, observe that:

  • If x \leq y, Alice wins.
    This is because, in this case S must either start with or end with a 1.
    So, Alice can just delete the boundary block of 1's, which reduces x by 1 and doesn’t change y.
  • If x \gt y, Bob wins.
    This is because, no matter what Alice does, x cannot be reduced by more than 1.
    So, when the turn passes to Bob, it’ll be the first case from his perspective; and he thus has a winning strategy.

Since we want Bob to win, we need to find the minimum number of flips that will result in x\gt y, that is, there being more blocks of 1's then 0's.
However, since we noted earlier that |x-y| \leq 1, this really means we’re forced to ensure that x = y+1.
This is only possible if and only if S both starts and ends with a 1.

So, the solution is to simply flip the first and/or last character of S if they’re 0.
N = 1 is an edge case, since the first and last characters are the same (and so only one swap is needed, if at all).

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 == 1:
        print(1 - int(s[0]))
        continue
    
    ans = (s[0] == '0') + (s[-1] == '0')
    print(ans)
1 Like
2

" Clearly, on her turn Alice will remove some block of 111’s, and Bob will remove some block of 000’s."
Why ? Can we have a proof for this please ?

1 Like
3

Hi, I have some confusions,
if S = 10011001 we have x = 3 and y = 2, which means x = groups of 1s and y = groups of 0s.
but you have mentoned if x<= y, aloce wins as S must either start or end with a 1, but for “0011001100”, x=2 and y=3 (x<y) but string starts and ends with 0s.

Can you please clarify this?

4

its said in the question

5

The question doesn’t say alice will only remove a particular element. It is possible to remove something else if that helps the player. In this case, it doesn’t

6

No the string is made up of 1s and 0s and now see the question
“Alice wins immediately when S doesn’t contain any occurrence of 1, while Bob wins immediately when S doesn’t contain any occurrence of 0”.
So i alice wins if s doesn’t have any occurrence of 1 then the obviously she would remove 1s from the string and not 0 and same goes for bob

7

it says alice wants to remove, not alice is only allowed to remove 1’s, its not obvious for me, the statement could have made this clear

8

Its a game theory problem why would you help you opponent to win. Alice want to win from herself not help bob to win