CONVSTR - Editorial

editorial
, , , ,
113

I still don’t understand how it is optimal…means how the no of operation is minimum…can somebody explain me??

114

Thanks man! This was really helpful.

115

hello, could you find what’s wrong with my code?

int test= 0;

cin >> test;

while(test--){
    int n=0;
    cin >> n;
    char A[n];
    char B[n];
    int Amap[26] = {0};
    for(int i =0 ;i < n ;i++){
         cin >> A[i];
         Amap[A[i] - 'a'] = 1;
    }
    for(int i =0 ;i < n ;i++) cin >> B[i];

    vector<pair<int,int>> diff;
    for(int i = 0; i< n ; i++){
        if(A[i] < B[i]){
            cout << -1 ;
            break;
        }
        if(Amap[B[i] -'a'] != 1){
            cout << -1 << "\n";
            break;
        }

        if(A[i] != B[i]) diff.push_back({B[i],i});

    }

    sort(diff.begin(),diff.end(),[](const pair<int,int> & a,const pair<int,int> & b){
        return a.first > b.first;
    });
    vector<vector<int>> ans;
    vector<int> temp;
    
    for(int i =0 ; i < diff.size() ; i++){
        temp.push_back(diff[i].second);
        for(int  j= i+1; j<diff.size() ; j++){
            if(B[diff[i].second] == B[diff[j].second]){
                temp.push_back(diff[j].second);
                diff.erase(diff.begin()+j);
                j--;
            }
        }
        for(int j = 0 ; j < n ; j++){
            if(A[j] == B[diff[i].second]){
                temp.push_back(j);
                sort(temp.begin(),temp.end());
                break;
            }
        
        }
        
        ans.push_back(temp);
        temp.erase(temp.begin(),temp.end());

    }
    if(ans.size() > 0){
        cout << ans.size();
        for(auto a : ans){
            cout << "\n";
            cout << a.size() << " ";
            for(auto j : a){
            cout << j << " ";
            }
        }
        cout << "\n";
    } 
    
}


return 0;
116

I used the kind of same algorithm during contest. But still getting WA. Help Please!!!
Here is my code…
https://pastebin.com/6WPdTgQp

117

can anyone find the error why I am getting wrong answer for subtask1

118

Got it! thanks

119

can anyone help?

120

@jmm2000 It seems like there is no error. It is very crazy that your code passed the second subtask and failed the first. how frustrating that must be :joy:!

121

u need to update the characters in string a in decreasing character manner
like loop 25 to 0
see video editorial for detail explanation

122

I have no idea how it can pass second subtask but not first.

123

I wrote a program for this problem and the result was wrong answer. My logic seems to be the same as the one given in this editorial. I can’t figure out what is wrong. Could someone please help? I resubmitted my code with comments to make it easier to understand: CodeChef: Practical coding for everyone

124

hi! i used graphs! i took care of 1st 2 conditions for -1.
Then i applied dfs for each letter, if it can change a wrong i.e. to be changed character then it changes it. its like normal dfs.

I can pass all the listed test cases . i don; t know where is the problem.
code is commented.
https://www.codechef.com/viewsolution/33551224

125

:+1:

126

check my first comment above :+1:

127

for the first subtask I think number of operation is atmost 1 so what is wrong then

128

WA in subtask 2, please someone help. my code

130

JUST WONDERING…

Why you folks AVOID writing GOOD READABLE CODE while writing EDITORIALS ?

That will significantly improve the reading time & experience.

1 Like
131

Nice Editorial… :smiley:

132

Well, I have printed the subsegments in decreasing manner. That should serve the purpose.

133

well i didn’t take care of a condition when b[i]==a[i] , and other character was dependant on that a[i].