INCREAST - Editorial

#include <bits/stdc++.h>

using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int n;
map<char, int> m;
string as;
cin>>as;
n=as.size();
char b[n+1];
for(int i=0;i<n;i++){
m[as[i]]++;
}

    // cout<<"\nmap\n";

    // for(auto i:m){
    //     cout<<i.first<<" : "<<i.second<<endl;
    // }

    // cout<<"\nmap\n";
    map<char, int> tm=m;
    int pos=0;
    auto lp=tm.begin();
    for(int i=0;i<n;i++){
        if(as[i]==lp->first){
            tm[as[i]]--;
            if(tm[as[i]]==0){
                pos=i;
                lp++;
            }
        }
        else{
            break;
        }
    }

    // cout<<"pos= "<<pos<<"\n";
    string a,ia="";
    if(pos!=0)
    {
        pos+=1;
        ia=as.substr(0,pos);
        a=as.substr(pos,n-1);
        m.clear();
        n=a.size();
        for(int i=0;i<n;i++){
            m[a[i]]++;
        }
    }
    else
    {
        a=as;
    }
    
    
    // cout<<"\nmap\n";

    // for(auto i:m){
    //     cout<<i.first<<" : "<<i.second<<endl;
    // }

    // cout<<"\nmap\n";
    
    
    
    char p;
    int pindex;
    if(m.begin()->first!=a[0]){
        p=a[0];
        pindex=0;
    }
    else{
        for(int i=0;i<n;i++){
            if(a[i]!=m.begin()->first){
                p=a[i];
                pindex=i;
                break;
            }
        }
    }
    int c=0,check=0;
    auto l=m.begin();
    // cout<<"p= "<<p<<"\n";
    for(int i=0;i<n;i++){
        // cout<<"a["<<i<<"]= "<<a[i]<<" l->first= "<<l->first<<" m[l->first]= "<<m[l->first]<<" p= "<<p<<"\n";
        if(a[i]==l->first&&m[l->first]!=0&&l->first<p){
            // cout<<"hi i am in\n";
            // cout<<"a["<<i<<"]= "<<a[i]<<"\n";
            b[c++]=a[i];
            m[a[i]]--;
            a[i]='0';
        }
        
        else if(p==l->first&&p==a[i]){
            for(int dp=pindex;dp<n;dp++){
                // cout<<"inside equals\n";
                
                if(l->first>a[dp]&&a[dp]!='0'){
                    // cout<<"check=1 a["<<dp<<"]= "<<a[dp]<<" l->first= "<<l->first<<"\n";
                    check=1;
                    break;
                }
                else if(l->first<a[dp]&&a[dp]!='0'){
                    // cout<<"a["<<dp<<"]= "<<a[dp]<<"\n";
                    b[c++]=a[i];
                    m[a[i]]--;
                    a[i]='0';
                    break;
                }
            }
        }

        // cout<<"broke out\n";

        if(check)
            break;

        if(m[l->first]==0)
        {
            l++;
            while(m[l->first]==0&&l!=m.end()){
                l++;
            }
        }
        

        if(a[i]!='0')
            m[a[i]]--;
        
    }
    for(int i=0;i<n;i++){
        if(a[i]!='0'){
            b[c++]=a[i];
        }
    }
    b[c]='\0';
    if(ia==""){
        cout<<b<<"\n";
    }
    else{
        cout<<ia<<b<<"\n";
    }
}
return 0;

}

Why is this code not working
pls someone once see to it, it’s working for all dry runs

it’s output the correct but, where i am wrong

@samahakal04
Your code output is aaabbbccbc , which is wrong

I can’t figure out where my solution fails. Can anyone help out?
I have used the concept of suffix array
https://www.codechef.com/viewsolution/54941409

but the substring is chosen once and you are adding by sorting the substring which is not mentioned anywhere

if you are choosing dcd from Original string than aaca is the remain string then why are you sorting the string to get aaac

@ishan301 try out for “aaaaababcb”, your code outputs “aaaaaabbcb” whereas the correct result should be “aaaaaabbbc”.

@sourabh_0123 try out for “aaaaaabacd”, your code outputs “aaaaaaacbd” whereas the correct result should be aaaaaaabcd.

1 Like

aadcacd
xx^^xx^

If we choose these 3, then the aaac will be the remaining string.

Thanks @grey_dot I have corrected that but still I am getting WA. Can you tell any other flaws? Here is the code:
https://www.codechef.com/viewsolution/55240246