INCREAST - Editorial

editorial
, ,
22

#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

23

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

24

@samahakal04
Your code output is aaabbbccbc , which is wrong

25

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

26

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

27

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

28

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

29

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

1 Like
30

aadcacd
xx^^xx^

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

31

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