EVENSPLIT - Editorial

editorial
,
1

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
2

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.

4

oh never mind, 110 → [11]0 → 101 → 1[01] → 011.

3 Likes
5

My Java Solution:
Lexicographically smallest string that can be obtained when all the 0’s move to the front and 1’s to the end of string. So, when length of String is less than or equal to 2, we should return string as it is. Otherwise we need to sort the string, for this I have first converted the string to char array and then sorted it and again converted char array to string and printed it. This way we can do this task with less time complexity.

Code:
import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while(t-- > 0){
int n = s.nextInt();
String str = s.next();
char[] arr = new char[str.length()];
arr = str.toCharArray(); // convert string to character Array

	    if(str.length() <= 2){
	        System.out.println(str);
	    }else{
	        int j = -1;
	         for (int i = 0; i < arr.length; i++) {
	            if(arr[i] == '0'){
	                j++;
	                char temp = arr[j];
	                arr[j] =  arr[i];
	                arr[i] = temp;
	            }
	         }
	         String str1 = new String(arr); // char array to String
	         System.out.println(str1);
	    }
	    
	}
}

}