MARBLE - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Reyaan Jagnani
Tester: Sarvesh Kesharwani
Editorialist: Sarvesh Kesharwani

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

We are given 2 strings, S and P, of equal length. The task is to find the minimum number of operations required to convert the string P into S. Both the strings consist of lowercase english alphabets and/or a character ?. The character ? can be present in either of the strings, both of them or none of them.

First of all, you are supposed to choose a lowercase english alphabet and replace all the occurrences of character ? with that alphabet. In case ? is present in both the strings, every ? should be assigned the same character. Now, since both the strings consist of only lowercase english alphabets, you can apply the following operations.

In one operation, you can do any one of the following:

  • Convert any vowel to any consonant.
  • Convert any consonant to any vowel.

Find the minimum number of operations to be performed on the string P to make it equal to the string S.

EXPLANATION:

Suppose we replace every ? with 'a'. Now we will iterate through the strings,
at ith index,
if S_i is vowel and P_i is consonant, in one move we can change P_i from consonant to vowel.
if S_i is consonant and P_i is vowel, in one move we can change P_i from vowel to consonant.
if S_i is consonant and P_i is consonant :
if S_i\neq P_i, in two moves we can make S_i = P_i i.e. change P_i to a vowel, again change it to consonant equal to S_i.
if S_i = P_i, no moves are required as they are already equal.
if S_i is vowel and P_i is vowel,
if S_i\neq P_i, in two moves we can make S_i = P_i i.e. change P_i to a consonant, again change it to vowel equal to S_i.
if S_i = P_i, no moves are required as they are already equal.

After the iteration we will get the number of moves required to change string P to string S.
Similarly, we can replace every alphabet with the '?' and count the number of moves using the above logic.
Output the minimum number of moves calculated by replacing all the alphabets with ’?’.

TIME COMPLEXITY:

O(26*N)

SOLUTION

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<char,int> vowel;
    vowel['a'] = 1, vowel['e'] = 1, vowel['i'] = 1, vowel['o'] = 1, vowel['u'] = 1;
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s1,s2;
        cin>>s1>>s2;
        int ans = n*2;
        for(char a1 = 'a'; a1<='z'; a1++)
        {
            int cnt = 0;
            for(int i=0; i<n; i++)
            {
                char ch1 = s1[i];
                char ch2 = s2[i];
                if(ch1=='?') ch1 = a1;
                if(ch2=='?') ch2 = a1;
                if(ch1==ch2) continue;
                if((vowel.find(ch1)==vowel.end() && vowel.find(ch2)==vowel.end()) || (vowel.find(ch1)!=vowel.end() && vowel.find(ch2)!=vowel.end()))
                {
                    cnt+=2;
                }
                else cnt++;
            }
            ans = min(ans, cnt);
        }
        cout<<ans<<endl;
    }
    return 0;
}


Python Solution
vowel={"a","e","i","o","u"}

def solve(N,a1,a2,v):
    ans=0
    for i in range(N):
        a,b=a1[i],a2[i]
        if (a=="0"):
            a=v
        if(b=="0"):
            b=v

        if (a==b):
            continue
        else:
            flag=0
            if (a in vowel):
                flag=flag+1
            if (b in vowel):
                flag=flag+1

            if(flag==1):
                ans=ans+1
            else:
                ans=ans+2
                

    return ans
            

T=int(input())
for _ in range(T):
    N=int(input())
    s1=list(input())
    s2=list(input())

    ans=2*N
    for a in range(26):
        ans=min(ans,solve(N,s1,s2,chr(96+a)))
    print(ans)
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

set<char> vowel;

void solve()
{     
     vowel.insert('a');
     vowel.insert('e');
     vowel.insert('i');
     vowel.insert('o');
     vowel.insert('u');
     int tc;cin>>tc;while(tc--)
     {
         long long n; 
         string s1,s2;
         cin>>n>>s1>>s2;
         vector<long long> ans(26);
         for(int i=0;i<26;i++){
            int cnt = 0;
            for(int j=0;j<n;j++){
               char c1 = s1[j];
               char c2 = s2[j];
               if(s1[j] == '?')s1[j] = char('a' + i);
               if(s2[j] == '?')s2[j] = char('a' + i);
               if(s1[j] != s2[j]){
                  bool ok1 = vowel.find(s1[j]) != vowel.end();
                  bool ok2 = vowel.find(s2[j]) != vowel.end();
                  if(ok1^ok2)cnt++;
                  else cnt+=2;
               }
               s1[j] = c1;
               s2[j] = c2;
            }
            ans[i] = cnt;
         }
         cout<<*min_element(ans.begin(),ans.end())<<'\n';
     }
}

int main()
{    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}


3 Likes

I loved the idea of checking every alphabet on the place of β€˜?’. It’s quite simple but one thing was not clear to me during contest is that whether putting any character that belongs to string itself will give the best result or any other character. Obviously the former option is right so it first checked which character of vowels and consonants appear the most in string at '?'s corresponding position, then I replaced with that. Very complex though…

2 Likes

#include<bits/stdc++.h>

using namespace std;

bool isvowel(char m){

if( m=='a' || m=='e' || m=='i' || m=='o' || m=='u')

return true;

else

return false;

}

int main(){

int T;

cin>>T;

while(T–){

int n; int count =0;

cin>>n;

string s; string p;

cin>>s>>p;

for(int i=0;i<n;i++){

if(s[i]=='?')

s[i]='a';

else if(p[i]=='?')

p[i]='a';

}

for(int i=0;i<n;i++){

if(isvowel(s[i])==isvowel(p[i]))

count = count+2;

else if(s[i]==p[i]){

   continue;

}

else

count++;

}

cout<<count<<endl;

}

return 0;

}

pls tell me my mistake…!!!

3 Likes

You are replacing β€˜?’ every time with char β€˜a’, but this is not optimal for every test case, We have to brute force over every 26 alphabets calculate total steps taken to convert string p to string s for β€˜a’, β€˜b’, β€˜c’, … β€˜z’, then after calculating for every alphabet we have to find out the alphabet for which it took minimum steps and return that as our output.
SOME OBSERVATIONS:

  1. If the char is vowel we can change to consonant and vice-versa, hence if both the char at s[i] and p[i] is vowel or consonant it will take two steps overall {first changing vowel to consonant then consonant to vowel}
//Setters solution:
for(char a1 = 'a'; a1<='z'; a1++) // looping over all aplhabets
        {
            int cnt = 0;
            for(int i=0; i<n; i++)
            {
                char ch1 = s1[i];
                char ch2 = s2[i];
                if(ch1=='?') ch1 = a1;
                if(ch2=='?') ch2 = a1;
                if(ch1==ch2) continue;
                if((vowel.find(ch1)==vowel.end() && vowel.find(ch2)==vowel.end()) || (vowel.find(ch1)!=vowel.end() && vowel.find(ch2)!=vowel.end())) //calculating steps required for a specific alphabet
                {
                    cnt+=2;
                }
                else cnt++;
            }
            ans = min(ans, cnt); //Finding out which takes minimum steps and return the final output
2 Likes

ohh i got it… thanks for pointing out mistake…

again it is wrong pls find my mistake

#include<bits/stdc++.h>

using namespace std;

bool isvowel(char m){

if( m=='a' || m=='e' || m=='i' || m=='o' || m=='u')

return true;

else

return false;

}

int main(){

int T;

cin>>T;

while(T–){

int n; int count =0; int ans = INT_MAX;

cin>>n;

string s; string p;

cin>>s>>p;

for(int j =β€˜a’;j<=β€˜z’;j++){

for(int i=0;i<n;i++){

if(s[i]=='?')

s[i]=j;

else if(p[i]=='?')

p[i]=j;

}

for(int i=0;i<n;i++){

if(isvowel(s[i])!=isvowel(p[i]))

count = count+2;

else if(s[i]==p[i]){

   continue;

}

else

count++;

}

ans=min(ans,count);

}

cout<<ans<<endl;

}

return 0;

}

and in place of T_,write T–

1 Like

you have to write β€˜if’ in place of β€˜else if’

1 Like

#include<bits/stdc++.h>
using namespace std;
bool isvowel(char m){
if( m==β€˜a’ || m==β€˜e’ || m==β€˜i’ || m==β€˜o’ || m==β€˜u’)
return true;
else
return false;
}
int main(){
int T;
cin>>T;
while(T–){
int n; int count =0; int ans = INT_MAX;
cin>>n;
string s; string p;
cin>>s>>p;

for(int j =β€˜a’;j<=β€˜z’;j++){
for(int i=0;i<n;i++){
if(s[i]==’?’)
s[i]=j;
if(p[i]==’?’)
p[i]=j;
}

for(int i=0;i<n;i++){
if(isvowel(s[i])!=isvowel(p[i]))
count = count+2;
else if(s[i]==p[i]){
continue;
}
else
count++;
}
ans=min(ans,count);
}
cout<<ans<<endl;

}
return 0;
}

again it is not giving correct output…

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

ll mod = 1000000007;

int main()

{

int t;

cin >> t;

while (t–)

{

int n;

cin >> n;

char vov[5] = {'a', 'e', 'i', 'o', 'u'};

string a, b;

cin >> a >> b;

string ar = a;

string br = b;

int x = a.compare(b);

ll ct = INT_MAX;

if (x == 1)

{

  cout << 0 << endl;

}

else

{

  for (int o = 97; o < 123; o++)

  {

    int nct = 0;

    for (int i = 0; i < n; i++)

    {

      int v1 = 0;

      int v2 = 0;

      if ((a[i] != b[i]))

      {

        if ((a[i] == '?') || (b[i] == '?'))

        {

          if (a[i] == '?')

          {

            a[i] = o;

          }

          else

          {

            b[i] = o;

          }

        }

        if (a[i] != b[i])

        {

          for (int j = 0; j < 5; j++)

          {

            if (a[i] == vov[j])

              v1++;

            if (b[i] == vov[j])

              v2++;

          }

          if ((v1 - v2) == 0)

          {

            nct += 2;

          }

          else

            nct++;

        }

      }

    }

    if (nct < ct)

    {

      ct = nct;

    }

    a = ar;

    b = br;

  }

  cout << ct << endl;

}

}

return 0;

}

please tell me my mistake!!

Optimizing the code for special cases by skipping some letters in some cases only makes it more complicated and potentially buggy. If CodeChef testcases are strong and stress the worst possible scenario (all letters are present), then such optimization is only a liability and won’t help to safeguard against TLE.

i have tried many time to submit my solution it is showing wrong again and again

#include<bits/stdc++.h>
using namespace std;
bool isvowel(char m){
if( m==β€˜a’ || m==β€˜e’ || m==β€˜i’ || m==β€˜o’ || m==β€˜u’)
return true;
else
return false;
}
int main(){
int T;
cin>>T;
while(T–){
int n; int count =0; int ans = INT_MAX;
cin>>n;
string s; string p;
cin>>s>>p;

for(int j =β€˜a’;j<=β€˜z’;j++){
for(int i=0;i<n;i++){
if(s[i]==’?’)
s[i]=j;
if(p[i]==’?’)
p[i]=j;
}

for(int i=0;i<n;i++){
if(isvowel(s[i])!=isvowel(p[i]))
count = count+2;
else if(s[i]==p[i]){
continue;
}
else
count++;
}
ans=min(ans,count);
}
cout<<ans<<endl;

}
return 0;

TRY THIS

#include<bits/stdc++.h>

using namespace std;

bool isvowel(char m){

if( m==β€˜a’ || m==β€˜e’ || m==β€˜i’ || m==β€˜o’ || m==β€˜u’)

return true;

else

return false;

}

int main(){

int T;

cin>>T;

while(T–){

int n; int ans = INT_MAX;

cin>>n;

string s; string p;

cin>>s>>p;

string x=s;

string y=p;

for(int j =β€˜a’;j<=β€˜z’;j++){

int count =0;

for(int i=0;i<n;i++){

if(s[i]==’?’)

s[i]=j;

if(p[i]==’?’)

p[i]=j;

}

for(int i=0;i<n;i++){

if(s[i]==p[i]){

continue;

}

if(isvowel(s[i])==isvowel(p[i]))

count = count+2;

else

count++;

}

ans=min(ans,count);

s=x;

p=y;

}

cout<<ans<<endl;

}

return 0;

}

why isn’t my code working?

from collections import Counter
lstc=[β€˜a’,β€˜b’,β€˜c’,β€˜d’,β€˜e’,β€˜f’,β€˜g’,β€˜h’,β€˜i’,β€˜j’,β€˜k’,β€˜l’,β€˜m’,β€˜n’,β€˜o’,β€˜p’,β€˜q’,β€˜r’,β€˜s’,β€˜t’,β€˜u’,β€˜v’,β€˜w’,β€˜x’,β€˜y’,β€˜z’]
lstv=[β€˜a’,β€˜e’,β€˜i’,β€˜o’,β€˜u’]
t=int(input())
for i in range(t):
n=int(input())
s=input()
p=input()
ans=n
for y in lstc:
s = s.replace(’?’, y)
p = p.replace(’?’, y)
c = 0
for u in range(n):
if s[u] != p[u]:
if ((s[u] not in lstv) and (p[u] not in lstv)) or ((s[u] in lstv) and (p[u] in lstv)):

                c += 2
            else:
                c += 1
    if c<ans:
        ans=c
print(ans)

Hi @amarbudhiraja

This video was helpful for me in understanding this, I thought you’d find it helpful too.
https://youtu.be/yFzPb1wtxEY