Phân tích

Gọi \(x\) là số đầu vào. Chúng ta muốn tìm số tiếp theo \(y\). Chúng ta ký hiệu \(L(s)\) là độ dài của chuỗi \(s\), tức là số lượng chữ số trong \(s\).

Trường hợp 1: Nếu tất cả các chữ số trong \(x\) đều không tăng (giảm dần hoặc bằng nhau), ví dụ \(x = 776432100\), thì \(x\) đã là số lớn nhất trong số các số trong danh sách có \(L(x)\) chữ số. Số tiếp theo, \(y\), phải có thêm một chữ số, đó là thêm một chữ số 0. Thực tế \(y\) phải là số nhỏ nhất có \(L(x)+1\) chữ số. Để có được \(y\), chúng ta đặt chữ số khác 0 nhỏ nhất lên đầu, và tất cả các chữ số còn lại được đặt theo thứ tự không giảm.

Trường hợp 2: Nếu không, \(x\) có thể được viết dưới dạng nối chuỗi \(x = ab\), trong đó \(b\) là hậu tố không tăng dài nhất của \(x\), sao cho \(d\), chữ số cuối cùng của \(a\), nhỏ hơn chữ số đầu tiên của \(b\). Gọi \(d'\) là chữ số nhỏ nhất trong số tất cả các chữ số trong \(b\) mà lớn hơn \(d\).
Vì \(b\) không tăng, \(x\) là số lớn nhất trong số những số có \(L(x)\) chữ số và bắt đầu bằng tiền tố \(a\). Các chữ số \(L(a)\) đầu tiên của \(y\) phải lớn hơn \(a\). Cách nhỏ nhất chúng ta có thể làm là thay thế \(d\) bằng \(d'\), và sau đó đối với các chữ số còn lại, chúng ta sắp xếp chúng theo thứ tự không giảm.
Hãy xem xét một ví dụ khác: \(x = 134266530\). Khi đó \(a = 1342\), \(b = 66530\), \(d = 2\), và \(d' = 3\). Số tiếp theo là \(y = 134302566\).

Thực tế, chúng ta có thể thống nhất hai trường hợp trên. Vì số lượng chữ số 0 không bị hạn chế (ngoại trừ việc số lượng các chữ số từ 1 đến 9 phải giữ nguyên), chúng ta có thể tưởng tượng có thêm một chữ số 0 ở đầu \(x\), do đó Trường hợp 1 được đưa về Trường hợp 2.

Cách cài đặt

Quy trình mô tả ở trên thực chất chính là thuật toán tìm hoán vị kế tiếp (next permutation) của một dãy hữu hạn trong một số ngôn ngữ lập trình. Dưới đây là một giải pháp về cơ bản chỉ là một dòng trong C++ (sử dụng hàm std::next_permutation).

  deque<char> f;
  ...
  f.push_front('0');
  next_permutation(f.begin(), f.end());
  if (f.front() == '0') f.pop_front();

Độ phức tạp

Độ phức tạp của thuật toán tìm hoán vị kế tiếp là \(O(L)\), trong đó \(L\) là số lượng chữ số của \(N\). Với \(N \le 10^{20}\), \(L\) tối đa khoảng 21 (sau khi thêm số 0 ở đầu), do đó thuật toán cực kỳ hiệu quả.

Dựa trên phân tích chính thức của Google Code Jam.