BALREV - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Saritesh
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Cakewalk

PREREQUISITES:

Inversions

PROBLEM:

Chef is given a binary string A of length N. He can perform the following operation on A any number of times:

  • Choose L and R (1 \leq L \leq R \leq N), such that, in the substring A[L,R], the number of $1$s is equal to the number of $0$s and reverse the substring A[L,R].

Find the lexicographically smallest string that Chef can obtain after performing the above operation any (possibly zero) number of times on A.

String X is lexicographically smaller than string Y, if either of the following satisfies:

  • X is a prefix of Y and X \neq Y.
  • There exists an index i such that X_i \lt Y_i and X_j = Y_j, \forall j such that 1 \leq j \lt i.

EXPLANATION:

The first intuition when we read the problem is, can we sort the string? If Yes, we have got our answer, as the sorted string is the lexicographically smallest possible string that we can get.

Let’s see if we can sort the string. Let there be an index i such that S_i = 1 and S_{i+1} = 0. If there is no such index i, then we have already sorted our string. Otherwise, the substring S_iS_{i+1} is a valid substring, and we can reverse it, making it 01. We can repeat this process as long as we can find such index i, and hence finally ending up with a sorted string.

But how to prove that the above process will eventually terminate?

We will prove this by using the number of inversions. It is recommended to first understand the concept of inversions.

Note that when we perform the above operation, the number of inversions decreases by 1. Because the initial number of inversions is finite, and the final number of inversions will be greater than or equal to 0, we can perform the above operation only finite number of times, eventually reaching a state where we cannot find a valid index i. In other words, the number of inversions will become 0, and hence we will end up getting our sorted string.

TIME COMPLEXITY:

We need to sort the given string - O(N \cdot \log{N}) for each test case.

SOLUTION:

Editorialist's Solution 
#define ll long long
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>
using namespace std ;


void solve()
{
    ll n ;
    cin >> n ;
    string a ;
    cin >> a ;

    sort(a.begin() , a.end()) ;
    cout << a << endl ;
    return ;
}

 
int main()
{   
    
    ll t = 1 ;
    cin >> t ;
    while(t--)
    {
        solve() ;
    }
    
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;
}
2

Can do this in O(n) time and O(n) space by counting number of zeroes and then making a separate string output to store our sorted string. Or you could change in the given string itself for O(n) time and O(1) space.

2 Likes