Test Set 1

Test Set 1 có thể được giải bằng mô phỏng, đi ngược qua các số Tatiana đã đếm. Bắt đầu ở \(N\) và kiểm tra xem nó có gọn gàng hay không. Nếu có thì đã xong; nếu không, kiểm tra \(N-1\), rồi \(N-2\) nếu \(N-1\) vẫn chưa gọn gàng, và cứ thế tiếp tục.

Kiểm tra một số có gọn gàng hay không chỉ cần một lượt qua các chữ số. Số chữ số của mọi số không vượt quá \(N\) có cận \(\log_{10}N\). Vì ta duyệt nhiều nhất \(O(N)\) số, tổng độ phức tạp là \(O(N\log N)\). Cách này dễ dàng đủ nhanh khi \(N\le1000\), nhưng không chịu nổi Test Set 2 với \(N\) tới \(10^{18}\). Nếu bắt đầu ở số không gọn gàng 111111111111111110, ta phải đếm lùi một quãng rất dài mới tới đáp án 99999999999999999!

Để duyệt các chữ số, có thể dùng tiện ích của ngôn ngữ để đổi số thành chuỗi, hoặc liên tục lấy phần dư modulo 10 để lấy chữ số cuối rồi chia cho 10 để bỏ chữ số đó.

Test Set 2: cách tham lam

Có một cách tham lam hiệu quả cho Test Set 2, nhưng nó có vài trường hợp khá tinh tế.

Gọi các chữ số của \(N\), từ hàng cao nhất đến hàng thấp nhất (từ trái sang phải), là \(N_1,N_2,\ldots,N_L\). Gọi \(A\) là đáp án cần tìm, tức số gọn gàng Tatiana đếm gần đây nhất. Ta muốn \(A\) có càng nhiều chữ số bên trái trùng với \(N\) càng tốt, vì điều đó làm \(N-A\) nhỏ nhất.

Tìm “nghịch thế” đầu tiên trong \(N\), tức chỉ số nhỏ nhất \(i\) sao cho \(N_i>N_{i+1}\). Nếu không có chỉ số như vậy thì \(N\) đã gọn gàng và \(A=N\). Nếu có, không số nào bắt đầu bằng dãy \(N_1,N_2,\ldots,N_i\) lại có thể vừa nhỏ hơn \(N\) vừa gọn gàng. Vì thế, ta thử để đáp án bắt đầu bằng \(A_1=N_1,A_2=N_2,\ldots,A_{i-1}=N_{i-1}\). Chữ số tiếp theo \(A_i\) phải nhỏ hơn \(N_i\), nên thử \(A_i=N_i-1\). Nếu \(A_i\ge A_{i-1}\), ta đặt mọi chữ số từ \(A_{i+1}\) trở đi thành 9; như vậy \(A\) lớn nhất có thể mà vẫn gọn gàng. Nhưng nếu \(A_i<A_{i-1}\), ta vừa tạo ra một nghịch thế khác, nên phải thử chỉ giữ các chữ số đến \(N_{i-2}\). Nếu vẫn không được, tiếp tục lùi tới \(N_{i-3}\), v.v. Thậm chí ta có thể không giữ chữ số nào của \(N\): với \(N=211\) ta được \(A=199\). Đôi khi ngay cả việc đó cũng không theo khuôn trên; chẳng hạn \(N=100\) có đáp án 99.

Tóm lại, nếu có nghịch thế đầu tiên tại \(i\), hãy tìm chỉ số lớn nhất \(j<i\) sao cho \(N_j<N_{j+1}\). Nếu không có thì đặt \(j=0\). Khi đó \(A\) bắt đầu bằng \(N_1,N_2,\ldots,N_j,N_{j+1}-1\), rồi có đủ chữ số 9 để tổng độ dài là \(L\). Ngoại lệ duy nhất là \(j=0\) và \(N_1=1\); khi ấy đáp án gồm \(L-1\) chữ số 9.

Chiến lược này chỉ cần một lượt tiến rồi một lượt lùi qua các chữ số, nên tốn \(O(\text{số chữ số của }N)=O(\log N)\). Ta thậm chí không cần chuyển chuỗi đầu vào thành số nguyên.

Để tránh một phần độ phức tạp khi cài đặt, có thể đơn giản thử mọi dạng SD999...99, trong đó S lần lượt là mỗi tiền tố của \(N\) (kể cả tiền tố rỗng), D là từng chữ số từ 0 đến 9, và số chữ số 9 được chọn sao cho tổng độ dài là \(L\). Cũng phải thêm trường hợp đặc biệt gồm \(L-1\) chữ số 9. Đáp án chắc chắn nằm trong số đó: chọn số gọn gàng lớn nhất không vượt \(N\). Đây là mẹo thường gặp để đơn giản hóa mã tham lam: thử nhiều phương án hơn mức thật sự cần, miễn số phương án vẫn xử lý được. Thường việc tìm phương án tốt nhất trong một tập nhỏ dễ cài đặt hơn việc viết đủ các kiểm tra để loại trước mọi phương án thừa.

Test Set 2: cách tổ hợp

Một cách khác dùng thêm một chút toán là nhận thấy số lượng số gọn gàng rất ít. Với độ dài cố định \(L\), số số gọn gàng bằng số cách đặt 8 quả bóng vào \(L+1\) hộp. Mỗi hộp biểu diễn một vị trí trước chữ số đầu, giữa hai chữ số, hoặc sau chữ số cuối; mỗi quả bóng biểu diễn thao tác “tăng số hiện tại thêm 1”. Chẳng hạn, số gọn gàng 2455 được biểu diễn bằng 1 bóng ở hộp đầu (bỏ qua 1), 2 bóng ở hộp thứ hai (từ 2 lên 4), 1 bóng ở hộp thứ ba (từ 4 lên 5), 0 bóng ở hộp thứ tư (chữ số 5 lặp lại), và tất cả bóng còn lại ở hộp cuối (tăng từ 5 đến 9 nhưng không còn chữ số nào để viết).

Số cách đặt 8 bóng vào \(L+1\) hộp là

và với \(L\) lớn nhất là 18, con số này nhỏ hơn hai triệu. Do đó có thể liệt kê mọi số gọn gàng, bỏ qua tất cả số khác, rồi trả về số lớn nhất tìm được mà không vượt \(N\). Có thể dùng đệ quy như mã giả sau:

best = 1
enum(current_string, current_digit, digits_left):
  if digits_left > 0
    enum(current_string + current_digit, current_digit, digits_left - 1)
    enum(current_string + (current_digit + 1), current_digit + 1, digits_left - 1)
  else
    if best ≤ string_to_int(current_string) ≤ N
      best = string_to_int(current_string)

Ta cũng có thể định nghĩa một hàm tham lam tìm số gọn gàng kế tiếp rồi dùng nó, như phần sau.

Test Set 2: tìm kiếm nhị phân

Bài toán gốc là: cho \(N\), tìm số nguyên lớn nhất \(Y\le N\) sao cho \(Y\) gọn gàng. Xét bài toán liên quan dễ hơn: cho \(X\), tìm số nguyên nhỏ nhất \(Y\ge X\) sao cho \(Y\) gọn gàng. Giả sử các chữ số của \(X\) từ trái sang phải là \(X_1,X_2,\ldots,X_L\). Ta tạo \(Y\) bằng cách tìm nghịch thế đầu tiên, tức chỉ số nhỏ nhất \(i\) sao cho \(X_i>X_{i+1}\), giữ \(X_1,X_2,\ldots,X_i\), rồi thêm đủ bản sao của \(X_i\) để \(Y\) dài bằng \(X\). Ví dụ, với 13254, nghịch thế đầu tiên là 32; thay mọi thứ sau chữ số 3 bằng các chữ số 3 ta được 13333. Nếu không có nghịch thế thì \(X\) đã gọn gàng và \(Y=X\). Thuật toán này tốn \(O(L)\).

Sau khi giải được bài phụ, ta tìm kiếm nhị phân để tìm khoảng nhỏ nhất \([X,N]\) sao cho số \(Y\) tương ứng với \(X\) theo định nghĩa trên không lớn hơn \(N\). Cách này tốn \(O(\log^2N)\): tìm kiếm nhị phân có \(O(\log N)\) bước và mỗi bước chạy thuật toán tham lam \(O(L)\), trong khi \(L=O(\log N)\). Nó kém hiệu quả hơn cách tham lam trực tiếp nhưng vẫn dễ dàng đủ nhanh cho Test Set 2.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Qualification Round, bài Tidy Numbers.