LCC/Moose '19 Contest 3 J4 - Hash

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem types

Any string can be "hashed" into some sequence of characters or integers. However, before we start hashing, let us define a simple procedure that can be operated on a string, called folding the string:

  1. First, add a y to the end of the string if the string has an odd length.
  2. Take the first and last character of string and convert each of them to a number between 1 and 26. If the character is a, it becomes the integer 1, b becomes 2, etc.
  3. Then, multiply these two integers together. If their value is greater than 26, continually subtract 26 until the value is between 1 and 26 (inclusive). Convert this new integer back into a letter between a and z (1=a, 2=b, etc.).
  4. This letter becomes the first character of the new string.
  5. Continue performing steps 3 and 4 until the new string is fully created, using the second and second last character, third and third last, etc. The new string should be exactly half the length of the old string. (including the changes performed in step 1).
  6. The string has been folded.

As an example, we will walk through the process of folding bbc:

  1. The string has an odd length, so we add a y, giving us bbcy.
  2. The first character is b, which becomes 2. The last character is y, which becomes 25.
  3. When we multiply the two integers together, we get 50. Since this number is larger than 26, we continually subtract 26. This gives us 24, which becomes the letter x.
  4. The first letter of the new string is now x.
  5. Performing steps 3 and 4 on the second and second last character gives us the character f. The string at this point is xf.
  6. The string has been fully folded, so the final string after folding bbc is xf.

One possible (though not very practical) way of "hashing" a string into one character consists of a series of steps:

  1. If the length of the string is exactly 1, the string has been successfully hashed, and we can exit.
  2. Otherwise, fold the string, and goto step 1.

This one character string is the hash of the original string.

You are given N strings, and you want to compute the hash of each one. Notice that the final hash of the string can only be a single character between a and z, which is subpar. Thus, you are curious as to how many pairs of strings have the same hash. Can you print this information out?

Input Specification

The first line will contain the integer N (1 \le N \le 10^5), the number of strings.

The next N lines will each contain a string for which you are to hash. Each string will only consist of lowercase latin characters. It is guaranteed the sum of the string lengths of all N strings does not exceed 10^6.

Output Specification

On the first line, output the number of pairs of the strings that have the same hash.

Subtasks

Subtask 1 [10%]

N \le 10 and each string will have a length of at most 100.

Subtask 2 [40%]

N \le 5000

Subtask 3 [50%]

No further constraints.

Sample Input

4
abcd
no
hello
ninjaclasher

Sample Output

1

Explanation

By performing the "hashing":

  • abcd becomes x
  • no becomes b
  • hello becomes b
  • ninjaclasher becomes n

Only no and hello have the same hash, so there is only one pair. Thus, the answer outputted is 1.


Comments

There are no comments at the moment.