Phân tích: Collecting Cards

Bài toán này yêu cầu một số kiến thức cơ bản về xác suất và tổ hợp. Chúng ta muốn tính số lượng gói thẻ dự kiến cần mua để có được tất cả \(C\) loại thẻ khác nhau.

Gọi \(E(x)\) là số lượng gói thẻ dự kiến chúng ta cần mua nếu chúng ta đã bắt đầu với \(x\) loại thẻ khác nhau (không quan trọng đó là những thẻ nào). Đáp án của bài toán là giá trị \(E(0)\). Chúng ta cũng biết rằng \(E(C) = 0\), vì nếu chúng ta đã có đủ \(C\) loại thẻ khác nhau, chúng ta không cần mua thêm bất kỳ gói nào nữa.

Chúng ta có thể thiết lập các phương trình hữu ích cho các giá trị khác của \(E(x)\) bằng cách suy nghĩ về tất cả các kết quả có thể xảy ra sau khi mua thêm một gói thẻ. Gọi \(T(x, y)\) là xác suất để có được \(y\) loại thẻ khác nhau sau khi mở một gói mới, khi hiện tại đang có \(x\) loại thẻ. Khi đó chúng ta có phương trình sau cho \(E(x)\):

Chúng ta cần mua ít nhất một gói mới, đó là lý do có số 1 trong công thức. Số lượng gói dự kiến cần mua sau đó phụ thuộc vào việc chúng ta nhận được bao nhiêu thẻ mới. Nếu chúng ta kết thúc với \(y\) loại thẻ khác nhau, chúng ta cần cộng thêm số gói dự kiến để đạt đến \(C\) bắt đầu từ \(y\), tức là \(E(y)\), nhân với xác suất của trường hợp cụ thể này là \(T(x, y)\).

Lưu ý rằng trong tổng trên, \(y\) có thể bằng \(x\) (nếu tất cả các thẻ trong gói mới đều là những thẻ chúng ta đã có). Khi đó, \(E(x)\) xuất hiện ở cả hai vế của phương trình. Chúng ta có thể chuyển số hạng chứa \(E(x)\) sang một vế để giải:

\(E(x) = 1 + \sum_{y=x}^{x+N} T(x, y) E(y)\)
\(E(x) (1 - T(x, x)) = 1 + \sum_{y=x+1}^{x+N} T(x, y) E(y)\)
\(E(x) = \frac{1 + \sum_{y=x+1}^{x+N} T(x, y) E(y)}{1 - T(x, x)}\)

Tất cả các phương trình này tạo thành một hệ phương trình tuyến tính với ma trận tam giác trên, có thể giải được bằng phương pháp thế ngược (back substitution). Chúng ta tính \(E(C-1)\), sau đó là \(E(C-2)\), ..., cho đến \(E(0)\).

Bây giờ chúng ta cần tính các giá trị của ma trận \(T\) (tức là các giá trị \(T(x, y)\) cho tất cả \(x\) và \(y\) khác nhau). Chúng ta sẽ tính toán điều này với sự trợ giúp của hệ số tổ hợp (binomial coefficients): số lượng các gói thẻ khác nhau có thể có là:

Để kết thúc với \(y\) loại thẻ khác nhau khi đang có \(x\) loại, chúng ta cần chọn thêm \(y-x\) thẻ mới từ \(C-x\) thẻ chưa sở hữu, và \(N-(y-x)\) thẻ còn lại phải được chọn từ \(x\) thẻ đã có. Xác suất khi đó là:

(Đối với những người có kiến thức về xác suất, đây được gọi là phân phối siêu bội (hypergeometric distribution)).

Trường hợp đặc biệt khi \(N = 1\) chính là bài toán nổi tiếng thu thập tem phiếu (coupon collector's problem).

Độ phức tạp

• Tính các hệ số tổ hợp: \(O(C^2)\).
• Giải hệ phương trình bằng thế ngược: \(O(C \cdot N)\).
• Tổng độ phức tạp: \(O(T \cdot C^2)\). Với \(C=40\), thuật toán này chạy rất nhanh.

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