Test Set 1

Trong Test Set 1, các giới hạn đủ nhỏ để ta có thể muốn thử thật nhiều đầu ra khả dĩ rồi giữ lại đầu ra tốt nhất. Tuy nhiên, vì không có giới hạn tiên nghiệm nào cho độ dài đầu ra và ta có thể dùng bất kỳ chữ cái tiếng Anh nào trong đầu ra, trước hết ta cần suy nghĩ thêm một chút. Ngoài ra, ta thực sự phải cài đặt phép tính khoảng cách chỉnh sửa; ta có thể tìm hiểu về nó qua nhiều tài liệu trực tuyến, bao gồm liên kết Wikipedia này.

Khoảng cách giữa hai chuỗi có độ dài không quá 6 nhiều nhất là 6, vì ta có thể thay từng ký tự trong chuỗi dài hơn (hoặc trong một chuỗi bất kỳ nếu chúng có cùng độ dài) để khớp với chuỗi còn lại, rồi xóa mọi ký tự thừa. Hơn nữa, khoảng cách giữa hai chuỗi không bao giờ nhỏ hơn hiệu tuyệt đối giữa độ dài của chúng, bởi ta cần thêm ít nhất từng ấy ký tự vào chuỗi ngắn hơn (nếu thực sự có một chuỗi ngắn hơn) chỉ để làm nó dài bằng chuỗi còn lại. Suy ra đầu ra không bao giờ cần dài quá 12 ký tự.

Ngoài ra, nếu đầu ra \(N\) chứa một chữ cái không xuất hiện trong cả hai chuỗi đầu vào, việc thay chữ cái đó trong \(N\) bằng một chữ cái có trong một trong hai đầu vào không thể làm tăng bất kỳ khoảng cách nào; điều này có thể được chứng minh bằng quy nạp khi xét định nghĩa đệ quy của khoảng cách chỉnh sửa. Vì vậy, ta có thể giới hạn phạm vi tìm kiếm ở các chuỗi có độ dài không quá 12 trên bảng chữ cái {X, Y, Z}. Có ít hơn một triệu ứng viên, và việc tính khoảng cách chỉnh sửa cho các chuỗi ngắn như vậy rất hiệu quả, nên cách này đủ nhanh để giải Test Set 1.

Có thể chứng minh các cận chặt hơn cho đầu ra, qua đó giảm mạnh số lượng ứng viên và làm lời giải nhanh hơn nữa. Chi tiết xin dành cho bạn đọc, nhưng hãy cân nhắc xem ta có thực sự cần một đáp án dài hơn 6 chữ cái hay không. Chẳng hạn, nếu có ABCDFG và ACDEFG, thay vì thỏa hiệp bằng chuỗi bảy chữ cái ABCDEFG qua việc thêm E vào tên thứ nhất và B vào tên thứ hai, ta cũng có thể xóa B khỏi tên thứ nhất và E khỏi tên thứ hai một cách tương đương, rồi thỏa hiệp bằng chuỗi ngắn hơn ACDFG.

Test Set 2

Đối với Test Set 2, ta cần thêm một số nhận xét. Nhận xét quan trọng nhất là khoảng cách chỉnh sửa thực sự là một khoảng cách, và có các tính chất thông thường của khoảng cách như tính phản xạ và thỏa mãn bất đẳng thức tam giác. Gọi \(e(s,t)\) là khoảng cách chỉnh sửa giữa hai chuỗi \(s\) và \(t\). Với một đầu ra \(N\), ta muốn \(e(\mathbf{C},N)+e(\mathbf{J},N)=e(\mathbf{C},N)+e(N,\mathbf{J})\) là nhỏ nhất. Theo bất đẳng thức tam giác, \(e(\mathbf{C},\mathbf{J})\) là một cận dưới của đại lượng này, và cận dưới đó đạt được. Chẳng hạn, ta có thể đặt \(N\) bằng C, vì \(e(\mathbf{C},\mathbf{C})=0\).

Theo lập luận trên, ta cần tìm một \(N\) sao cho \(e(\mathbf{C},N)+e(N,\mathbf{J})=e(\mathbf{C},\mathbf{J})\) và \(|e(\mathbf{C},N)-e(N,\mathbf{J})|\) nhỏ nhất có thể. May thay, định nghĩa của khoảng cách chỉnh sửa gợi ý một cách để làm điều đó. Nếu khoảng cách chỉnh sửa giữa C và J là \(d\), thì tồn tại một đường đi gồm \(d\) phép toán hợp lệ áp dụng lên C để biến nó thành J. Nói một cách hình thức, tồn tại \(d-1\) chuỗi trung gian \(S_1,S_2,\ldots,S_{d-1}\) sao cho \(e(\mathbf{C},S_i)=i\) và \(e(S_i,\mathbf{J})=d-i\). Vì vậy, chỉ cần chọn \(S_{d/2}\). Nếu \(d\) lẻ, làm tròn lên hay làm tròn xuống đều được, vì với cả hai lựa chọn, \(|e(\mathbf{C},N)-e(N,\mathbf{J})|=1\).

Để tìm \(S_1,S_2,\ldots,S_{d-1}\), ta có thể dùng một kỹ thuật phổ biến để khôi phục đường đi đạt kết quả tối ưu đã tìm được bằng quy hoạch động (DP).

Ví dụ, gọi \(\mathbf{C}_a\) là tiền tố độ dài \(a\) của C, và \(\mathbf{J}_b\) là tiền tố độ dài \(b\) của J. Thuật toán thông thường để tính khoảng cách chỉnh sửa dựa trên định nghĩa đệ quy của hàm \(f(a,b)\) trả về \(e(\mathbf{C}_a,\mathbf{J}_b)\) (xem liên kết ở phần trước để biết chi tiết). Tương tự, ta có thể định nghĩa \(g(a,b,k)\) là một hàm vừa trả về \(e(\mathbf{C}_a,\mathbf{J}_b)\), vừa trả về một chuỗi \(S\) sao cho \(e(\mathbf{C}_a,S)=k\) và \(e(\mathbf{J}_b,S)=e(\mathbf{C}_a,\mathbf{J}_b)-k\). Hàm mới \(g\) có thể được định nghĩa bằng một phép đệ quy tương tự \(f\), rồi được ghi nhớ kết quả để tăng hiệu quả. Chi tiết xin dành làm bài tập cho bạn đọc.

Dữ liệu kiểm thử

Chúng tôi khuyên bạn nên luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 3 — Naming Compromise.