PERMEX - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

Easy

PREREQUISITES:

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 :frowning:

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;
}