Phân tích

Trong hầu hết các bài toán Google Code Jam, mỗi bộ thử nghiệm hoàn toàn tách biệt và những gì bạn học được từ bộ này sẽ không giúp ích cho bộ khác. Tuy nhiên, bài toán này lại khác:

"Googlerese dựa trên phép ánh xạ thay thế tốt nhất có thể, và chúng tôi sẽ không bao giờ thay đổi nó. Nó sẽ luôn giống nhau trong mọi trường hợp kiểm thử."

Chúng tôi thực sự nghiêm túc khi nói điều này! Thực sự chỉ có một phép ánh xạ duy nhất, và thách thức chính ở đây là tìm ra nó là gì. May mắn thay, có rất nhiều thông tin chúng ta có thể học được từ dữ liệu mẫu (input và output). Ví dụ, bằng cách nhìn vào từ đầu tiên trong dòng đầu tiên, chúng ta biết rằng "our" trở thành "ejp" trong Googlerese, vì vậy 'o' -> 'e', 'u' -> 'j', và 'r' -> 'p'. Nếu bạn đi qua toàn bộ văn bản mẫu, bạn sẽ thấy có gần đủ thông tin để tái tạo toàn bộ phép ánh xạ:

'a' -> 'y'
'b' -> 'n'
'c' -> 'f'
'd' -> 'i'
'e' -> 'c'
'f' -> 'w'
'g' -> 'l'
'h' -> 'b'
'i' -> 'k'
'j' -> 'u'
'k' -> 'o'
'l' -> 'm'
'm' -> 'x'
'n' -> 's'
'o' -> 'e'
'p' -> 'v'
'q' -> ???
'r' -> 'p'
's' -> 'd'
't' -> 'r'
'u' -> 'j'
'v' -> 'g'
'w' -> 't'
'x' -> 'h'
'y' -> 'a'
'z' -> ???

Chúng ta chỉ cần tìm cách dịch 'q' và 'z'. Nhưng nếu bạn đọc kỹ đề bài, bạn sẽ nhận thấy có thêm một ví dụ nữa mà chúng tôi đã cung cấp! "a zoo" được dịch thành "y qee". Điều này có nghĩa là 'z' được ánh xạ thành 'q'.

Tiếp theo, chúng ta cần tìm xem 'q' được ánh xạ thành chữ cái nào. Đối với phần này, bạn cần nhớ rằng mỗi chữ cái được ánh xạ tới một chữ cái khác nhau. Và nếu bạn nhìn kỹ, đã có các chữ cái được ánh xạ tới mọi chữ cái khác ngoại trừ 'z'. Điều này chỉ để lại một khả năng duy nhất: 'q' phải được ánh xạ tới 'z'.

Và bây giờ chúng ta đã có bảng ánh xạ dịch thuật đầy đủ, tất cả những gì cần làm là viết một chương trình để áp dụng nó vào các đoạn văn bản.

Cách cài đặt

Dưới đây là một giải pháp bằng Python:

translate_to_english = {
    ' ': ' ', 'a': 'y', 'b': 'h', 'c': 'e', 'd': 's',
    'e': 'o', 'f': 'c', 'g': 'v', 'h': 'x', 'i': 'd',
    'j': 'u', 'k': 'i', 'l': 'g', 'm': 'l', 'n': 'b',
    'o': 'k', 'p': 'r', 'q': 'z', 'r': 't', 's': 'n',
    't': 'w', 'u': 'j', 'v': 'p', 'w': 'f', 'x': 'm',
    'y': 'a', 'z': 'q'}

for tc in xrange(1, int(raw_input()) + 1):
  english = ''.join(
      [translate_to_english[ch] for ch in raw_input()])
  print 'Case #%d: %s' % (tc, english)

Độ phức tạp

Độ phức tạp thời gian là \(O(N)\) với mỗi bộ thử nghiệm, trong đó \(N\) là độ dài của chuỗi \(G\), vì chúng ta chỉ cần duyệt qua chuỗi một lần và tra cứu bảng ánh xạ. Độ phức tạp không gian là \(O(1)\) để lưu trữ bảng ánh xạ gồm 26 ký tự.

Dựa trên phân tích chính thức của Google Code Jam.