Phân tích

Test Set 1

Với tổng số chữ số không quá \(8\), ta duyệt mọi cặp số có thể dựng và chọn cặp tối ưu. Một cách là duyệt mọi hoán vị của các chữ số, coi mỗi hoán vị là một xâu rồi thử mọi vị trí tách nó thành hai phần. Với mỗi cách tách, dựng hai số và cập nhật đáp án. Phải loại mọi cách mà một trong hai số bắt đầu bằng 0.

Ký hiệu \(N=|D|\), độ phức tạp là \(O(N!\cdot N^2)\).

Test Set 2

Trước hết xác định độ dài hai số; chúng phải gần nhau nhất có thể. Nếu \(N\) chẵn, mỗi số phải có đúng \(N/2\) chữ số. Nếu \(N\) lẻ, số lớn hơn có \(\lceil N/2\rceil\) chữ số và số nhỏ hơn có \(\lfloor N/2\rfloor\) chữ số. Sau đây gọi số lớn là \(A\), số nhỏ là \(B\).

Khi \(N\) lẻ, thử mọi chữ số khác \(0\) làm chữ số đầu của \(A\) và \(B\). Vì \(A\) đã chắc chắn lớn hơn \(B\), ta muốn phần còn lại của \(A\) nhỏ nhất và phần còn lại của \(B\) lớn nhất. Hai mục tiêu bổ trợ nhau: lấy \(\lfloor N/2\rfloor\) chữ số còn lại nhỏ nhất, theo thứ tự không giảm, để hoàn thiện \(A\); dùng phần còn lại theo thứ tự không tăng để hoàn thiện \(B\).

Cũng có thể chọn tham lam các chữ số đầu nhưng phải tránh \(0\). Cách đơn giản thử mọi cặp chữ số đầu chỉ tốn \(O(b^2N)\), với cơ số \(b=10\), đủ nhanh.

Khi \(N\) chẵn, chỉ chọn chữ số đầu chưa quyết định duy nhất phần còn lại vì chưa chắc \(A>B\). Tuy nhiên, ta vẫn dùng được kỹ thuật tương tự.

Giả sử có tiền tố độ dài \(i\), \(A_1A_2\ldots A_i\) của \(A\) và \(B_1B_2\ldots B_i\) của \(B\). Ta bảo đảm \(A>B\) bất kể các chữ số về sau khi và chỉ khi tồn tại \(k\le i\) sao cho \(A_j=B_j\) với mọi \(1\le j<k\) và \(A_k>B_k\).

Do đó, duyệt mọi cách dựng các tiền tố bằng nhau \(A_1\ldots A_{k-1}\) và \(B_1\ldots B_{k-1}\), rồi mọi cặp \(A_k,B_k\). Sau đó hoàn thiện để \(A\) nhỏ nhất, \(B\) lớn nhất bằng kỹ thuật trên; cập nhật đáp án bằng hiệu của hai số. Vẫn phải bảo đảm không số nào bắt đầu bằng \(0\).

Việc chọn các cặp tiền tố bằng nhau có \(O(2^{N/2})\) khả năng: không thể có quá \(N/2\) cặp, và thứ tự giữa chúng không quan trọng miễn không bắt đầu bằng \(0\). Chọn \(A_k,B_k\) tốn \(O(b^2)\), dựng hai số sau khi có tiền tố tốn \(O(N)\). Tổng độ phức tạp là \(O(2^{N/2}b^2N)\), rất nhanh trong thực tế với cài đặt tốt.

Có thể tối ưu thêm nhưng không cần cho giới hạn đề. Có cách dùng số loại chữ số để thay \(N\) trong số mũ bằng cơ số \(b\), và cũng có cách tham lam giải toàn bài trong thời gian tuyến tính. Hơn nữa, nếu đầu vào và đầu ra ở dạng mã hóa độ dài đoạn (run-length encoding), bài có thể giải tuyến tính theo kích thước biểu diễn đó, tức \(O(\log N)\).

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