Editorial for COCI '20 Contest 6 #3 Anagramistica
Submitting an official solution before solving the problem yourself is a bannable offence.
The first subtask can be solved by iterating over all possible subsets and counting the number of similar pairs in each one.
Since each element is either in the chosen subset or not, that leads us to a dynamic programming solution, where is the number of ways to choose among the first
words a subset with exactly
similar pairs. The transition would be:
where is the number of new similar pairs that appear when we add the
word to the subset. Unfortunately, since we don't know which words are in the subset, we can't know
.
But, we can use a similar approach if we notice that if we sort the letters in each word, then the words are similar if and only if they are equal.
After sorting, we get a multiset of words, with distinct elements, and the
element appears
times. Let
be the number of ways to choose among the first
different words a subset with exactly
equal words. The transition is:
The initial values are , for
, or
otherwise.
Since the numbers in the binomial coefficient are at most , we can precompute them using Pascal's triangle. The complexity for each
is
, since the sum of all
is equal to
, so the total complexity of the solution is
.
Comments