Problem B
Perfect String Hash
In computer science, a hash function is a function which maps data of arbitrary size (called keys) into data of fixed size called hashes; typically integers within a certain range, say $\{ 0, 1, 2, \ldots M-1\} $ for some constant $M$. It is highly desireable that different keys yields different hashes, but since there are usually more possible keys than available hashes, collisions are inevitable.
When our set of possible keys is bounded, however, we can create what is known as a perfect hash function. Given a finite set of keys $S$, a perfect hash function maps distinct elements in $S$ to a set of non-negative integers less than $M$, with no collisions. In mathematical terms, it is an injective function $h: S \to \{ 0, 1, 2, \ldots M-1\} $, for some constant $M$.
We are aiming to implement a perfect hash function for a set of strings, such that you can choose the constant $M$ as small as possible. As as starting point, consider the hash function for strings below (which, with the except of the modulo operation, is stolen from the built-in hashcode function for strings in the Java language):
public int hash(String s) {
int hash = 0;
for (int i = 0; i < s.length(); i++) {
hash = (31 * hash + s.charAt(i)) % M;
}
return hash;
}
The above code corresponds to the function
\[ h(s) = \sum _{i=0}^{\ell }s_ i\cdot a^{\ell -i} \mod M \]with $a=31$ and $\ell = \texttt{s.length()-1}$. It is known as the Horner’s method for computing a polynomial.
Your task is to find a value for the constant $a$ (possibly different from 31) and a value for $M$ such that $h$ is a perfect hash function for the set of strings $S$, and $M$ is as small as possible.
Explantion of sample
For example, consider the set $S = \{ \texttt{"Hi"}, \texttt{"ha"}\} $. The smallest $M$ we can hope for is 2, since $|S|=2$. Sadly, the two strings ‘Hi’ and ‘ha’ will yield the same hash for $M=2$ regardless of our value of $a$. For $M=3$, however, we can pick $a=2$, which maps the two strings to different values (even if $a=31$ does not).
Input
The first line of input contains an integer $n$ ($2 \leq n \leq 80$), the size of the set $S$. Then the elements of $S$ follows on the next $n$ lines, each consisting of a unique string. No string has more than 32 characters, and all strings are made entirely of alphabetic ASCII characters (that is, 65 <= s.charAt(i) <= 90 || 97 <= s.charAt(i) <= 122 for every $\texttt{s}\in S$ and $0 \leq i < \texttt{s.length()}$). You may assume that for all input files, $M \le 500$.
Output
Output a single line containing two space-separated non-negative integers $a$ and $M$, such that $M$ is as small as possible and there are no collisions using $a$ as the constant of $h$. If multiple choices of $a$ are possible, output your favourite among those less than $2^{31}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 Hi ha |
2 3 |
