Sunday, September 6, 2015

Codeforces: Xenia and Hamming

Here is a coding puzzle I wanted to formalize due to clarity for myself. If you're into number theory this is your thing.

Problem statement:

Solution: First observation which is easy to make is that it is easier to calculate where the characters match instead of mismatch and that we do not need to compute n*x and m*y. This is true:

\( (n \cdot x)[dx + i \cdot |x|] = x[(dx + i \cdot |x|) \mod |x|] \)

Therefore, we want to count how many (dx, i) exist so that x[(dx + i*|x|) mod |x|] = y[(dx + i*|x|) mod |y|] holds. Since i*|x| mod |x| == 0, it is actually:

\( x[dx] = y[(dx + i \cdot |x|]) \mod |y| \)

Lets fix dx and see how i*|x| behaves within modulo |y|. This part requires some simple algebraic knowledge. i*|x| is trivially a repeating sequence within modulo |y|. But how does that repetition look like?

If i*|x| = t (mod |y|), then i*|x| - j*|y| = t, for some j. Using bezouts identity we know that t = gcd(|x|, |y|) * k, for some k.  This means that all sequences make jumps of length gcd(|x|, |y|). With this information and the frequency of all characters within the second string for each repeating sequence, an efficient algorithm can be developed.

No comments:

Post a Comment