Phân tích: Good Luck

Yếu tố may mắn

Bài toán này khác thường ở chỗ bạn không có đầy đủ thông tin và buộc phải đưa ra dự đoán như một phần của giải pháp. Chúng tôi nghĩ rằng đây sẽ là một sự thay đổi thú vị so với bối cảnh xác định thông thường.

Tuy nhiên, may mắn không đóng vai trò quá lớn trong bài toán này. Bộ dữ liệu đầu tiên đủ dễ để nhiều cách tiếp cận có thể hoạt động. Bộ dữ liệu thứ hai khó hơn, nhưng chúng tôi ước tính rằng một giải pháp tối ưu sẽ có cơ hội thành công rất cao: xác suất một giải pháp tối ưu thất bại chỉ ở mức 1 trên một triệu! Điều này là do 8000 là một số lượng lớn các dự đoán độc lập, và giới hạn X khá thận trọng: thấp hơn khoảng 5 độ lệch chuẩn so với số lượng dự đoán đúng kỳ vọng.

Chiến lược tối ưu

Người ta có thể bị cám dỗ áp dụng các phương pháp heuristic khác nhau để cố gắng suy luận về loại số ẩn nào có khả năng xảy ra. Trong trường hợp này, tốt nhất là tiếp cận vấn đề một cách khoa học và chỉ đơn giản là luôn chọn khả năng có xác suất thành công cao nhất!

Để làm điều đó, chúng ta tính toán xác suất của mỗi trong số 18564 khả năng (đối với bộ dữ liệu lớn hơn) và chọn khả năng lớn nhất.

Tại sao lại là 18564? Có 7 lựa chọn cho mỗi trong số 12 số ẩn. Điều đó dường như mang lại \(7^{12} = 13,841,287,201\) khả năng, một con số rất lớn. Nhưng, thứ tự của các số ẩn không quan trọng, điều này làm giảm số lượng các khả năng khác nhau xuống còn tổ hợp lặp: \(\binom{12+7-1}{7-1} = 18564\). Hãy thử chứng minh công thức này! Hoặc chỉ cần liệt kê tất cả và đếm.

Xác suất tiên nghiệm: K=0

Điều gì xảy ra nếu \(K=0\), tức là chúng ta không có thông tin gì về các số ẩn? Có vẻ như khi đó việc chúng ta đoán gì không quan trọng, vì tất cả các khả năng đều có khả năng xảy ra như nhau. Nhiều thí sinh đã mắc sai lầm này. Một số khả năng có xác suất tiên nghiệm cao hơn những khả năng khác, ngay cả khi không có bất kỳ thông tin bổ sung nào!

Ví dụ, đối với bộ dữ liệu nhỏ: bộ số 333 ít có khả năng xảy ra hơn bộ 234. Chính xác là ít hơn 6 lần. Tại sao? Bởi vì bộ 234 có thể được tạo ra theo 6 cách khác nhau (234, 243, 324, 342, 423, 432) trong khi 333 chỉ có thể được tạo ra theo 1 cách duy nhất.

Nói chung, nếu chữ số d xuất hiện \(C_d\) lần trong số các thẻ ẩn, xác suất của bộ đó là \(N! / (C_2! \times \dots \times C_M! \times (M-1)^N)\).

K=1 và định lý Bayes

Vậy chúng ta đã tính toán được xác suất tiên nghiệm của mọi bộ thẻ ẩn, nhưng điều đó chưa sử dụng thông tin quan trọng có sẵn: K tích của các tập con ngẫu nhiên. Làm thế nào để sử dụng thông tin đó? Xác suất có điều kiện là công cụ phù hợp cho công việc này.

Hãy bắt đầu với \(K=1\). Đối với mỗi bộ số ẩn, \(A\), chúng ta đã biết xác suất xảy ra bộ đó, \(Pr(A)\). Chúng ta cũng biết một tích \(p\) của một tập con ngẫu nhiên của các số này. Điều chúng ta đang cố gắng tính toán là xác suất có điều kiện để bộ ẩn là \(A\) khi biết tích của một tập con ngẫu nhiên là \(p\). Hãy viết nó là \(Pr(A | p)\).

Làm thế nào để tính toán điều đó? Sử dụng định nghĩa của xác suất có điều kiện:
\(Pr(A | p) = Pr(A \cap p) / Pr(p) = Pr(A) \times Pr(p | A) / Pr(p)\)
Phép suy luận này được gọi là định lý Bayes.

Chúng ta đã biết \(Pr(A)\), vì vậy chúng ta chỉ cần biết \(Pr(p | A)\). Chúng ta có thể tính toán trước các giá trị này cho mọi \(A\). Chỉ cần thử mọi tập con có thể có của mỗi bộ số ẩn có thể, xem các tích trong mỗi trường hợp là gì và xây dựng một bảng lớn gồm tất cả các xác suất này. Có khoảng \(18564 \times 2^{12} \approx 76\) triệu tập con như vậy.

\(Pr(p)\) sau đó có thể được tính bằng tổng của \(Pr(A) \times Pr(p | A)\) trên tất cả các \(A\).

Giải pháp hoàn chỉnh

K lớn hơn 1, nhưng đó không phải là vấn đề: chúng ta lặp lại lập luận trên cho mỗi trong số K tích, điều chỉnh xác suất của các tổ hợp ẩn trong quá trình thực hiện.

Giải pháp đầy đủ là:

• Một số bước tính toán trước:
  • Tạo tất cả các tổ hợp có thể có của các số ẩn, bỏ qua thứ tự.
  • Tính xác suất ban đầu của mỗi bộ ẩn này.
  • Đối với mỗi bộ ẩn có thể, tìm tất cả các tích có thể có của các tập con và tính \(Pr(p | A)\). Lập chỉ mục các giá trị này theo \(p\) để dễ dàng tra cứu sau này.
• Đối với mỗi bộ ẩn:
  • Bắt đầu với phân phối xác suất ban đầu đã tính trước trên các bộ ẩn có thể.
  • Đọc từng tích \(p\) một, và điều chỉnh phân phối xác suất bằng cách sử dụng định lý Bayes và các xác suất có điều kiện \(Pr(p | A)\) đã tính trước.
  • In ra khả năng có xác suất cao nhất.

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