Break the hash
At some programming contests rivals’ solutions can be hacked: you submit a test on which someone else’s solution fails. You are reading a rival’s solution and see that it compares strings with a polynomial hash: the base b is written in the code, and so is the modulus M. Sometimes there is no modulus at all, and the hash simply overflows a 64-bit unsigned number, that is, M = 2⁶⁴.
The hash of a string s of letters s₀s₁…sL−1 is computed like this:
h = 0
for c in s:
h = (h * b + ord(c)) mod M
where ord is the ASCII code of a letter: 97 for a, 122 for z. Build two different strings with the same hash.
Input
One line: two numbers b and M. The modulus M is either 18446744073709551616 (that is, 2⁶⁴) or a prime not greater than 2³¹ − 1. The base: 1 ≤ b < M.
Output
Two strings of lowercase Latin letters a–z, each from 1 to 2048 long. The strings must differ, and their hashes modulo M must coincide. The lengths may differ. Any such answer will do.
Examples
Example 1
131 18446744073709551616
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababba baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaab
Example 2
31 1000000007
pkoqhrtlal wbmbhveana
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 13 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The two cases are quite different. Start with a prime modulus around a billion: how many random strings do you need to try before two of them share a hash? Recall the birthday problem.
2Hint 2
For 2⁶⁴ brute force is hopeless: it takes about 2³² strings. But 2⁶⁴ is not a prime. If the base is even, what happens to b⁶⁴ modulo 2⁶⁴? And if it is odd, look at the Thue–Morse strings: a and b, then ab and ba, abba and baab, each next one a concatenation of the previous two.
3Hint 3
The hash of a concatenation XY equals h(X) · b|Y| + h(Y). Express the difference of the hashes of Sk and Tk through the difference for k − 1, and count how many factors of two it has.
4The idea
Three cases. A prime modulus M ≤ 2³¹ − 1: the hashes of random strings behave like random numbers, and among k strings a match becomes more likely than not already at k ≈ 1.18 √M, at most sixty thousand strings. 2⁶⁴ and an even base: b⁶⁴ is divisible by 2⁶⁴, and everything to the left of the last 64 letters drops out of the hash. 2⁶⁴ and an odd base: Thue–Morse strings of 1024 letters.
5Walkthrough
A prime modulus. Generate random ten-letter strings, compute their hashes and put them in a dictionary until some hash occurs a second time for a different string. With M = 2³¹ − 1 about sixty thousand strings suffice on average, with 10⁹ + 7 about forty thousand.
2⁶⁴, an even base. The strings “a” and “b”, each followed by 64 letters z. The first letter enters the hash with the factor b⁶⁴, and that is divisible by 2⁶⁴ because b has at least one factor of two.
2⁶⁴, an odd base. S₀ = a, T₀ = b, Sk+1 = SkTk, Tk+1 = TkSk. For the difference Dk = h(Sk) − h(Tk) we get Dk+1 = Dk(b2k − 1), and D₀ = −1. The factor b − 1 is even, b² − 1 is divisible by 8, and each next one by 2 at least once more than the previous. Altogether there are at least 1 + 3 + 4 + … + 11 = 64 twos for k = 10. Strings of 1024 letters, and the answer does not depend on the base.
5+Solution
6Complexity
For a prime modulus, O(√M) strings of ten letters and as much dictionary memory: about sixty thousand in the worst test. For 2⁶⁴, O(1): one answer for all odd bases and one for all even ones.
7Common mistakes
- Brute force for 2⁶⁴ too. The birthday problem needs about 1.18 · 2³² ≈ 5 · 10⁹ strings. Brute force does not finish in the allotted time and prints two strings with different hashes.
- The same string twice. A hash match in the dictionary must be checked for different strings: the random generator may produce the same string again.
- Letters outside a–z. Thue–Morse strings are convenient to build from 0 and 1; replace them with the letters a and b. That only shifts the codes, and the difference of the hashes is the same.
- A hash modulo 2⁶⁴ in Python. Python numbers do not overflow: if you check the answer yourself, take the remainder explicitly,
% 2**64.