Test Set 1

Vì \(L\le2\), có thể vét cạn. Thu thập các chữ xuất hiện ở ký tự thứ nhất của các từ đầu vào vào tập \(C_1\), và các chữ xuất hiện ở ký tự thứ hai vào tập \(C_2\). Mọi từ mới ứng viên có dạng \(c_1c_2\), với \(c_1\in C_1\) và \(c_2\in C_2\). Với từng ứng viên, kiểm tra nó có nằm trong input hay không. Có thể in bất kỳ ứng viên nào chưa xuất hiện; nếu mọi ứng viên đều đã có thì trường hợp đó bất khả thi.

Có không quá \(26^2\) ứng viên, nên thuật toán chạy rất nhanh. Trường hợp \(L=1\) được xử lý tương tự chỉ với \(C_1\).

Test Set 2

Trong các vòng đầu của Code Jam, vét cạn thường chỉ đủ cho Test Set đầu tiên, nhưng bài này là ngoại lệ: cách trên vẫn hoạt động tốt.

Tạo các tập \(C_1,C_2,\ldots,C_L\), trong đó \(C_i\) chứa đúng các chữ đã xuất hiện ở vị trí \(i\). Mọi từ Desta có thể ghép là một phần tử của tích Descartes

Sinh lần lượt các tổ hợp và kiểm tra bằng một tập băm chứa \(N\) từ đầu vào. Gặp tổ hợp chưa có thì trả về nó.

Nếu có đúng \(N\) tổ hợp khả dĩ, do \(N\) từ đầu vào phân biệt và mỗi từ đều là một tổ hợp hợp lệ, toàn bộ các tổ hợp đã có trong input và phải in -. Nếu số tổ hợp lớn hơn \(N\), trong \(N+1\) ứng viên đầu tiên chắc chắn có ít nhất một từ không thuộc danh sách chỉ gồm \(N\) từ. Vì thế không bao giờ cần sinh quá \(N+1\le2001\) ứng viên, dù toàn bộ tích Descartes có thể lớn hơn nhiều.

Mỗi ứng viên dài \(L\), nên sau khi đọc input, thời gian kỳ vọng là \(O(NL)\) khi dùng tập băm và bộ nhớ là \(O(NL)\).

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2018, Round 1C, bài A Whole New Word; kho Google Coding Competitions (Apache-2.0).