Phân tích: Ugly Numbers

Như đề bài đã nêu rõ, có \(3^{D-1}\) cách mà bạn cần xem xét. Khi \(D\) không lớn hơn 13, như trong tập dữ liệu nhỏ (small dataset), người ta có thể đơn giản là tạo ra tất cả các kết hợp có thể và tính toán từng kết hợp đó. Tuy nhiên, với \(D\) lên tới 40, phương pháp vét cạn rõ ràng là quá chậm.

Như bạn có thể mong đợi từ một cuộc thi lập trình, thuật ngữ kỳ diệu ở đây là quy hoạch động. Đây là bài toán đầu tiên trong Google Code Jam 2008 thuộc thể loại quy hoạch động (DP) chuẩn; và có thể chắc chắn rằng sẽ còn nhiều bài toán như vậy nữa.

Như trong bất kỳ bài toán DP nào, nhiệm vụ đầu tiên là cấu trúc bài toán theo một cách tốt để không có quá nhiều số cần tính toán, và mỗi số có thể được tính toán dễ dàng từ các số trước đó. Nếu bạn quan sát lời giải của những người dẫn đầu trong vòng thi này, bạn sẽ thấy, mặc dù thuật toán của họ có khác biệt đôi chút, nhưng tất cả đều chứa con số kỳ diệu sau:

2 · 3 · 5 · 7 = 210.

Giả sử chúng ta có hai số, \(x\) và \(y\), việc biết tính "xấu xí" của \(x\) và \(y\) là không đủ để quyết định xem \(x + y\) và \(x - y\) có xấu xí hay không. Mặt khác, chúng ta không cần giá trị chính xác của \(x\) và \(y\). Chỉ cần biết \(x \pmod{210}\) và \(y \pmod{210}\) là đủ để chúng ta quyết định xem, ví dụ, \(x + y\) có xấu xí hay không. (Vì \(210 = 2 \times 3 \times 5 \times 7\)).

Đối với những người thích các thuật ngữ toán học, chúng ta đang sử dụng định lý số dư Trung Hoa. Bài toán của chúng ta có thể được xem như là các phép toán số học trên nhóm cyclic \((Z_{210}, +)\).

Vì vậy, hãy phác thảo bước trung tâm nhất trong giải pháp quy hoạch động của chúng ta. Chúng ta muốn tính toán:

dyn[i][x] := number of ways we get an expression evaluating 
          to x (mod 210) if we only consider the first i
          characters of the string. (*)

Như vậy, chúng ta chỉ có \(40 \times 210\) trạng thái cần xem xét. Đối với mỗi dyn[i][x], chúng ta thử tất cả các vị trí có thể để chèn dấu '+' hoặc '-' cuối cùng. Nếu dấu cuối cùng là '+' trước vị trí \(j\) (\(j < i\)), và số được tạo bởi các chữ số từ vị trí \(j\) đến vị trí \(i\) là \(d\), thì chúng ta muốn biết dyn[j-1][(x-d)%210]. Mặt khác, nếu dấu được chèn là '-', thì chúng ta muốn xem xét dyn[j-1][(x+d)%210].

Dưới đây là một cách cài đặt điêu luyện từ Derek Kisman. Giải pháp C++ hoàn chỉnh của anh ấy tuân theo ý tưởng trên, với một chút biến tấu và một số mẹo lập trình hay.

#define MOD (2*3*5*7)
string s;
long long dyn[41][MOD];

main() {
  int N, prob=1;
  for (cin >> N; N--;) {
    cin >> s;
    memset(dyn, 0, sizeof(dyn));
    dyn[0][0] = 1;
    for (int i = 0; i < s.size(); i++)
    for (int sgn = (i==0) ? 1 : -1; sgn <= 1; sgn += 2) {
      int cur = 0;
      for (int j = i; j < s.size(); j++) {
        cur = (cur*10 + s[j]-'0')%MOD;
        for (int x = 0; x < MOD; x++)
          dyn[j+1][(x+sgn*cur+MOD)%MOD] += dyn[i][x];
      }
    }
    long long ret = 0;
    for (int x = 0; x < MOD; x++)
      if (x%2 == 0 || x%3 == 0 || x%5 == 0 || x%7 == 0)
        ret += dyn[s.size()][x];
    cout << "Case #" << prob++ << ": " << ret << endl;
  }
}

Thông tin thêm:

• Quy hoạch động
• Định lý số dư Trung Hoa

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