Tập dữ liệu nhỏ

Với tập nhỏ, chỉ cần tìm kiếm theo chiều rộng (BFS) để tìm số bước ít nhất sinh ra mọi số từ 1 tới \(10^6\). Ta không bao giờ muốn tạo một số lớn hơn \(10^6\) rồi đảo nó để nhận số nhỏ hơn, nên chỉ cần xét \(10^6\) trạng thái.

Tập dữ liệu lớn

Với tập lớn, lời giải sau hoạt động. Hai ý tưởng chính là:

• Trước tiên nên tạo các số \(10,100,1000,\ldots\) cho đến khi đạt một lũy thừa của 10 có cùng số chữ số với \(N\), rồi mới tạo \(N\).
• Trong khi số hiện tại có một số lượng chữ số cố định, chỉ nên đảo nhiều nhất một lần.

Thuật toán gồm hai phần.

Phần 1: Đạt đúng số chữ số nhanh nhất có thể

Để đi từ số 1 theo sau bởi \(X\) chữ số 0 đến số 1 theo sau bởi \(X+1\) chữ số 0, trước tiên đếm tăng cho đến khi nửa phải của số được lấp đầy bằng các chữ số 9. Khi độ dài lẻ, chọn nửa trái ngắn hơn nửa phải. Sau đó đảo số, tiếp tục đếm tới số gồm toàn chữ số 9, rồi cộng 1. Riêng từ 1 tới 10 hiển nhiên không cần đảo.

Phần 2: Đếm thẳng tới đáp án, hoặc đếm một đoạn, đảo rồi đếm tiếp, tùy cách nào nhanh hơn

Khi đã ở lũy thừa của 10 có đúng số chữ số, dùng cách tương tự để tạo \(N\): đếm cho tới khi nửa phải trông giống phần đảo của nửa trái của \(N\), đảo số, rồi đếm tới đích. Ví dụ, để đi từ 100000 tới 123456:

• đếm tới 100321;
• đảo để được 123001;
• đếm tới 123456.

Nếu nửa trái chỉ là một chữ số 1 theo sau bởi các chữ số 0, ta có thể bỏ qua hai bước đầu và đếm thẳng tới \(N\).

Khi nửa phải của \(N\) toàn chữ số 0, phương pháp trên không hoạt động vì sau phép đảo, nửa phải sẽ kết thúc bằng 1. Thay vào đó, làm cho nửa phải trông giống nửa trái của \(N-1\), đảo rồi đếm tới \(N\). Ví dụ, để đi từ 100000 tới 300000:

• đếm tới 100992;
• đảo để được 299001;
• đếm tới 300000.

Tuy nhiên, cũng như trước, nếu nửa trái của \(N-1\) chỉ là một chữ số 1 theo sau bởi các chữ số 0 thì có thể bỏ qua hai bước đầu. Chẳng hạn, để đi từ 100000 tới 101000, tốt nhất là đếm tăng trực tiếp.

Tại sao chỉ cần đảo nhiều nhất một lần? Mục đích của phép đảo là giúp đạt nửa trái mong muốn nhanh nhất có thể. Còn việc tăng nửa phải tới giá trị cần thiết được thực hiện tốt hơn bằng cách đếm tăng trực tiếp. Nói cách khác, thực hiện nhiều phép đảo không đem lại thêm lợi ích.

Thuật toán xử lý \(O(\log_{10}N)\) nhóm chữ số và dùng bộ nhớ phụ \(O(\log_{10}N)\) cho biểu diễn thập phân.

Cài đặt mẫu bằng C++:

#include <cstdio>
#include <cstdlib>

#include <string>
#include <algorithm>

using namespace std;

long long p10[10];  // p10[i] == 10^i

bool is_1_followed_by_0s(string S) {
  reverse(S.begin(), S.end());
  return atoi(S.c_str()) == 1;
}

int solve(long long N) {
  if (N < 10) return N;  // Trivial case.

  char X[20]; sprintf(X, "%lld", N);
  string S = X;
  int M = S.length();  // Number of digits of N.

  // Starts from 1.
  int ans = 1;

  // Part 1: from 1, get to the M digits as fast as possible.
  for (int d = 1; d < M; d++) {
    // For digits = 7, it starts from 7 digits:    1000000
    ans += p10[(d + 1) / 2] - 1; // Count up 9999: 1009999
    if (d > 1) ans++;            // Flip once:     9999001
    ans += p10[d / 2] - 1;       // Count up 999: 10000000
  }


  // Part 2:

  // Split N into two halves. For example N = "1234567"
  string L = S.substr(0, M / 2);  // L = "123"
  string R = S.substr(M / 2);     // R = "4567"

  // Handles the case where the right half is all zeroes.
  if (atoi(R.c_str()) == 0) return solve(N - 1) + 1;

  // Special case: Count directly to the answer.
  if (is_1_followed_by_0s(L))
    return ans + atoi(R.c_str());

  // Count until the right half looks like the left half of N
  // in reverse. In this case, count from 1000000 to 1000321.
  reverse(L.begin(), L.end());
  ans += atoi(L.c_str());

  // Flip 1000321 to 1230001.
  ans++;

  // Count up 4566 to the target from 1230001 to 1234567.
  ans += atoi(R.c_str()) - 1;
  return ans;
}

int main() {
  p10[0] = 1;
  for (int i = 1; i < 10; i++)
    p10[i] = p10[i - 1] * 10;

  long long T, N;
  scanf("%lld", &T);
  for (int TC = 1; TC <= T; TC++) {
    scanf("%lld", &N);
    printf("Case #%d: %d\n", TC, solve(N));
  }
}

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