Test Set nhỏ

Vì Small có chuỗi dài không quá 20, số điện thoại dài không quá 6 chữ số: các tên ngắn nhất ONE, TWO có ba chữ, và \(7\times3>20\). Nhận xét quan trọng là số đáp án khả dĩ không quá một triệu, thực tế ít hơn nhiều vì chỉ chấp nhận chữ số không giảm.

Có thể xét mọi số điện thoại từ 0 đến 9, từ 00 đến 99 (lưu ý 00 khác 0), rồi tiếp tục đến các chuỗi sáu chữ số 000000 đến 999999; trong khoảng cuối thực ra chỉ cần đến 222222. Chỉ giữ các chuỗi có chữ số không giảm, đổi từng chữ số thành chữ cái rồi sắp toàn bộ chữ cái theo bảng chữ cái. Các chữ của 1 có thể được đưa vào dưới dạng EON, ENO, NEO, v.v., nhưng dạng sắp xếp luôn là ENO; 0 thành EORZ, 01 thành EENOORZ, v.v.

Tạo một từ điển (bảng băm) ánh xạ chuỗi chữ cái đã sắp sang số điện thoại. Mỗi khóa thực ra chỉ ứng với một số — sẽ giải thích sau. Với mỗi test, sắp \(S\) theo bảng chữ cái rồi tra từ điển; bạn của ta có thể hoán vị \(S\) tùy ý mà không đổi số gốc.

Không cần tạo lại từ điển cho từng test; chỉ tạo một lần trước khi xử lý. Thậm chí có thể tạo trước khi tải đầu vào và lưu trong mã nguồn hoặc tệp riêng mà chương trình đọc, miễn mã nguồn không vượt giới hạn chuẩn 100 kB.

Test Set lớn

Từ điển cho mọi số điện thoại 1000 chữ số quá lớn để tạo và lưu trước, càng không thể sinh trong lúc chạy.

Một cách tham lam hấp dẫn là liên tục loại các bộ chữ của tên chữ số, chẳng hạn lấy NINE (một E, một I, hai N) đến khi không thể rồi lấy EIGHT, v.v. Nhưng cách này có thể sai: nếu số thật không có 9, bộ NINE đầu tiên có thể lấy N từ SEVEN, I từ SIX, và NE từ ONE, cuối cùng để lại mớ chữ không thể ghép thành bất kỳ chữ số nào.

Phương pháp ấy sẽ đúng nếu loại chữ số theo đúng thứ tự. FOUR là tên duy nhất trong mười số chứa U, nên thấy ba U thì chắc chắn có ba FOUR. Ta an toàn xóa ba F, ba O, ba U, ba R và ghi nhận ba chữ số 4. Sau khi bỏ hết FOUR, FIVE là tên còn lại duy nhất chứa F, nên số F cho biết số FIVE; tiếp tục tương tự. Nếu làm ngược, lấy FIVE trước theo số F, kết quả có thể sai tùy số lượng FOUR, SIX, SEVEN, v.v.

Một thứ tự an toàn, dựa vào chữ cái duy nhất tại thời điểm loại, là: ZERO, SIX, EIGHT, TWO, FOUR, FIVE, SEVEN, THREE, NINE, ONE. Chẳng hạn mọi chữ của ONE đều xuất hiện trong tên khác, nhưng khi đến bước cuối chỉ còn các ONE.

Sự tồn tại của thứ tự này cũng giải thích vì sao từ điển Small không có hai số điện thoại khác nhau cùng sinh một chuỗi đã sắp. Hai số khác nhau không thể tạo cùng chuỗi vì không có tập con các từ tên chữ số nào là tổ hợp tuyến tính của các từ còn lại. Điều này không đúng với bộ từ tùy ý. Ví dụ, trong một ngôn ngữ mà bốn tên chữ số là AB, AC, BD, CD, từ chuỗi ABCD không thể biết nó được tạo bởi một AB và một CD, hay một AC và một BD.

Nguồn

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