Phân tích

Test Set 1

Trước hết, nối gì vào số đầu tiên không bao giờ là tối ưu. Với giới hạn nhỏ, ta có thể duyệt mọi cách nối chữ số vào số thứ hai và thứ ba sao cho đạt yêu cầu. Ta dừng khi biết chắc không thể cải thiện nữa, chẳng hạn khi cả hai số đều đã dài hơn \(4\) chữ số.

Test Set 2

Ta dùng chiến lược tham lam: bắt đầu từ số thứ hai, biến mỗi số thành một số lớn hơn số ngay trước nó nhưng nhỏ nhất có thể. Lựa chọn này dùng ít chữ số nhất cho số hiện tại, đồng thời khiến bài toán của số kế tiếp dễ nhất có thể, nên là tối ưu.

Còn lại là tính lựa chọn đó hiệu quả. Phát biểu chính xác: cho hai số nguyên \(A,B\), tìm \(B'\) nhỏ nhất sao cho \(B'>A\) và \(B\) là tiền tố của \(B'\). Ký hiệu số chữ số của \(Z\) là \(\operatorname{len}(Z)\).

• Nếu \(A<B\), lấy \(B'=B\).
• Nếu \(A\ge B\) và \(\operatorname{len}(A)=\operatorname{len}(B)\), nối bất kỳ chữ số nào vào \(B\) cũng làm nó lớn hơn \(A\); để nhỏ nhất, nối một chữ số \(0\).

Trường hợp còn lại là \(B\) có ít chữ số hơn \(A\). Đặt \(k=\operatorname{len}(A)-\operatorname{len}(B)\).

Trước hết thử \(B'=B\cdot10^k\), tức nối \(k\) chữ số \(0\). Nếu \(B'>A\), đây là đáp án tối ưu.

Tiếp theo, kiểm tra liệu \(B'\) có thể có cùng số chữ số với \(A\) hay không. Nếu ngay cả khi nối \(k\) chữ số \(9\) vào \(B\) mà vẫn không lớn hơn \(A\), thì \(B'\) bắt buộc dài hơn \(A\). Khi đó chỉ cần làm \(B\) dài hơn \(A\) đúng một chữ số và nhỏ nhất có thể bằng cách nối \(k+1\) chữ số \(0\).

Nếu nối \(k\) chữ số \(0\) còn quá nhỏ nhưng nối \(k\) chữ số \(9\) đã lớn hơn \(A\), thì \(B\) thực ra là một tiền tố của \(A\). Khi ấy \(B'=A+1\) là đáp án tối ưu.

Mọi kiểm tra trên tuyến tính theo độ dài \(A,B\), và mỗi số đầu vào được xử lý nhiều nhất một lần trong vai trò \(A\), một lần trong vai trò \(B\). Các số có thể dài thêm sau mỗi thao tác, nhưng mỗi lần chỉ thêm một chữ số. Vì thế toàn thuật toán là bậc hai theo tổng số chữ số đầu vào và tuyến tính theo số chữ số đầu ra.

Ví dụ, nếu đầu vào gồm \(N\) số cùng độ dài theo thứ tự giảm nghiêm ngặt, số đầu ra thứ \(i\) dài hơn số trước đúng một chữ số, cần tổng cộng \(N(N-1)/2\) thao tác.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1A, bài Append Sort.