FLIPPRE - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a binary string S.
In one move, you can choose a prefix of S that has an equal number of zeros and ones, and flip all its elements.
Find the number of distinct strings reachable by performing this operation several times.

EXPLANATION:

Define the balance of a prefix, denoted b_i, to be the number of zeros minus the number of ones in this prefix.
We’re allowed to perform operations only on prefixes with balance equal to 0.
Also, flipping every element of a prefix essentially multiplies its balance by -1.

Now, suppose we perform an operation on prefix i.
Then,

  • For each j \leq i, the prefix of length j will have all its characters flipped.
    So, if b_j was originally 0, it will remain 0; and if it wasn’t originally 0, it will remain non-zero.
  • For j \gt i, the only characters flipped will be the ones till index i.
    Among them, there are an equal number of zeros and ones - so the balance b_j doesn’t change at all.
    This also means that just in the first case, b_j will remain 0 if it already was, and remain non-zero if it already wasn’t.

So, performing an operation in fact doesn’t change the set of prefixes that can be operated on - and these are exactly all those prefixes with balance zero initially.

Now, let’s find all prefixes with balance 0.
Suppose these are i_1, i_2, \ldots, i_k.

Observe that any final string will be obtained by choosing some subset of these k indices and operating on them (in some order).
This brings up a couple of questions:

  1. If the set of indices to be operated on is fixed, does the order of operations matter?
  2. Can two different sets of operations result in the same final string?

Quite nicely, the answer to both of these questions is: no.
This means each final string is uniquely characterized by which subset of indices are operated on.
There are k indices, and any subset of them can be chosen, so the answer is simply 2^k.

Proof

First, let’s prove that order of operations doesn’t matter.
Suppose we operate on prefix i, then prefix j, with i \lt j.
Then,

  • Everything in [1, i] will be flipped twice.
  • Everything in [i+1, j] will be flipped once.
  • Everything in [j+1, N] won’t be flipped at all.

If we operate on j first and then i, the exact same situation occurs, so order indeed doesn’t matter.

Now, suppose we operate on two different subsets: say
x_1, x_2, \ldots, x_r and y_1, y_2, \ldots, y_s.

Let’s look at their largest elements, x_r and y_s.
Suppose x_r \lt y_s. Then, observe that in the first set of operations (defined by x_i), the index y_s will not be flipped at all (since it’s larger than any flipped prefix).
On the other hand, in the second set of operations it will be flipped once (by the operation y_s), and so the resulting strings will definitely be different.

Similarly, if x_r \gt y_s, look at index x_r instead to see that it’ll be different in both resulting strings.
This means, if both sets of operations must have the same result, we should have x_r = y_s.

However, we can now discard both x_r and y_s from the sets; and apply the same logic to the remaining indices.
This will tell us that we should have x_{r-1} = y_{s-1}, x_{r-2} = y_{s-2}, \ldots

There are now two possibilities:

  1. r = s, i.e. the sets have equal sizes.
    Then, our argument shows that both sets are indeed equal if their resulting strings are equal.
  2. r\neq s, i.e. the sizes differ.
    Suppose r \lt s. Then, since we’re repeatedly removing one element from both sets, we’ll run out of elements in the first subset.
    This leaves the only way for the strings to be equal, to be if the empty set results in the same string as performing the operations y_1, y_2, \ldots, y_{s-r}.
    This is clearly not possible (since y_{s-r} will be flipped, for example), so we obtain a contradiction.

This proves that different subsets of indices will result in different final strings.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    string s; cin >> s;
    
    int curr = 0;
    int ans = 1;
    for (auto x : s){
        if (x == '0') curr += 1;
        else curr -= 1;
        
        if (curr == 0){
            ans *= 2;
        }
    }
    
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    dif, ct = 0, 0
    for c in s:
        if c == '0': dif += 1
        else: dif -= 1
        ct += dif == 0
    print(2**ct)