PERMEX - Editorial

Setter: Nabil Boudra
Tester: Harris Leung
Editorialist: Kanhaiya Mohan

Easy

MEX

PROBLEM:

You are given an integer N and a (0-indexed) binary string A having length N+1.

Find any permutation P of {0,1,2,...,N-1} (or determine that it does not exist) that satisfies the following conditions for all i (0 \le i \le N):

• if A_i = 0: No contiguous segment of P has \texttt{mex} equal to i
• if A_i = 1: There exists at least one contiguous segment of P that has \texttt{mex} equal to i

If multiple permutations exist that satisfy the given conditions, print any.

Note: \texttt{mex} of a segment is the smallest non-negative number that does not occur in that segment.

EXPLANATION:

When is the answer -1?

We have to find a permutation P of \{0,1,2,...,N-1\}.

• Consider a subarray of length 1, containing only the i^{th} element. If P_i \neq 0, for this subarray of length 1 , the MEX is 0.
Since N \geq 2, there is always a subarray of length 1 such that it does not contain any 0 and thus, its MEX would be 0. This implies that the value of A_0 must be 1.

• Similarly, consider a subarray of length 1 which contains only the i^{th} element such that P_i = 0. For this subarray, the MEX is 1.
Since P always contains a 0, there is always a subarray of length 1 such that its MEX is 1. In other words, the value of A_1 must be 1.

• Consider the subarray of length N. This includes the whole permutation P. Thus, all the elements in the range [0, N-1] are included in this subarray and its MEX is N.
This implies that the value of A_N must be equal to 1.

To conclude, if any value out of A_0, A_1 or A_N is 0, no possible permutation exists which satisfies the given conditions and thus, the answer is -1.

If the values of A_0, A_1 and A_N are 1, we can always construct a solution.

We can construct a permutation P such that, for all the indices i (i>0) and A_i = 1, the MEX of the prefix of length i is equal to i. To construct this:

• Start with the identity permutation. This means we set P_i = i for all (0 \leq i \leq N-1). Currently, for all prefixes of this permutation, the MEX of the prefix is equal to the length of the prefix.

• Consider j as the first index where A_i = 0. Since for all indices <j, A_i = 1, we keep the prefix of length (j-1) as the identity permutation. Thus, P_k = k for all (0 \leq k <j-1).
If we keep the value of the (j-1)^{th} element (0-based indexing) as (j-1), we would have a subarray (prefix of length j) for which the MEX is equal to j.
Since A_j = 0, we have to avoid this. For that, we can swap the values P_{j-1} and P_{j}. Now, the resultant permutation looks like [0, 1, 2, …, j-2, j, j-1, j+1,..., N-1].
Note that in this permutation, there exists no subarray, where MEX of the subarray is j.

• Based on the same observation, for all indices i where A_i = 0, we swap the (i-1)^{th} and i^{th} elements of P (0-based indexing).

• If A_i = 1, the (i-1)^{th} element of P remains unchanged. Thus, the MEX of the prefix of length i is equal to i only when A_i = 1.

P.S. This construction guarantees the lexicographically minimum permutation P which satisfies all the conditions.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
string a;
cin>>n>>a;
if(a[0]==a[1]&&a[1]==a.back()&&a[0]=='1'){
cout<<"Yes\n";
vector<int> res(n);
for(int i=0;i<n;i++) res[i]=i;
for(int i=0;i<n;i++) if(a[i]=='0') swap(res[i],res[i-1]);
for(int&x:res)
cout<<x<<" ";
cout<<'\n';
}
else
cout<<"No\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
cin >> t;
while(t--) solve();
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
int n;
int a[300001];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
cin >> n;
for(int i=0; i<=n ;i++){
char c;cin >> c;
a[i]=c-48;
}
if(a[0]==0 || a[1]==0 || a[n]==0){
cout << "No\n";continue;
}
cout << "Yes\n";
int ptr=1;
cout << "0 ";
while(ptr!=n){
int nx=ptr+1;
while(!a[nx]) nx++;
for(int i=nx-1; i>=ptr ;i--) cout << i << ' ';
ptr=nx;
}
cout << '\n';
}
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
if(s[0]=='0' || s[1]=='0' || s[n]=='0'){
cout<<"No";
}
else{
cout<<"Yes\n";
int p[n];
for(int i = 0; i<n; i++){
p[i] = i;
}
for(int i=1; i<=n; i++){
if(s[i]=='0'){
swap(p[i-1], p[i]);
}
}
for(int i = 0; i<n; i++) cout<<p[i]<<' ';
}
cout<<endl;
}
return 0;
}

2 Likes

not able to understand editorial

4 Likes

let’s take binary string as S, if(S[0] == ‘0’) what does this means? … this means in resulting permutation there should not contain any contiguous segment having Mex 0. but in array we have values greater than 1 that has Mex 0 so it contradicts thus we always have S[0] to be 1 if not answer never exist . similarly if(S[1]==‘0’) in permutation there always be value 0 with which Mex will be 1 so this also contradicts. but if(s[2] == ‘0’) we can make a permutation [0,2,1] with which we can hide Mex == 2.just think what will be the Mex of [0,1,2,… n-1] ? is will be N . So in Given String S[N] must be ‘1’. Except these 3 cases we can always make a permutation to hide Mex(2…n-1).
lets understand string s = “110101”
with those cases our default Mex(curmex) will be 2 ( [0,1]).
iterate I from 2 to n-1.
if(s[I]==‘1’)
{
// curmex is 2 and I is 2 and since s[I] == ‘1’ this means Mex = 2 have to be legal.
so we just push this I into permutation (as current permutation is [0,1] )
also curmex will increase by 1 (as current permutation is [0,1,2])
}
if(s[I]==‘0’)
we don’t want our curmex to be equal to I so here we will use greedy approach
since current permutation is [0,1,2] and Mex is 3 but we don’t want 3 so if we just push 3 before 2 then what happens? … [0,1,3,2] this will make Mex array to be (1,2,2,4). you can see there is no 3 and that what we want.

3 Likes

What is wrong here, anyone please?
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
if(s[0]!=‘1’ || s[1]!=‘1’ || s[n]!=‘1’)
{
cout<<“No”<<endl;
return;
}
vector ans(n);
ans[0]=0;
int gap=-1;
int k=1;
cout<<“Yes”<<endl;
rep(i,2,n+1)
{
if(s[i]==‘1’)
{
if(gap==-1)
ans[k++]=i-1;
else
ans[gap]=i-1,gap=-1;
}
else
{
if(s[i-1]==‘1’)
gap=k,ans[k+1]=i-1,k+=2;
else
ans[k++]=i-1;
}
}
rep(i,0,n) cout<<ans[i]<<" ";
cout<<endl;
}