Editorial for WC '18 Contest 2 J3 - Seeing Double


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 Bi (for i=1M), and for each one, compare it against each of Ethan's mask names Aj (for j=1N), incrementing our running answer if we find a match (such that Bi=Aj). Over the course of this algorithm, we may compare each of the strings A1N against each of the strings B1M, resulting in a time complexity of O(NM).

Another possible approach is to start by inserting Ethan's mask names A1N 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 Bi (for i=1M), querying the data structure for the existence of Bj rather than iterating over all of the strings A1N each time. The time complexity of this algorithm is either O((N+M)logN) or O(N+M), depending on the data structure used.


Comments

There are no comments at the moment.