Có ít nhất ba hướng giải bài toán này, với mức độ thành công khác nhau.

Vét cạn

Trong Test Set 1, \(N<100000\). Khi cần tìm \(A+B=N\), có ít hơn 100000 lựa chọn cho \(A\); một khi đã chọn \(A\), giá trị \(B=N-A\) được xác định. Ta thử lần lượt các giá trị \(A\) cho tới khi cả \(A\) và \(B\) đều không chứa chữ số 4.

Cách này không dùng được cho Test Set 2, vì trong trường hợp xấu nhất ta có thể phải kiểm tra gần \(10^9\) giá trị.

Cách ngẫu nhiên

Ta có thể lặp lại việc chọn đều ngẫu nhiên một ứng viên \(A\) trong đoạn \([1,N-1]\), đặt \(B=N-A\), rồi kiểm tra cả hai số có tránh được chữ số 4 hay không. Câu hỏi là xác suất thành công có đủ lớn để tìm được đáp án kịp thời hay không.

Trước hết, xét mọi chuỗi 9 chữ số, cho phép các số 0 ở đầu; tập này cũng bao gồm mọi số có ít hơn 9 chữ số. Xác suất một chữ số bất kỳ khác 4 là \(9/10\). Các vị trí độc lập nhau, nên xác suất cả 9 chữ số đều khác 4 là

Trong thực tế, tùy theo \(N\), ta có thể có ít lựa chọn hợp lệ hơn. Tuy vậy, con số này gợi ý rằng có khá nhiều ứng viên. Nếu xác suất \(A\) không chứa 4 không nhỏ hơn ước lượng quá nhiều, và việc \(A\) không chứa 4 không làm \(B\) dễ chứa 4 hơn đáng kể, ta có thể kỳ vọng tìm được đáp án nhanh.

Ta cũng có thể lập một cận chặt chẽ hơn. Gọi \(D\) là số chữ số của \(N\). Xét các số \(A<N\) được viết đủ \(D\) chữ số bằng cách thêm số 0 ở đầu; viết \(B=N-A\) theo cách tương tự.

Xét chữ số cuối của \(A\). Ta thất bại nếu chữ số đó là 4, hoặc nếu nó bằng \((N-4)\bmod10\) khiến chữ số cuối của \(B\) là 4. Do đó có ít nhất 8 trong 10 lựa chọn cho chữ số cuối là tốt.

Giả sử các chữ số thấp hơn đã được chọn mà chưa thất bại. Ở chữ số kế tiếp của \(A\), có nhiều nhất một giá trị làm chính chữ số đó bằng 4 và nhiều nhất một giá trị khác làm chữ số tương ứng của \(B\) bằng 4. Phép nhớ hoặc mượn từ các vị trí thấp hơn có thể thay đổi giá trị cụ thể nào là xấu, nhưng không thay đổi việc luôn còn ít nhất 8 trong 10 lựa chọn tốt. Lập luận này áp dụng cho cả \(D-1\) chữ số thấp.

Với chữ số đầu, chỉ cần lo chữ số đầu của \(A\) hoặc \(B\) bằng 4 khi chữ số đầu của \(N\) ít nhất là 4. Khi ấy chắc chắn có ít nhất 5 lựa chọn cho chữ số đầu của \(A\), và nhiều nhất hai lựa chọn xấu, nên ít nhất \(3/5\) lựa chọn là tốt. Vì vậy xác suất một \(A\) ngẫu nhiên hợp lệ không nhỏ hơn

Với \(D=9\), cận này xấp xỉ 0,1. Ta chỉ cần trung bình khoảng 10 lần thử, và xác suất vẫn thất bại sau 1000 lần thử chỉ khoảng \(10^{-46}\).

Nếu kiểm tra toàn bộ các số có \(D\) chữ số với \(D\) nhỏ, trường hợp ít nghiệm nhất là số gồm một chữ số 4 rồi đến \(D-1\) chữ số 9. Chẳng hạn với \(N=49999999\), khoảng 0,1258 số \(A\) có thể dùng được; cận 0,1 ở trên thực ra không quá lỏng.

Tuy nhiên, cách ngẫu nhiên rất khó thành công ở Test Set 3, nơi \(N\) có thể cỡ \(10^{100}\). Cận dưới trở thành

Ngay cả khi sinh ngẫu nhiên \(A\) chỉ từ các chữ số khác 4 rồi kiểm tra \(B\), tức thay các thừa số \(8/10\) bằng \(9/10\), cận vẫn chỉ cỡ \(10^{-5}\). Với 100 bộ test, đây không phải một giải pháp đáng tin cậy. Ta cần một cách kiến thiết tất định.

Kiến thiết theo từng chữ số

Ta có thể viết \(N\) thành tổng các chữ số nhân với lũy thừa của 10. Ví dụ:

Mọi chữ số đều biểu diễn được thành tổng của hai chữ số khác 4. Cụ thể, dùng \(4=2+2\); với mọi chữ số \(X\ne4\), dùng \(X=0+X\).

Áp dụng độc lập tại từng vị trí. Trong ví dụ trên, tách \(4\cdot1000\) thành \(2\cdot1000+2\cdot1000\), tách \(8\cdot100\) thành \(0\cdot100+8\cdot100\), và làm tương tự với các vị trí còn lại. Ta nhận được

Nói cách khác:

• tạo \(A\) bằng cách thay mọi chữ số 4 của \(N\) bằng 2, và thay mọi chữ số khác bằng 0;
• tạo \(B\) bằng cách thay mọi chữ số 4 của \(N\) bằng 2, còn các chữ số khác giữ nguyên.

Cả hai số đều không chứa chữ số 4 và tổng của chúng đúng bằng \(N\). Vì đề bảo đảm \(N\) có ít nhất một chữ số 4, \(A\) luôn dương. Các số 0 ở đầu có thể bỏ khi in.

Dù \(N\) có thể lớn tới một googol, ta không cần kiểu số nguyên lớn: chỉ cần xử lý hai chuỗi chữ số. Thuật toán chạy trong \(O(D)\) thời gian và dùng \(O(D)\) bộ nhớ, với \(D\) là số chữ số của \(N\).

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2019, Qualification Round, bài Foregone Solution; kho Google Coding Competitions (Apache-2.0).