Editorial for WC '18 Contest 2 J3 - Seeing Double
Submitting an official solution before solving the problem yourself is a bannable offence.
One approach we can take is to iterate over Benji's mask names (for
), and for each one, compare it against each of Ethan's mask names
(for
), incrementing our running answer if we find a match (such that
). Over the course of this algorithm, we may compare each of the strings
against each of the strings
, resulting in a time complexity of
.
Another possible approach is to start by inserting Ethan's mask names into a data structure such as a set (a balanced binary search tree) or hash table, and then iterate over each of Benji's mask names
(for
), querying the data structure for the existence of
rather than iterating over all of the strings
each time. The time complexity of this algorithm is either
or
, depending on the data structure used.
Comments