SAMESTR - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You are given a binary string S.
For a fixed k between 1 and N, you can do the following:

  • Exactly k times, choose an index i and flip S_i between 0 and 1.

Find the number of k such that it’s possible to make S have all its characters equal.

EXPLANATION:

Let’s try to solve the problem for a fixed k.

In fact, let’s try to solve an even more restricted version: with this fixed k, let’s try to make the string have all 0's.
Suppose S has x ones.
Then,

  • We need x moves to turn every 1 into a 0.
  • After that, any move we make will turn a 0 into a 1 - so we need another move to turn it back.

So, it’s possible to turn all the characters into 0 if and only if:

  1. k\geq x, so that we have enough moves to even affect all the ones.
  2. (k-x) is even, since each extra move we make requires an additional move to revert the change.

In other words, the values of k for which it’s possible to turn all the characters into 0 are exactly

\{x, x+2, x+4, x+6, \ldots \}

Similar reasoning tells us that if there are y zeros, the k for which all the characters can be turned into 1 are

\{y, y+2, y+4, y+6, \ldots \}

So, simply count all the values that satisfy one of the above two properties.
Make sure not to overcount: if x = 4, y = 6 then the values 6, 8, 10 will appear in both lists, but should be counted only once.

Further, since we want k \geq 1, make sure not to count k = 0 (which you might do accidentally if x = 0 or y = 0).

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    mn = min(s.count('0'), s.count('1'))
    mx = n - mn
    if mn > 0: ans = len(range(mn, n+1, 2))
    else: ans = len(range(2, n+1, 2))
    if mn%2 != mx%2: ans += len(range(mx, n+1, 2))
    print(ans)
2 Likes
2

Let suppose k(10^18 and not dependent on n) was pretty large, what will be the formula to get our answer(may include inclusion exclusion right?) not be able to get to the desired formula. @iceknight1093 is there any other way?

I got this to work:-

    if(ones % 2 == zeros % 2){ // if same parity
        // common to be counted as one time => (n - maxi) / 2 + 1
        // rest => (maxi - 2 - mini) / 2 + 1
        int maxi = max(ones, zeros);
        int mini = min(ones, zeros);
        ans = (maxi - 2 - mini) / 2 + 1 + (n - maxi) / 2 + 1; 
    }else{
        // otherwise just add both.
        ans = (n - ones) / 2 + 1 + (n - zeros) / 2 + 1;
    }

    // because k==0 is not allowed.
    if(ones == 0 || zeros == 0) ans--;
3

You don’t explicitly need inclusion-exclusion, actually (though you can use it if you like).

One simple solution is: solve for values \leq N as usual.
For values \gt N, either you can take all of them (if zeros and ones have different parity), or you can take only the even/only the odd numbers (if zeros and ones have same parity) - in both cases the counts are easy to compute.

1 Like