Test Set 1

Trong test set thứ nhất, chỉ có tối đa \(N=6\) từ và mỗi từ dài tối đa \(50\) ký tự. Ta có thể dùng vét cạn để thử mọi cách chia các từ thành từng cặp (cho phép một số từ không thuộc cặp nào — trên thực tế, ta sẽ loại bỏ các từ này), thử mọi cách chọn hậu tố trọng âm cho từng cặp và kiểm tra rằng không có hai cặp nào dùng cùng một hậu tố trọng âm. Cuối cùng, chọn kích thước lớn nhất trong tất cả các cách chia hợp lệ.

Test Set 2

Hãy xét ảnh hưởng của độ dài hậu tố trọng âm tới khả năng nhiều từ cùng chứa hậu tố đó. Nếu có các từ CODEJAM, JAM, HUM và HAM, hậu tố trọng âm JAM chỉ có thể thuộc hai từ, trong khi hậu tố trọng âm ngắn hơn là M phù hợp với cả bốn từ. Từ đó có nhận xét sau: với hai từ muốn ghép thành một cặp, việc chọn hậu tố chung dài nhất có thể của chúng làm hậu tố trọng âm không bao giờ khiến kết quả kém tối ưu — cách này vẫn bảo đảm chúng gieo vần, đồng thời dành các hậu tố trọng âm ngắn hơn cho những cặp khác. Lưu ý rằng mọi cặp khác có thể dùng hậu tố dài hơn thì cũng có thể dùng bất kỳ hậu tố ngắn hơn nào. Chẳng hạn, nếu muốn CODEJAM và JAM gieo vần, ta nên chọn JAM làm hậu tố trọng âm của chúng và để hậu tố M có thể được dùng cho HUM và HAM.

Bài toán này hoàn toàn xoay quanh các hậu tố chung của những từ. Để thao tác thuận tiện hơn với hậu tố, trước tiên hãy đảo ngược từng từ (khi đó, hậu tố của từ ban đầu trở thành tiền tố của từ đã đảo), rồi xây dựng một trie, còn thường được gọi là cây tiền tố, từ các từ đã đảo. Trie chứa các từ CODEJAM, JAM, HUM và HAM sẽ biểu diễn các từ theo thứ tự ký tự đảo ngược, bắt đầu bằng nhánh M; từ đó các nhánh tiếp tục tương ứng với các tiền tố của MAJEDOC, MAJ, MUH và MAH.

Ta cũng đánh dấu những nút trie tại đó có một từ đầu vào kết thúc. Vì tất cả các từ đều được bảo đảm là khác nhau, chỉ cần dùng một cờ boolean đơn giản. Trong hình minh họa chính thức, các nút trie nơi một từ kết thúc được tô màu đỏ.

Bây giờ có thể giải bài toán như sau: với một nút trie \(v\), gọi \(f(v)\) là số lượng nhỏ nhất có thể của các từ chưa được ghép cặp mà hậu tố trọng âm sau khi đảo ngược kết thúc tại nút \(v\) hoặc trong cây con của nút đó. Khi ấy, đáp án của bài toán là \(N-f(\text{root})\), vì \(f(\text{root})\) bao quát tất cả các hậu tố trọng âm có thể sử dụng.

Ta tính các giá trị \(f(v)\) như thế nào? Nếu \(v\) không có nút con, đặt \(f(v)=1\), vì trong trie này mọi nút lá đều là điểm kết thúc của một từ. Nếu nút \(v\) có các nút con, ta tính \(f(v)\) bằng thuật toán sau và gán kết quả cho \(r\):

r = tổng f(c) với mọi c là nút con của v
nếu nút v được đánh dấu (có một từ kết thúc tại v): r = r + 1
nếu v không phải là nút gốc và f(v) ≥ 2: r = r - 2

Trước hết, ta đệ quy đếm số lượng từ chưa được ghép cặp. Cuối cùng, cho hai trong số các từ đó ghép thành một cặp, sử dụng tiền tố kết thúc tại nút \(v\) — tương ứng với một hậu tố của các từ ban đầu — làm hậu tố trọng âm.

Trong trie ví dụ, các giá trị \(f(v)\) được tính từ lá lên gốc. Bốn nút kết thúc từ ban đầu có giá trị \(1\); sau khi ghép tại những nút hậu tố phù hợp, một số nút trung gian có giá trị \(0\), còn các nút khác chuyển tiếp một từ chưa ghép với giá trị \(1\), đúng như hình minh họa chính thức.

Việc chứng minh thuật toán trên tính đúng \(f(v)\) khá trực tiếp. Trước hết, lưu ý rằng chỉ những từ được biểu diễn tại nút \(v\) hoặc bên dưới \(v\) trong trie mới có thể ghép bằng tập hậu tố trọng âm được biểu diễn bởi \(v\) hoặc cây con của nó. Sau đó, ta chứng minh bằng quy nạp: rõ ràng \(f\) đúng với cây chỉ có một nút vì không thể tạo cặp nào. Giả sử theo giả thuyết quy nạp rằng \(f\) đúng trên mọi cây con thực sự nằm dưới \(v\). Cách ghép được suy ra từ phép dựng \(f(v)\) — thêm một cặp bất kỳ từ các từ còn lại vào kết quả đệ quy — là hợp lệ: ta chỉ ghép hai từ bằng hậu tố trọng âm được biểu diễn bởi \(v\), còn phần kết quả kia hợp lệ theo giả thuyết quy nạp. Để chỉ ra cách ghép này cũng có kích thước lớn nhất, theo giả thuyết quy nạp, không có cách nào ghép nhiều hơn sum(f(c) for all c where c is a child node of v) từ bằng các hậu tố trọng âm được biểu diễn trong cây con nhưng không được biểu diễn trực tiếp bởi \(v\). Lý do là các từ nằm trong những cây con khác nhau của \(v\) không thể được ghép bằng một hậu tố trọng âm dài hơn hậu tố do \(v\) biểu diễn, và hậu tố trọng âm do \(v\) biểu diễn chỉ có thể bổ sung nhiều nhất một cặp vào tổng số.

Lưu ý rằng các giá trị \(f(v)\) được tính theo cách đệ quy và mỗi \(f(v)\) chỉ được tính đúng một lần cho mỗi nút \(v\). Vì ngoài thời gian dành cho các lời gọi đệ quy, bản thân thuật toán chỉ tốn thời gian hằng số, ta có thể tính tất cả các giá trị \(f(v)\) trong thời gian \(O(T)\), với \(T\) là tổng số nút trong trie. Có thể chặn trên \(T\) bằng tổng độ dài của tất cả các từ, hoặc bằng \(N \times m\), trong đó \(m\) là độ dài lớn nhất của một từ.

Cuối cùng, cũng có những cách cài đặt kém hiệu quả hơn nhưng đơn giản hơn mà vẫn đáp ứng yêu cầu. Chẳng hạn, sắp xếp các từ đã đảo theo thứ tự bảng chữ cái, chọn hai từ kề nhau bất kỳ có tiền tố chung dài nhất, ghép chúng thành một cặp, xóa chúng khỏi danh sách rồi lặp lại. Thuật toán dễ cài đặt này về cơ bản tạo ra cùng cách ghép như công thức đệ quy ở trên. Nó chuyển một phần độ phức tạp trong cài đặt sang phần chứng minh tính đúng đắn. Nếu bạn chứng minh nhanh hơn viết mã thì nhìn chung cách này có thể giúp giải bài nhanh hơn.

Lưu ý về dữ liệu kiểm thử: 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 2019, Vòng 1A — Alien Rhyme.