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