solution of Transform the String (6pts, 8pts) | google kickstart 2021 round H:
Let us first define the two operations that we can perform.
Clockwise: Changing a letter to the one following it. For example, changing from c to d.
Counter-clockwise: Changing a letter to the one preceding it. For example, changing from a to z.
Let us denote the ASCII value of a character cx by ASCII(cx). If we move the padlock from a character ca to another character cb such that ASCII(ca)<ASCII(cb), the number of operations required in clockwise direction = ASCII(cb)−ASCII(ca) and the number of operations required in counter-clockwise direction = 26−(ASCII(cb)−ASCII(ca)).
For example, if we move the padlock from c to e:
Number of operations required in clockwise direction = ASCII(e)−ASCII(c)=2.
Number of operations required in counter-clockwise direction = 26−(ASCII(e)−ASCII(c))=24.
Similarly, if we move the padlock from a character ca to another character cb such that ASCII(ca)>ASCII(cb), the number of operations required in clockwise direction = 26−(ASCII(ca)−ASCII(cb)) and the number of operations required in counter-clockwise direction = ASCII(ca)−ASCII(cb)).
For example, if we move the padlock from g to b:
Number of operations required in clockwise direction = 26−(ASCII(g)−ASCII(b))=21.
Number of operations required in counter-clockwise direction = ASCII(g)−ASCII(b)=5.
Thus minimum number of operations required to change a character in the padlock from ca to cb = min(abs(ASCII(ca)−ASCII(cb)),26−abs(ASCII(ca)−ASCII(cb))).
Let us call the above expression f(ca,cb).
Approach 1
Test Set 1
When length of F = 1 we need to change every character in S to that in F. Therefore, the answer is the sum of f(cs,cf) for every character cs in S and cf in F.
Test Set 2
For this case, F can have multiple characters.
For each character in S we need to find a character in F such that f(cs,cf) is minimized. Therefore, for every character cs in S, we iterate over all possible characters cf in F and find minimum of f(cs,cf) and add the minimum value to the final answer.
Approach 2
For each character in S, move the padlock in the clockwise direction and count the number of operations until we reach a character that belongs to F. Similarly, for the same character in S, move the padlock in the counter-clockwise direction and count the number of operations until we reach a character that belongs to F. Compare the number of operations in both directions and add minimum of the two to the final answer.
code :
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
string a,b;
int ans;
for(int i=0;i<t;i++){
cin>>a>>b;
if(b.size()==1){
ans=0;
for(int j=0;j<a.size();j++){
//cout<<(int)a[j]<<" : "<< (int)b[0]<<" "<<int('z')<<endl;
int t1=abs((int)a[j]-(int)b[0]);
int t2=abs(26-t1);
//cout<<t1<<" "<<t2<<endl;
ans+=min(t1,t2);
}
cout<<"Case #"<<i+1<<": "<<ans<<"\n";
}
else{
ans=0;
int temp;
for(int j=0;j<a.size();j++){
temp=500;
for(int k=0;k<b.size();k++){
int t1=abs((int)a[j]-(int)b[k]);
int t2=abs(26-t1);
temp=min(temp,min(t1,t2));
}
ans+=temp;
}
cout<<"Case #"<<i+1<<": "<<ans<<"\n";
}
}
}