Phân tích

Test Set 1

Trong Test Set 1, miền các giá trị \(M\) có thể có nhỏ đến mức số lượng bản ghi lớn hơn rất nhiều; vì vậy, mỗi tổ hợp \((M_i,N_i)\) có xác suất tương đối lớn, bằng \(1/(99 \times M_i)\), để xuất hiện ở một bản ghi cụ thể, và có xác suất còn lớn hơn để xuất hiện trong ít nhất một bản ghi.

Giả sử với mỗi \(x\) trong đoạn từ \(1\) đến \(9\) đều tồn tại ít nhất một bản ghi có \(M_i=N_i=x\). Từ bản ghi có \(M_i=N_i=1\), ta biết chữ cái duy nhất trong \(R_i\) biểu diễn \(1\). Sau đó, trong tất cả các bản ghi có \(M_i=2\), ta có thể loại những bản ghi mà \(R_i\) biểu diễn \(1\). Những bản ghi còn lại phải là các bản ghi có \(M_i=N_i=2\), và trong đó, chữ cái duy nhất trong \(R_i\) biểu diễn \(2\). Tổng quát hơn, sau khi đã giải mã các chữ cái ứng với từ \(1\) đến \(x\), ta có thể lấy các bản ghi có \(M_i=x+1\), loại những bản ghi mà \(R_i\) chứa chữ cái đã được gán, và các giá trị \(R_i\) của những bản ghi còn lại sẽ chứa chữ cái cần gán cho \(x+1\). Cuối cùng, chữ cái duy nhất chưa được gán phải được gán cho \(0\).

Quy trình này hoạt động miễn là với mỗi \(x\) trong đoạn từ \(1\) đến \(9\) đều tồn tại bản ghi có \(M_i=N_i=x\). Khó tính chính xác xác suất để điều đó xảy ra, nhưng tổ hợp ít có khả năng xuất hiện nhất là \(M_i=N_i=9\), với xác suất chỉ \(1/(99 \times 9)\) trên mỗi bản ghi. Xác suất để tổ hợp đó xuất hiện ít nhất một lần trong \(10000\) bản ghi lớn hơn \(99{,}999\%\). Các giá trị \(x\) nhỏ hơn còn có xác suất cao hơn. Dĩ nhiên, xác suất để cả \(9\) tổ hợp cùng tồn tại nhỏ hơn con số ấy, và xác suất để điều đó xảy ra trong cả \(10\) bộ test còn nhỏ hơn nữa, nhưng vẫn đủ tốt. Ngoài ra, có một xác suất rất nhỏ rằng chữ cái biểu diễn \(0\) hoàn toàn không xuất hiện trong dữ liệu vào; nhưng nếu vậy thì không thuật toán nào có thể tìm ra nó. Vì đây là một test set hiển thị kết quả chấm, ta có thể thử gửi lời giải và xác nhận rằng nó được chấp nhận.

Ta có thể bổ sung các heuristic khác vào thuật toán. Ví dụ, nếu không thể tìm giá trị cho \(9\) theo cách trên và cần phân biệt hai chữ cái còn lại để gán cho \(9\) và \(0\), chỉ cần có một bản ghi mà \(R_i\) bắt đầu bằng một trong hai chữ cái đó là đủ để biết chữ cái ấy phải là \(9\), vì \(0\) không thể là chữ số đứng đầu. Điều này làm xác suất phương pháp hoạt động tăng thêm. Ta có thể tiếp tục thêm ngày càng nhiều heuristic để bao phủ các trường hợp còn lại, nhưng đến một lúc nào đó, thử một phương pháp tổng quát hơn sẽ dễ dàng hơn.

Test Set 2

Trong Test Set 2, xác suất để \(M_i\) chỉ có một chữ số là nhỏ, nên ta không thể trông chờ điều đó xảy ra, càng không thể trông chờ nó xảy ra nhiều lần và đồng thời thỏa các điều kiện bổ sung. Tuy nhiên, ta có thể xử lý tương tự các bản ghi mà \(M_i\) và \(R_i\) có cùng độ dài: chỉ cần dùng chữ số đầu tiên của \(M_i\) và chữ cái đầu tiên của \(R_i\), rồi sử dụng các cặp (chữ số, chữ cái) ấy giống như trong lời giải cho Test Set 1.

Test Set 3

Đến đây, có vẻ như ta phải bỏ đi toàn bộ những nhận xét ở trên, vì tất cả chúng đều dựa trên việc biết \(M_i\). Tuy nhiên, nhận xét "dùng chữ số/chữ cái đứng đầu" mà ta đã dùng để giải Test Set 2 thực ra cũng là bước đầu tiên để giải Test Set 3.

Trong Test Set 3, thông tin của mỗi bản ghi đến từ một số nguyên duy nhất chứ không phải hai số, nên ta không thể dùng mối liên hệ giữa hai thành phần như trước. Ta có thể bắt đầu bằng cách xét phân phối được dùng để sinh ra mẩu thông tin duy nhất mà mình có. Xác suất để một \(N_i\) cụ thể bằng \(x\) là tổng của \(10^{-16}/y\) với mọi \(y\) thuộc \([x,10^{16}-1]\), có thể xấp xỉ bởi \(10^{-16}(\ln 10^{16}-\ln x)\). Nói cách khác, xác suất này giảm theo \(x\). Vì thế, các chữ số đứng đầu nhỏ có khả năng xuất hiện cao hơn các chữ số đứng đầu lớn. Hơn nữa, dù mức giảm xác suất giữa việc kết quả thực tế bằng \(x\) và bằng \(x+1\) là nhỏ, mức giảm xác suất giữa việc chữ số đứng đầu bằng \(d\) và bằng \(d+1\) lại lớn, bởi nó gộp lại chênh lệch giữa xác suất của \(dS\) và xác suất của \((d+1)S\) đối với mọi hậu tố \(S\) có thể có. Đây là một phiên bản của định luật Benford.

Do đó, một lời giải khả thi là tính tần suất mỗi chữ cái xuất hiện ở vị trí chữ số đứng đầu, rồi gán chữ cái có tần suất cao nhất cho \(1\), cao thứ hai cho \(2\), và cứ tiếp tục như vậy. Chữ cái duy nhất không bao giờ xuất hiện ở vị trí đứng đầu, do đó có tần suất nhỏ nhất, cần được gán cho chữ số \(0\).

Dữ liệu kiểm thử

Chúng tôi khuyến nghị bạ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 1C — Overrandomized.