INCREAST - Editorial

Tester: Lavish Gupta
Editorialist: Taranpreet Singh

Easy-Medium

Observations

PROBLEM

Given a string S, you can perform the following operation at most once. Choose a subsequence of S, remove it from S and append it at the end of S in the same order as it originally appeared in S.

Find the lexicographically smallest string which can be obtained.

QUICK EXPLANATION

• The subsequence of characters not chosen shall form a non-decreasing sequence of characters.
• The first character of chosen subsequence would not be strictly smaller than the last character of the non-chosen subsequence.

EXPLANATION

This problem requires a lot of observations. Instead of focusing on the subsequence of characters chosen, let’s focus on which characters are not chosen. Those characters remain at their own places, in the original order, and they appear before the chosen characters in the final string.

Observation 1: The subsequence of characters not chosen form a non-decreasing subsequence.
Proof: Let’s assume that both positions p and q are not chosen in subsequence, and p \lt q and S_p \gt S_q holds. This way, S_q appears before S_p. We can choose to include position q in subsequence, so that S_p appears first, resulting in a lexicographically smaller subsequence. This happens for each inversion pair. Hence, after removing all inversions, the characters not chosen form an increasing subsequence.

For example, for string `pqpqrqs`, the characters not chosen form string `ppqqs` and chosen characters form string `qr`.

Now that we have a non-decreasing subsequence, we need to decide what prefix of this `ppqqs` needs to be kept non-chosen. In this case, the best we can obtain is `ppqqqrs`.

First of all, the characters strictly greater than the first character of chosen subsequence needs to be removed. For example, here, the character `s` must actually be chosen, as not choosing `s` is sub-optimal.

We cannot decide whether we should keep the `qqq`, or include them in operation.

For example, consider strings `aadeacd`, it is optimal to choose subsequence `de`, and for string `aadcacd`, it is optimal to choose `dcd`. How to decide whether the last `d` should be chosen or not?

The last `d` must be included in subsequence, only if the appending the chosen subsequence results in a smaller subsequence. For the first string, including `d` would have resulted in `aaacded` which is larger than `aaacdde`.

The easiest way to decide is by iterating over chosen string, and if it has first character same as last character of non-chosen subsequence, find the first character in chosen subsequence different from the first character. For first string, that was `e`, which is greater than `d`. So we should not remove `d` from the end.

For second string, the next character was `c`, which is smaller than `d`, so it was optimal to remove `d` from the end of non-chosen characters.

The correct answer for string `aadeacd` is `aaacdde`, and the correct answer to `aadcacd` is `aaacdcd`. Try figuring out on a notebook.

Implementation

Keep a boolean array representing whether or not some position is included in the operation or not. For finding non-decreasing subsequence of characters not chosen, a stack can be used. At each character, pop from stack all characters greater than the current character.

TIME COMPLEXITY

The time complexity is O(|S|) per test case.

SOLUTIONS

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pr(x) {cout << x << '\n'; return;}
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
template<class T> inline T Bit(T x, int i) { return (x >> i) & 1;}
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
clock_t start = clock();

void solve() {
string s; cin >> s;
int n = s.size();
vector<int> last(26, -1);
for (int i = 0; i < n; i++) {
last[s[i] - 'a'] = i;
}
int dig = 0;
int mx = 26;

string ans = s, ans1, ans2;
for (int i = 0; i < n; i++) {
while (dig < 26 && i > last[dig]) dig++;
if (dig == mx) {
string ans3 = ans2, ans4;
for (int j = i; j < n; j++) {
if (s[j] == ('a' + mx)) {
ans4.push_back(s[j]);
}
else {
ans3.push_back(s[j]);
}
}
ans2 += s.substr(i);
ans = min(ans, ans1 + min(ans2, ans4 + ans3));
break;
} else if (dig > mx) {
ans = min(ans, ans1 + ans2 + s.substr(i));
break;
}
if (s[i] == ('a' + dig)) {
ans1.push_back(s[i]);
} else {
if (mx == 26) mx = (s[i] - 'a');
ans2.push_back(s[i]);
}
if (i == n - 1) ans = min(ans, ans1 + ans2);
}
assert(sz(s) == sz(ans));
cout << ans << '\n';
}

signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>
using namespace std;

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 200000;
const int MAX_N = 100000;
const int MAX_SUM_LEN = 1000000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

// int n;

void solve()
{
//cout << "start" << endl ;
string str ;
str = readStringLn(1 , MAX_N) ;
int n = str.size() ;
max_n = max(max_n , n) ;
sum_len += n ;

int suff_min[n] ;
//cout << str << endl ;

for(int i = 0 ; i < str.size() ; i++)
{
int val = (str[i] - 'a') ;
assert(val >= 0 && val < 26) ;

suff_min[i] = val ;
}

for(int i = n-2 ; i >= 0 ; i--)
{
suff_min[i] = min(suff_min[i+1] , suff_min[i]) ;
}

int unused_start = 27 ;
vector<int> retain(n) ;

for(int i = 0 ; i < n ; i++)
{
int val = (str[i] - 'a') ;
if(val == suff_min[i] && val < unused_start)
{
retain[i] = 1 ;
continue ;
}
if(val == unused_start && val == suff_min[i])
{
retain[i] = 2 ;
continue ;
}

if(unused_start == 27)
{
retain[i] = 0 ;
unused_start = val ;
}

}

// for(int i = 0 ; i < n ; i++)
//     cout << retain[i] << ' ';
// cout << endl ;

string ans1 , ans2 ;
for(int i = 0 ; i < n ; i++)
{
if(retain[i] == 1)
ans1 += str[i] ;
if(retain[i] == 1 || retain[i] == 2)
ans2 += str[i] ;
}
for(int i = 0 ; i < n ; i++)
{
if(retain[i] == 0 || retain[i] == 2)
ans1 += str[i] ;
if(retain[i] == 0)
ans2 += str[i] ;
}
// cout << ans1 << endl ;
// cout << ans2 << endl ;
cout << min(ans1 , ans2) << endl ;
return ;
}

signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t = 1;

for(int i=1;i<=t;i++)
{
solve() ;
}

assert(getchar() == -1);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_len << '\n';
cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
``````
Editorialist's Solution
``````import java.util.*;
import java.io.*;
class INCREAST{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
char[] S = n().toCharArray();

Stack<Integer> stack = new Stack<>();
for(int i = 0; i< S.length; i++){
while(!stack.isEmpty() && S[stack.peek()] > S[i])added[stack.pop()] = false;
}
StringBuilder ans = new StringBuilder(), st = new StringBuilder();
for(int i = 0; i< S.length; i++)if(added[i])ans.append(S[i]);else st.append(S[i]);

boolean bef = true;
for(int i = 1; i< st.length(); i++){
if(st.charAt(i) != st.charAt(i-1)){
bef = st.charAt(i) < st.charAt(i-1);
break;
}
}
int ind = ans.length();
if(st.length() > 0 && st.charAt(0) <= ans.charAt(ans.length()-1)){
for(int i = 0; i< ans.length(); i++){
if(bef && ans.charAt(i) >= st.charAt(0)){
ind = i;
break;
}
if(!bef && ans.charAt(i) > st.charAt(0)){
ind = i;
break;
}
}
}
StringBuilder output = new StringBuilder();
for(int i = 0, cnt = 0; i< S.length; i++){
if(cnt < ind){
output.append(S[i]);
cnt++;
}
}
}
for(int i = 0; i< S.length; i++)if(!added[i])output.append(S[i]);

pn(output.toString());
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new INCREAST().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
``````

Feel free to share your approach. Suggestions are welcomed as always.

I did this within few lines of code and now i am doubtfull weather i did it correctly or i was just lucky . can any one confirm is this approach correct .
https://www.codechef.com/viewsolution/54793824

@taran_1407 how answer of `aadcacd` is `aaacdcd` it should be `aaacddc` right?

`aadcacd` is the original string.

`aaacdcd` can be achieved by choosing `dcd` from the original string, and
`aaacddc` can be achieved by choosing `dc` from the original string.

If you compare them, `aaacdcd` is smaller than `aaacddc`, and it is the smallest possible final string, so the answer will be the `aaacdcd`.

I did something similar to the Editorial’s approach.

However, for the “whether to choose character == first unused character” part, I just created two resulting strings, one including the == characters and one that don’t.

Therefore, I could just print out the smaller of the two resulting strings as the answer to the task.

My Solution

wow, nice

aadcacd = aaa + dc + cd

here, dc>cd
hence we add cd in aaa first then dc

can any one find out what’s wrong in my solution
Solution

Your solution is O(n^2) and should TLE. Try running it on `"ababababab..."`.

@meooow I think you have misread it . I have not even used any nested loop .

Adding strings takes time linear in size of the strings.

My solution follows the editorial until it comes to deciding how much of the prefix to keep non-chosen, at which I took the quick way out and binary searched for the last prefix that gives a better result than its neighbor.

@meooow
I was not aware about this concept , i just google it found it to be correct . Thanks for it . Now i am also confused how i got AC .

@samahakal04
Try this case
ababacbcbc
correct output : aaabbbbccc (sub string:bbccc)

1 Like

https://www.codechef.com/viewsolution/54970398

@meooow @taran_1407 java, how is char c=‘a’; c=(char)(c+int) is different than char c; c=(char)(‘a’+int)?
I got wrong ans due to the first and when changed to second, got accepted, even though both got printed the same.

@wargang your code is going wrong for string aadeacd given in editorial, also for aaacccacd due to line 91, i think issues are in else operation at 87 for increasing[i]==chosen_string[i] code, hope it helps

where it fails?
can someone help.
https://www.codechef.com/viewsolution/54974389

I saw some solution( on codeChef(YouTube))… YT solution implementation is always wrong …
In this problem you can see wrong implementation on YouTube editorial.
And in Find special Node (Nov Stater 17)
question it provided wrong Implementation (On YT channel ). I confused all the day .

I want to complement . where can i report😑.