COCI '18 Contest 5 #4 Parametriziran

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.4s
Memory limit: 64M

Problem type

A string of characters consisting of lowercase letters of the English alphabet and question marks is called a parameterized word (e.g., a??cd, bcd, ??). Two parameterized words are considered similar if the question mark symbols in both words can be replaced by arbitrary lowercase letters of the English alphabet so that the resulting strings are the same. For example, parameterized words a??? and ?b?a are similar because by replacing the question marks in both words, it is possible to obtain the word abba.

Mirko has recently bought a collection of parameterized words. Among the N words found in the collection, Mirko is interested in how many pairs of similar parameterized words exist. All the words in the collection have the same number of characters, M, and a word may occur multiple times in the collection.


The first line contains the integer numbers N (1 \le N \le 50\,000) and M (1 \le M \le 6). Each of the following N lines contains one parameterized word from the collection with exactly M characters.


Print the total number of similar pairs of parameterized words.


In the test samples totally worth 30% of the points it will be valid M \le 2. In the test samples totally worth additional 30% points it will be valid M \le 4.

Sample Input 1

3 3

Sample Output 1


Explanation for Sample Output 1

Pairs of similar words are: (??b, c??) and (c??, c?c).

Sample Input 2

4 6

Sample Output 2


Sample Input 3

5 2

Sample Output 3



There are no comments at the moment.