PROBLEM LINK:
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;
}
}