CONVSTR - Editorial

editorial
, , , ,
48 
void solve(string &s1,string &s2,lli n){

if(s1==s2){
    cout<<0<<endl;
    return;
}

vector<vector<lli>>ans;
for(char ch='z';ch>='a';ch--){
    lli flag1=0;
    lli flag2=0;
    vector<lli> ind;
    loop(i,n){
        
        if(s1[i] > ch  and  s2[i]==ch){
            ind.pb(i);
            flag1=1;
        }
        
        if(s1[i]==ch  and flag2==0){
            flag2=1;
            ind.pb(i);
        }
    }
    
    if(flag1 and flag2){
        
        for(auto xt : ind )
            s1[xt] = ch;
        
        ans.pb(ind);
    }
}

if(s1!=s2)
{
    cout<<-1<<endl;
    return;
}
else
{
    cout<<sz(ans)<<endl;
    for(auto xt : ans){
        cout<<sz(xt)<<" ";
        for(auto xr : xt)
            cout<<xr<<" ";
        cout<<endl;
    }
    
    return;
}

}

O(N*(26)) solution : CodeChef: Practical coding for everyone

49

I used that only, only once I used ascii. I have to do a lot of practice, this was only my 2nd contest after cook-off. I hope by practice, I can shorten my code. Which corner cases are you telling about?

50

sorry that test case was wrong!!
upd:- I m trying to understand it, plz wait and it will be helpful if u can tell the logic behind it. thank you

1 Like
51

First case where it fails is abc and aaa minimum operation required is 1 whereas your code outputs 2.(Simply select 0,1,2 and it will convert 1st string to aaa in one operation).
Another case is abc aab .Here the minimum operation is correct but the order is different .
Your code in first operation selects 0 and 1 which will make 1st string aac and in second operation your code selects 1 and 2 which means it will make it aaa which is not equal to aab.
so changing the order will make it correct i.e select 1 and 2 first(it will make abb) and then 0 and 1.(it will make aab which is equal to 2nd string).Hope that helps

52

Can somebody help me to find whats wrong with my solution.
My solution-CodeChef: Practical coding for everyone

53

Bro ur solution is too lengthy ā€¦and many if else :frowning_face:

54

1
5
abcdd
aabcd

55

Thanks

56

Mine?

59

sorry bro i got the logic but i dont know why it is not working

1 Like
60

Thank you for the awesome problem :heart_eyes: :heart_eyes:. Loved it!

1 Like
61

glad you liked it :smile:

4 Likes
62

Simplest O(n*(sizeof alphabet)) approach. Got AC on first attempt.
https://www.codechef.com/viewsolution/33467393

63

In the example test case, why do you need to have the

2
3 1 2 4
3 0 1 3

Why canā€™t it be

2
2 1 0
2 2 4

Because all that we need to do is replace the character at position 1 with the character 0 because the position at 1 is ā€˜bā€™ and character at position 0 is ā€˜aā€™.

64

great editorial @taran_1407

65

Yes, it is possible. Multiple Solutions can exist. Both Solutions satisfy all the conditions.

66

I got it bro. I understood the question wrong.

67

The first case given in the quick explanation part may not be true as it is not applicable in the following example: (Ax<Bx; string is not convertible)
aab aba
Here even though a<b ie. A[1]<B[1], still i could choose the subset {2} and still convert string A to string B in two steps.
Can anyone explain this?

68

Here is my solution, it passes first subtaskā€¦and i m not able to figure out what is wrong for the second subtask.
https://www.codechef.com/viewsolution/33506548

71

All solutions , the setterā€™s, testerā€™s, and the editorialistā€™s solutions are correct. If they are a bit difficult (they are to me and many beginners who are yet to learn a lot) read the explanation and try to do it yourself. You can also refer others solutions now.

1 Like