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.