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 B_i (for i = 1 \dots M), and for each one, compare it against each of Ethan's mask names A_j (for j = 1 \dots N), incrementing our running answer if we find a match (such that B_i = A_j). Over the course of this algorithm, we may compare each of the strings A_{1 \dots N} against each of the strings B_{1 \dots M}, resulting in a time complexity of \mathcal O(NM).

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


Comments

There are no comments at the moment.