# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* everule1

*apoorv_me*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1741

# PREREQUISITES:

None

# PROBLEM:

Given a binary string S of length N, decide whether it represents a fair distribution or not.

A distribution is fair if, for any non-decreasing array v of non-negative integers, the difference between the values marked zero and the values marked one doesn’t exceed v_N (the maximum value).

# EXPLANATION:

Intuitively, if there are “too many zeros” or “too many ones”, it feels like the distribution isn’t going to be fair.

Indeed, suppose there are X zeros and Y ones in S.

Then, if |X-Y| \gt 1, it’s easy to see that the distribution is unfair: simply take the array v = [1, 1, 1, \ldots 1], and the difference between the values is exactly |X-Y| which is larger than v_N = 1.

So, for the distribution to be fair, we *must* have |X-Y| \leq 1.

Next, notice that v is a sorted array of **non-negative** integers.

In particular, we’re allowed to use zeros.

This means we can also consider arrays of the form v = [0, 0, 0, \ldots, 0, 1, 1, \ldots, 1] - which in turn means that if any *suffix* of S has too many zeros (or ones), S can’t be a fair distribution.

That is, we have the following condition:

For every 1 \leq i \leq N, let the suffix S_iS_{i+1}S_{i+2}\ldots S_N of S have X_i zeros and Y_i ones.

Then, if |X_i - Y_i| \gt 1 for any i, S can’t be a fair distribution.

As it turns out, this condition is not only necessary, but also sufficient!

## Proof

Let’s reverse everything, and assume we’re working with prefixes instead.

Without loss of generality, we can assume S_1 = 1 as well (if not, flip all the elements and the fairness of the distribution doesn’t change).

In this situation, v will be a non-increasing array with v_1 being the maximum; and we want v_N \geq 0.

Let X_i be the number of zeros among the first i characters, and Y_i be the number of ones.

Suppose |X_i - Y_i| \leq 1 for every 1 \leq i \leq N.

Our claim is that if this is satisfied, then S represents a fair distribution.

First, note that when i is even, |X_i - Y_i| \leq 1 is possible if and only if |X_i - Y_i| = 0; that is, X_i = Y_i.

In other words, each even-length prefix should have an equal number of zeros and ones.

Fix a non-increasing array of non-negative integers v.

Let’s define P_i to be the *prefix difference* of the distribution, with respect to this array.

That is, P_i will denote the difference between Alice’s and Bob’s values, among the first i elements.

So,

- If S_i = 1, P_i = P_{i-1} + v_i.
- Else, P_i = P_{i-1} - v_i.

**Claim:** For each 1 \leq i \leq N, we’ll have |P_i| \leq v_1.

In particular, if i is even, we’ll further have |P_i| \leq v_1 - v_i.

**Proof:** This is clearly true for i = 1, since 0 \leq P_1 = v_1 \leq v_1.

For i = 2, our earlier observation about X_i = Y_i for even i shows that S_2 = 0 must hold, so P_2 = v_1 - v_2 is forced; also satisfying the claim.

We’ll prove for the other indices via induction.

Consider some i \geq 2 that’s *even*.

By the inductive hypothesis, we know |P_i| \leq v_1 - v_i.

Since v_{i+1} \leq v_i, neither P_i + v_{i+1} nor P_i - v_{i+1} can exceed v_1 in absolute value; so |P_{i+1}| \leq v_1 is true.

Then, the condition on having an equal number of zeros and ones means that P_{i+2} = P_i + v_{i+1} - v_{i+2}, or P_{i+2} = P_i - v_{i+1} + v_{i+2}.

Once again, it’s not hard to see that |P_{i+2}| \leq v_1 - v_{i+2} will be satisfied. Visually:

- If v_{i+1} moves the difference towards v_1, v_{i+2} will move it away.
- if v_{i+1} moves the difference away from v_1, v_{i+2} \leq v_{i+1} means that it can’t make up the difference enough to even get past v_1 - v_i.

This completes the proof.

Checking this condition is fairly easy in \mathcal{O}(N) time, simply compute the number of zeros and ones in each suffix of S.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Author's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
void solve(){
int n;
cin>>n;
string s;
cin>>s;
reverse(s.begin(), s.end());
int pref = 0;
int mx = 0;
for(auto &c : s){
if(c == '0') --pref;
else ++pref;
mx = max(mx, abs(pref));
}
if(mx > 1){
cout<<"NO\n";
}
else{
cout<<"YES\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
}
```

## Tester's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
string s; cin >> s;
int sm = 0;
for(int i = n - 1 ; i >= 0 ; i--) {
sm += (s[i] == '1' ? 1 : -1);
if(abs(sm) >= 2) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
int tests; cin >> tests;
while(tests--)
solve();
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
s = input()
ans, dif = 'Yes', 0
for x in reversed(s):
dif += x == '0'
dif -= x == '1'
if abs(dif) > 1: ans = 'No'
print(ans)
```