A: Triple Texting

https://open.kattis.com/problems/tripletexting

Since Grandma repeats the word that she wants to send three times, each letter of the word is sent three times, and so if there is at most one mistaken letter, at least two of the three copies of the letter will be correct. Therefore we can construct the original word from the majority value of the letter at each position.

More formally, let t=t1t2tnt = t_1t_2\dots t_n be the original string, and let s=s1s2s3ns=s_1s_2\dots s_{3n} be the string Grandma sends (the input to the program). Then for 1in1\leq i \leq n, ti=majority(si,si+n,si+2n)t_i = \textrm{majority}(s_i, s_{i+n}, s_{i+2n}). An easy way to implement the majority function is

def majority(a,b,c):
  if a == b:
    return a
  else:
    return c

Last updated