Editorial for LCC/Moose '19 Contest 1 S4 - Morphgrams


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.

Author: Riolku

For this problem you want to reduce each word to a "pattern" such that morphgrams have the same pattern.

To do this, make the first unique letter in the word be mapped to the next letter in the alphabet; so FOOD becomes ABBC. Now you must check if patterns match. The naive way to do this is to check every pair of words.

To optimize this, use a map. For each pattern, count the number of occurrences. Let x be the number of occurrences of a given pattern. Then there are:

\displaystyle  {x \choose 2} =  \frac{x \times (x - 1)}{2}

pairs that match for this given pattern. Finally, add up all your totals for the final answer.


Comments

There are no comments at the moment.