ACM ICPC World Finals 2017
Shortest judge solution: 473 bytes. Shortest team solution (during contest): 585 bytes.
Python solutions by the judges: both Pypy and CPython
This problem has a beautiful solution that is not impossible to get an intuition about, but hard to actually prove correct.
A naive way of computing the probability that a string X of length ` appears in a uniformly random string of length n is to use the principle of inclusion-exclusion:
p(X) = ∑I ⊆[n−`+1] (−1)|I|+1 Pr[there is an occurence of X at all positions in I]
For I = {i} consisting of a single element, the probability in the sum is simple 3−` – the probability that characters i, i + 1, . . . , i + ` − 1 match X. Thus the first-order contribution from index sets I of size 1 to p(X) is simply (n − ` + 1)/3`, regardless of what X looks like.
For the second-order terms I = {i, j}, things are a bit more interesting. If j ≥ i + ` then the probability is simply 3−2` since the two matches of X involve disjoint positions. But for j < i + ` however, the probability is 0 unless j − i is an overlap of X, where we say that t is an overlap of X if the prefix of the first ` − t characters of X equals the suffix of the last ` − t characters of X. If t is an overlap of X, then the set I = {i, i + t} contributes −1/32`−t to the expression for p(X) above.
This hints at the following intuition: strings X with more overlaps should have smaller values of p(X). Among different overlap values t, higher values of t seems to result in smaller probabilities, because the subtracted terms 1/32`−t are larger. So a somewhat natural hypothesis is that if we write the overlaps of X in decreasing order, then strings with lexicographically smaller overlap sequences have higher likelihood.
However, this is just an intuition, and it is not at all clear what happens with higher-order terms – the degree-3 terms (having |I| = 3) give positive contributions to p(X) and more overlaps will by a similar reasoning cause these to be larger. It turns out that the hypothesis above is correct, and that lexicographically smaller overlap sequences leads to larger probabilities. We only have a very long and non-intuitive proof of this, which we don’t include here. But since several people have expressed an interest in it, it has been made available as a separate document here: http://www.csc.kth.se/~austrin/icpc/tarotshamproof.pdf.
As an example, consider the two strings X = RPSRPSRPS and Y = RPRRPRRPR. The overlaps of X are Ov(X) = (6, 3, 0). The overlap sequence of Y is Ov(Y) = (6, 3, 1, 0). This means that in general, X has a higher likelihood of appearing than Y (since (6, 3, 0) is lexicographically smaller than (6, 3, 1, 0)).
However, there was an additional mistake that could be made. If n ≤ 2` − 2, only overlaps t ≥ 2 can come into play. This means that for such small values of n, the strings X and Y are actually equi-probable. In general, we need to ignore any overlap values that are smaller than 2` − n when constructing the overlap sequence.
Overlap sequences can be constructed in O(`) time using KMP or hashing, leading to an O(`s log s) time algorithm.