Phân tích bài toán

Tập dữ liệu nhỏ (Small dataset)

Giải pháp cho tập dữ liệu nhỏ của bài toán này khá đơn giản. Ta có thể duyệt qua tất cả các cách phân tích N thành tổng của các số nguyên dương và kiểm tra xem mỗi cột có các chữ số khác nhau hay không.

Vì có 190,569,292 cách phân tích số 100 thành tổng các số nguyên dương, thuật toán này có thể không chạy đủ nhanh. Tuy nhiên, chúng ta có thể tối ưu hóa bằng một nhận xét dễ dàng: các số hạng phải khác nhau (vì nếu có hai số hạng giống nhau, tất cả các cột của chúng sẽ có các chữ số giống nhau, vi phạm điều kiện các chữ số trong mỗi cột phải khác nhau). Điều này làm giảm tổng số cách phân tích của 100 xuống chỉ còn 444,793, đủ nhỏ cho nhu cầu của chúng ta.

Nhưng nếu bạn muốn thu hẹp không gian tìm kiếm hơn nữa, bạn có thể sử dụng quay lui (backtracking). Đây là một kỹ thuật tổng quát hoạt động như sau trong bài toán này: khi bạn đang tạo cách phân tích, bạn có thể kiểm tra xem có cột nào có hai chữ số bằng nhau sau khi thêm mỗi số hay không, chứ không chỉ đợi đến cuối cùng. Bằng cách đó, nhiều cách phân tích sai sẽ bị loại bỏ sớm và bạn có ít khả năng phải kiểm tra hơn.

Tập dữ liệu lớn (Large dataset)

Để tiếp cận tập dữ liệu lớn, chúng ta cần xoay góc nhìn đi 90 độ. Trong giải pháp trên, chúng ta đã tạo phương trình ẩn chữ từ trên xuống dưới. Bây giờ, chúng ta sẽ tạo nó từ phải sang trái (từ hàng đơn vị lên các hàng cao hơn).

Đầu tiên, chúng ta kiểm tra tất cả các khả năng cho các chữ số ở cột ngoài cùng bên phải (ít quan trọng nhất) sao cho chữ số cuối cùng của tổng của chúng khớp với chữ số yêu cầu. Sau đó, chúng ta tiếp tục với các chữ số cho cột tiếp theo bên trái, và cứ thế tiếp tục.

Giả sử chúng ta đã điền xong một vài cột bên phải. Chúng ta có thể lưu ý rằng những thứ liên quan đến chúng ta hiện tại là giá trị V của số dư (carry) từ các cột đã điền sang cột tiếp theo, số lượng K các số hạng trong cột vừa được điền, và một cờ boolean F cho biết liệu có chữ số 0 nào trong cột vừa được điền hay không (cờ này quan trọng vì nó ảnh hưởng đến việc liệu chúng ta có thể kết thúc số tương ứng tại đó hay không - vì số không thể có chữ số 0 ở đầu). Khi chúng ta biết các giá trị của V, K và F, các chữ số thực tế trong các cột đã điền không ảnh hưởng đến việc thực thi thuật toán tiếp theo.

Nhận xét này dẫn chúng ta đến giải pháp Quy hoạch động (Dynamic Programming) sau: hãy tính Count[i, V, K, F] được định nghĩa là số cách đặt các chữ số trong i cột cuối cùng sao cho tổng trong các cột đó khớp với N, có số dư là V, số lượng số hạng có ít nhất i chữ số là K, và F là 1 khi có một số hạng bắt đầu bằng chữ số 0 (tức là số hạng đó phải tiếp tục ở cột bên trái), 0 nếu ngược lại.

Để tính Count[i+1,...] từ Count[i,...], chúng ta cần xem xét tất cả các cách có thể để đặt tối đa K chữ số vào cột thứ i+1 từ bên phải. K tối đa là B (vì tất cả các chữ số trong một cột là khác nhau, số lượng số hạng không vượt quá số lượng chữ số khác nhau), có thể lên tới 100 trong tập dữ liệu lớn. Nhìn thoáng qua, điều này cho chúng ta ít nhất 100! (giai thừa của 100) khả năng, khiến ý tưởng của chúng ta vẫn chưa khả thi.

Nhưng đây là lúc một ý tưởng Quy hoạch động khác xuất hiện! Ta có thể nhận thấy rằng chúng ta không cần biết chính xác tất cả các chữ số của cột thứ i+1. Điều quan trọng đối với chúng ta là số lượng các chữ số đó, tổng của các chữ số đó, và liệu một trong số chúng có phải là số 0 hay không. Khi chúng ta biết những điều đó, chúng ta có thể nhân câu trả lời của mình với một số thích hợp (sẽ là tích của các hệ số nhị thức và giai thừa) để tính đến các cách khác nhau để gắn các chữ số đó vào các số đã hình thành trong i cột đầu tiên.

Vì vậy, chúng ta chạy một Quy hoạch động riêng biệt để tính Count2[K, S, F] được định nghĩa là số cách đặt K chữ số khác nhau trong một cột sao cho tổng của chúng là S và F biểu thị liệu một trong số chúng có phải là số 0 hay không. K tối đa là B, S là \(O(\mathbf{B}^2)\), nghĩa là chúng ta có \(O(\mathbf{B}^3)\) trạng thái, đủ nhỏ.

Quy hoạch động chính có \(O(\mathbf{B}^2 \cdot \text{số\_chữ\_số})\) trạng thái, và sử dụng bảng Count2, mỗi trạng thái có thể được xử lý trong \(O(\mathbf{B}^2)\) bằng cách xem xét số lượng chữ số trong cột thứ i+1 và số dư sang cột thứ i+2 (tổng yêu cầu trong cột thứ i+1 được xác định duy nhất bởi số dư đến nó, số dư từ nó, và chữ số tương ứng của N). Tổng thời gian chạy của giải pháp này là \(O(\mathbf{B}^4 \cdot \text{số\_chữ\_số})\).

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