# FAIR_DISTRIB - Editorial

Author: everule1
Tester: apoorv_me
Editorialist: iceknight1093

1741

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)

3 Likes

The proof is well written, thanks!

1. Why is it that the implementation/proof requires the input to be reversed?

i.e. The requirement of |Xi - Yi| <= 1 applied across all input prefixes should also work, right (since this check should also ensure a “balanced” distribution)? And yet when I tried submitting that, it failed. Why?

1. And how does one intuitively think of computing across suffixes instead of prefixes?

It does not work, no.

The order matters here because of the way in which v is sorted.
The statement mentions we consider all arrays of the form 0 \leq v_1 \leq v_2 \leq \ldots \leq v_N.
The later elements are larger (and the inequality is with respect to v_N), which is why suffixes are more important.
More concretely, you can set some prefix of v to be 0's, which essentially ignores that prefix entirely (so of course, you’re left with some suffix which should represent a fair distribution of the positive elements of v).

For instance, consider S = 100.
This is not a fair distribution because it fails on v = [0, 1, 1], but if you look at prefixes you’d conclude it is a fair distribution.

This should be answered by what I mentioned above: because of the order on v, you can ignore some prefix by setting it to 0 (meaning you’re left with a suffix).
You can’t ignore a suffix the same way.

The implementation doesn’t require explicit reversal, you can iterate from N down to 1 too; as long as you work with suffixes in some way you’ll be fine.

For the proof, I chose to reverse it just so that notation would be cleaner for me to write
Notice I wrote about even/odd indices, and I’d rather say “even i” than “even (N-i)” over and over.
Apart from that, note that when I reversed the string I also specifically made note that I reversed v as well, so the proof deals with a decreasing v, not an increasing one (and the condition for a balanced distribution depends on v_1, not v_N).

This is a good testcase to validate against. Thanks. I understand now that the suffixes carry more weight because of the non-decreasing nature.

Your remaining responses make sense to me, my original intuition was that from a prefix-standpoint, as long as an opposing Si appeared, it would undo the work of the previous Si by atleast the same amount. Which is why if there was 2 or more matching consecutive Si without being followed by a counter Si, only then would it allow for an unfair distribution.

I guess I didn’t realize that abusing prefixes = 0 could generate a test case that breaks this logic - I was too focused on positive tests than negative tests. Checking the suffixes instead would ensure that such prefixes that could be set to 0, do not influence the following processing of later elements that may be non-zero (and therefore more relevant than a prefix).

Thanks!

1 Like