INCREAST - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Soumyadeep Pal
Tester: Lavish Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

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 readString(int l,int r,char endd){
    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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,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;
    
    t = readIntLn(1,MAX_T);
    
    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<>();
        boolean[] added = new boolean[S.length];
        for(int i = 0; i< S.length; i++){
            while(!stack.isEmpty() && S[stack.peek()] > S[i])added[stack.pop()] = false;
            stack.add(i);
            added[i] = true;
        }
        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(added[i]){
                if(cnt < ind){
                    output.append(S[i]);
                    cnt++;
                }
                else added[i] = false;
            }
        }
        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;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        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());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

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

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

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

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?

could you explain it, please?

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

please help why this is giving WA. I’ve implemented the editorial’s idea.
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

- YouTube You can see i this video :expressionless::expressionless::expressionless::expressionless:

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 :expressionless::expressionless::expressionless::expressionless::expressionless:.

I want to complement . where can i report😑.