Test Set nhỏ

Small có nhiều nhất 15 chữ. Ở bước \(i\), chữ mới được thêm vào đầu hoặc cuối từ hiện tại, nên số từ có thể có nhiều nhất gấp đôi bước \(i-1\). Vì vậy tổng số last word không quá \(2^{15}\). Sinh tất cả rồi lấy từ đứng cuối theo thứ tự bảng chữ cái:

def alphabetically_last_word(S):
  possible_words = set([''])
  for c in S:
    possible_words = set([c + r for r in possible_words] + [r + c for r in possible_words])
  return max(possible_words)

Test Set lớn

Cách trên quá chậm cho Large. Ở bước \(i\), thêm \(S_i\) vào đầu hoặc cuối \(X_{i-1}\), thu được \(X_i=X_{i-1}S_i\) hoặc \(X_i=S_iX_{i-1}\). Để kết quả cuối đứng muộn nhất theo bảng chữ cái, ở mỗi bước cũng luôn nên giữ \(X_i\) muộn nhất có thể. Chính xác hơn, sau \(i\) chữ, \(X_i\) phải là chuỗi muộn nhất có thể tạo từ \(i\) chữ đầu theo luật.

Giả sử ở bước \(i\), gọi \(Y_i\) là chuỗi sớm hơn và \(Z_i\) là chuỗi muộn hơn trong hai chuỗi \(S_iX_{i-1}\) và \(X_{i-1}S_i\). Nếu chọn \(Y_i\) là tối ưu, last word cuối có dạng \(AY_iB\) với một số \(A,B\) do các bước sau chèn vào. Ta có thể chọn \(Z_i\) rồi chèn các chữ sau theo hệt cách cũ để được \(AZ_iB\). Với mọi \(A,B\), \(AZ_iB\) không thể đứng sớm hơn \(AY_iB\) vì \(Z_i\) không sớm hơn \(Y_i\). Do đó mọi từ dùng \(Y_i\) đều có thể thay bằng một từ không kém hơn dùng \(Z_i\), và chọn \(Z_i\) luôn đúng.

Vì thế \(X_i\) chỉ cần là chuỗi lớn hơn theo thứ tự từ điển giữa \(X_{i-1}S_i\) và \(S_iX_{i-1}\). Mỗi bước chỉ so sánh việc đặt chữ mới ở đầu hay cuối:

def alphabetically_last_word(S):
  result = ''
  for c in S:
    result = max(c + result, result + c)
  return result

Hai lời giải rất giống nhau. Large nhận ra ngay từ nào ở mỗi bước chắc chắn thuộc một đáp án tối ưu. Thay vì giữ lượng thông tin tăng theo hàm mũ, nó chỉ giữ một chuỗi, nên nhanh và ít bộ nhớ hơn. Cách Small dùng thời gian và bộ nhớ hàm mũ; cách Large chỉ dùng đa thức.

Một cách nhìn khác là phép max giao hoán với bước xây tập trong mã Small, nên có thể giữ giá trị lớn nhất sau mỗi bước thay vì đợi đến cuối. Đây là con đường biến lời giải Small thành lời giải Large, tương ứng với mục “A possible stepping stone...” trong bài luận mà phân tích chính thức dẫn tới.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - Round 1A - The Last Word, kho Google Coding Competitions (Apache-2.0).