← All solutions

Shortest judge solution: 405 bytes. Shortest team solution (during contest): 498 bytes.

Python solutions by the judges: both Pypy and CPython

This was one of the two easiest problems in the set. The set of translations forms a directed graph on the 26 letters of the alphabet. Given two query words s₁ s₂ s₃ . . . s_L and t₁ t₂ t₃ . . . t_L of equal length L (if the lengths are different, the answer is clearly no and we just answer that), we need to check whether for each 1 ≤ i ≤ L, there is a path from s_i to t_i in the graph of letter translations.

One natural way of doing this is to precompute the transitive closure of the graph using the Floyd-Warshall algorithm, which allows you to check each pair (s_i, t_i) in constant time. But the bounds are quite small, so you can use pretty much any polynomial time algorithm for this (e.g. doing a DFS for every pair (s_i, t_i)).