 # EVENSPLIT - Editorial

Setter: iceknight1093
Testers: tabr

1282

Sorting

# PROBLEM:

You are given a binary string S.

You are allowed to perform the following operation:

• Select any subsequence of length 2k
• Move the elements at the first k indices of the sequence to the beginning of the string, and those at the last k indices to the end of the string.

You may perform this operation any number of items. Output the lexicographically minimal string that you can reach.

# EXPLANATION:

Note that if |S| = 2, then the operations are ineffective, i.e, they do not change S. Therefore, in this case the answer is S itself.

Else, I claim that we can perform operations to sort S completely.

Proof:
If the string consists of only 1's or only 0's then we are done. Else, consider the element S_2. If S_2 = 1, then we perform the operation with the chosen subsequence being \{1, 2\}. This keeps S_1 fixed, and sends S_2 = 1 to the end of the string. Else, we perform the operation with the chosen subsequence being \{2, N\}. This keeps S_N fixed and sends S_2 = 0 to the beginning of the string.

Without loss in generality, assume that S_1 = 0 now (if S_N = 1 instead, you can perform symmetric operations). For every index i such that S_i = 1, you can now perform the operation \{1, i\}, which will keep S_1 the same but send S_i = 1 to the end of the string. Doing this repeatedly will sort the string.

Therefore, if N = 2 then we just output S. Else, we sort S and output that.

# TIME COMPLEXITY:

Both O(N) and O(N \log N) are easy.

My solution takes O(N \log N).

# SOLUTION:

Editorialist's Solution
``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
if(n > 2) sort(s.begin(), s.end());
cout<<s<<endl;
}
}
``````
1 Like

If string are like this, ‘10’, ‘110’, ‘1110’ i.e. a prefix of 1s with only one 0
then we have to print the same string cause the string cannot be modified with the given operations.

oh never mind, 110 → 0 → 101 → 1 → 011.

3 Likes