EVENSPLIT - Editorial

PROBLEM LINK:

Contest
Practice

Setter: iceknight1093
Testers: tabr
Editorialist: aryanag_adm

DIFFICULTY:

1282

PREREQUISITES:

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 → [11]0 → 101 → 1[01] → 011.

3 Likes