ACM14KG3 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Easy

PREREQUISITES:

Directed Graph, Floyd Algorithm

PROBLEM:

There are M mappings from lower case English alphabet to lower case English alphabet. Using these mappings, can one transform a string S to another string T?

EXPLANATION:

Let Can[i][j] denote whether the lower case English character i could be transformed to j in some combinations of given mappings. Initially, only Can[i][i] and the given mappings are set to true.

Then, the Floyd algorithm used to compute the transiting property can be adopted here, as the following:

For k = 1 to 26:
    For i = 1 to 26:
        For j = 1 t 26:
           Can[i][j] |= Can[i][k] && Can[k][j]

After that, we have known all possible transformations between lower case characters. To answer the question, we just need to check the reachability between corresponding characters of the two strings S and T.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions will be available soon.

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

@shangjingbo Solution link isn’t available

3

#include <bits/stdc++.h>
using namespace std;
#define endl “\n”
bool parent[26][26];
int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t–)
{
memset(parent,false,sizeof(parent));
for(int i=0;i<26;i++)
parent[i][i]=true;
string s1,s2;
cin>>s1;
cin>>s2;
int m;
cin>>m;
while(m–)
{
string a;
cin>>a;
parent[a[0]-‘a’][a[3]-‘a’]=true;
}
int flag=1;
if(s1.size()!=s2.size())
{
cout<<“NO”<<endl;
continue;

}
for(int i=0;i<s1.size();i++)
{
if((!parent[s1[i]-‘a’][s2[i]-‘a’]))
{
flag=0;
break;
}
}
if(flag)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
}

whats wrong in this code i am getting WA for this

4

Hey in your code if the are two loop eg (a->b->c->d) and (w->x->y->z) .and if we want to transform from a->w -----> your code will give the output : YES,
ANS: NO

5

So what I’m doing is replacing every character in the string S which is equal to the RHS of a rule with an arbitrary character ("_"), and replacing every character in the string T equal to the LHS of all the rule, again by an uderscore. Getting correct answer on the given test case, but WA overall.
(Example if S is “ab”, T is “ba”, and the rules are a->b, b->a, then:
Using the first rule, S becomes _b and T becomes _a
Using the second rule, S becomes __ and T also becomes __, making them equal)
Here’s my code if that helps ->

def convert_string(str, a):
str = str.replace(a, "_")
return str

cases = int(input())

for i in range(cases):
s = input()
t = input()
number_of_rules = int(input())
rules = []
for j in range (number_of_rules):
rules.append(input().split("->"))

if (len(s) != len(t)):
    print("NO")
    continue

flag = False
for j in range(len(rules)):
    s = convert_string(s, rules[j][0])
    t = convert_string(t, rules[j][1])

    if s == t:
        print("YES")
        flag = True
        break


if flag == False:
    print("NO")
7

ok thank u i got it