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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 be the number of occurrences of a given pattern. Then there are:
pairs that match for this given pattern. Finally, add up all your totals for the final answer.
Comments