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:
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, itsMEX
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 itsMEX
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 theMEX
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, whereMEX
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;
}