Test Set 1

Trong bộ nhỏ, googlement có độ dài tối đa \(5\). Ta sẽ trình bày cho độ dài đó; các độ dài ngắn hơn được xử lý tương tự.

Mọi chuỗi độ dài \(5\) chỉ dùng chữ số trong \([0,5]\) và khác 00000 đều là googlement; có \(6^5-1=7775\) chuỗi như vậy. Một lời giải khả thi là duyệt tất cả các googlement rồi mô phỏng quá trình phân rã của từng chuỗi cho đến khi đạt trạng thái lặp duy nhất 10000. Trong quá trình ấy, với mỗi googlement, duy trì số chuỗi phân rã mà nó xuất hiện. Khi hoàn tất, ta biết số tổ tiên khả dĩ của mọi googlement, tức có sẵn đáp án cho mọi bộ test nhỏ.

Phần sau sẽ chứng minh 10000 là googlement độ dài \(5\) duy nhất là hậu duệ của chính nó, đồng thời xem xét độ dài tối đa của chuỗi phân rã. Ngay cả nếu mỗi chuỗi dài tới số lượng googlement, chỉ với \(7775\) googlement, phương pháp này vẫn đủ nhanh cho bộ nhỏ.

Đó là cách “từ trên xuống”; cách “từ dưới lên” cho bài toán cây này cũng hoạt động. Với một googlement, ta suy ra các chữ số bắt buộc có trong googlement đã tạo ra nó, tức “tổ tiên trực tiếp”. Chẳng hạn, với 12000, mọi tổ tiên trực tiếp phải có một chữ số 1, hai chữ số 2 và hai chữ số 0 để đủ tổng cộng năm chữ số. Ta sinh mọi googlement như vậy, ví dụ 12020, rồi đệ quy đếm các tổ tiên trực tiếp của chúng, ví dụ 42412, theo đúng cách đó. Quá trình không kéo dài vô hạn vì cây chỉ có nhiều nhất \(7775\) googlement. Trường hợp xấu nhất là 10000, hậu duệ của mọi googlement.

Sau khi có ý tưởng từ dưới lên, phần còn lại là chi tiết cài đặt. Khó nhất là sinh các tổ tiên trực tiếp có số lần xuất hiện xác định cho từng chữ số. Có thể dùng thư viện hoán vị, hoặc tự sinh hoán vị mà không xét lặp các bản sao giống nhau. Có thể tiết kiệm thời gian giữa các bộ test bằng ghi nhớ kết quả cho từng nút của cây, vì hành vi phân rã của một googlement luôn giống hệt nhau và cùng một googlement có thể — rất có thể sẽ — xuất hiện nhiều lần trong các bộ test khác nhau.

Test Set 2

Trong cách từ dưới lên của bộ nhỏ, ta tốn nhiều thời gian sinh tổ tiên trực tiếp để kiểm tra. Việc đó cần thiết với tổ tiên như 12020, vì bản thân nó còn có tổ tiên. Nhưng dựng và liệt kê tổ tiên như 42412 là lãng phí vì chúng không có tổ tiên. Tổng quát hơn, một googlement độ dài \(L\) có tổng chữ số lớn hơn \(L\) không thể có tổ tiên: không thể nhét hơn \(L\) chữ số vào chuỗi độ dài \(L\).

Hóa ra tránh liệt kê những tổ tiên không có tổ tiên của riêng mình giúp cách từ dưới lên đủ nhanh cho bộ lớn. Ta dùng thêm tổ hợp và định lý đa thức.

Xét lại các tổ tiên trực tiếp của 12020. Mỗi tổ tiên phải có một 1, hai 2 và hai 4. Có bao nhiêu chuỗi như vậy? Từ năm vị trí trống, có \(\binom52=10\) cách đặt hai chữ số 2; sau đó có \(\binom32=3\) cách đặt hai chữ số 4 vào hai trong ba vị trí còn lại; cuối cùng có \(\binom11=1\) cách đặt chữ số 1. Tích các số này là \(30\), nên 12020 có \(30\) tổ tiên trực tiếp. Mỗi tổ tiên ấy có tổng chữ số \(13>5\), do đó không có tổ tiên riêng. Ta không cần biết cụ thể chúng là gì, chỉ cần cộng \(30\) vào kết quả.

Đến đây, có thể kiểm tra cải tiến trên trường hợp xấu nhất 100000000 trước khi tải bộ lớn, hoặc tự thuyết phục bằng tổ hợp. Các googlement độ dài \(9\) có tổ tiên chính là những chuỗi có tổng chữ số không quá \(9\). Dùng lập luận chia bóng vào hộp, số lượng là

Đây chỉ là phần cực nhỏ trong \(999999999\) googlement độ dài \(9\): ta đã tránh liệt kê khoảng \(999900000\) chuỗi còn lại. Miễn thao tác sinh tổ tiên không tạo quá nhiều chi phí phụ, cách này dễ dàng xử lý \(100\) test lớn đúng hạn, ngay cả khi hầu hết hoặc tất cả chúng duyệt gần như toàn bộ cây.

Phụ lục: một số chứng minh

Ta chứng minh với mỗi độ dài chỉ có một trạng thái tự lặp và đồ thị không có chu trình nào khác. Trước hết là các nhận xét:

• Khi một googlement phân rã, số chữ số khác 0 của googlement cũ bằng tổng chữ số của googlement mới.
• Vì thế, googlement có chữ số ngoài 0 và 1 sẽ phân rã thành googlement có tổng chữ số nhỏ hơn.
• Googlement chỉ gồm 0 và 1 sẽ phân rã thành googlement có cùng tổng chữ số. Nếu nó là một 1 rồi đến không hoặc nhiều 0, nó phân rã thành chính mình. Nếu chỉ có một 1 ở vị trí khác, nó phân rã thành 1 rồi đến các 0. Nếu không thuộc hai trường hợp đó, nó có ít nhất hai 1, nên phân rã thành googlement cùng tổng chữ số nhưng có ít nhất một chữ số ngoài 0 và 1.

Từ đó suy ra:

• Googlement độ dài \(L\) duy nhất có thể phân rã thành chính nó là 1 theo sau bởi \(L-1\) chữ số 0. Với mọi googlement khác, bước phân rã hoặc giảm tổng chữ số, hoặc tạo một googlement mới có chữ số ngoài 0 và 1, rồi googlement mới ấy sẽ phân rã thành chuỗi có tổng chữ số nhỏ hơn.
• Một chuỗi phân rã cần nhiều nhất hai bước để tổng chữ số giảm ít nhất một đơn vị. Do đó chiều cao cây phân rã không quá hai lần tổng chữ số tối đa. Cận thực tế còn nhỏ hơn; chẳng hạn 999999999 lập tức phân rã thành 000000009, làm tổng chữ số giảm rất nhiều.

Nội dung trên được chuyển ngữ đầy đủ từ phân tích chính thức của Google Code Jam 2017, Vòng 3, bài Googlements.