MAX1XOR - Editorial

PROBLEM LINK:

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

Author: arunsharma_
Tester: abhidot
Editorialist: iceknight1093

DIFFICULTY:

1381

PREREQUISITES:

None

PROBLEM:

Given a binary string S, consider another binary string X such that X_{i+1} = S_i \oplus X_i for each 1 \leq i \lt N.

Find the maximum number of ones such a string can have.

EXPLANATION:

Note that one X_1 is fixed, the rest of the string is uniquely determined, since:

  • X_2 = X_1 \oplus S_1
  • X_3 = X_2\oplus S_2
    \vdots

But X is a binary string, so there are only two choices for X_1 — it can be either 0 or 1.
Simply try both options, construct the respective strings, and see which one has the maximum number of ones.

TIME COMPLEXITY

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

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    s = input()
    ct1, ct2 = 0, 0
    prv = '0'
    for i in range(1, n):
        if s[i-1] == prv: prv = '0'
        else: prv = '1'
        ct1 += prv == '1'
    ct2, prv = 1, '1'
    for i in range(1, n):
        if s[i-1] == prv: prv = '0'
        else: prv = '1'
        ct2 += prv == '1'
    print(max(ct1, ct2))

i think i got the logic but can’t understand why it is giving tle with s1=s1+“1”; statement and not with s1+=“1”;??

a = a + b first constructs the string a + b and the assigns it to a.
a += b directly appends b to the end of a. This takes $

If you analyze what this means for constructing a string of length N character-by character, the first method takes \mathcal{O}(N^2) time while the second takes \mathcal{O}(N) time.

thanks

thanks for this valuable info mate