Statement

Ancient viking people carved stories on stone using their own symbols. Björn found N versions of the same story and he already converted them to texts containing only the lowercase letters a-z. The texts are indexed from 0 to N-1, let's denote them with S_0, S_1, … S_N-1. All the texts have the same length K, but they might differ on some positions. Now Björn wants to know which is the original version of the story, because he thinks that the others are just mutated copies of it. He suspects that the original text is the one that has the minimal average distance from all the others. We define the distance between two texts as the number of positions where they differ. More formally, the distance between two texts S_i and S_j denoted by dist(S_i, S_j) is the number of different k indices, for which 0 ≤ k ≤ K-1 and S_i[k] ≠ S_j[k]. We are looking for the text S_orig for which the value avgdist(S_i) = 1/(N-1) \sum_j=0^N-1dist(S_i, S_j) is minimal. (Note that dist(S_i, S_i) = 0)...