Phân tích: Falling Diamonds

Đây là một bài toán khá lắt léo. Việc giải quyết được bộ test nhỏ thường tạo ra sự khác biệt giữa việc được đi tiếp hay không - cụ thể, giải được toàn bộ bài này là đủ để thăng hạng; cũng như giải được bộ test nhỏ của bài này và bộ test lớn của bài Osmos.

Bộ test nhỏ (Small case)

Đối với bộ test nhỏ, chúng ta chỉ có tối đa 20 viên kim cương trong mỗi bộ test. Lưu ý rằng mỗi viên kim cương sẽ thực hiện một hành động không xác định (ngẫu nhiên) tối đa một lần, khi nó rơi trúng đỉnh của một viên kim cương khác (khi đó nó có thể trượt theo một trong hai hướng). Điều này có nghĩa là chúng ta sẽ có tối đa \(2^{20}\) trường hợp khác nhau có thể xảy ra khi các viên kim cương rơi, vì vậy chúng ta có thể liệt kê tất cả chúng (lưu ý rằng thực tế có ít đường đi khả thi hơn - ví dụ: viên thứ nhất, thứ năm và thứ sáu sẽ không bao giờ có sự lựa chọn).

Việc này thực sự hơi khó cài đặt, vì trong mỗi nhánh, chúng ta phải theo dõi xác suất đạt được nhánh đó — nó không chỉ phụ thuộc vào số lượng kim cương chúng ta đã xử lý cho đến nay, mà còn phụ thuộc vào việc có bao nhiêu viên kim cương đã có sự lựa chọn cho đến nay. Sau khi thực hiện xong, chúng ta cần tìm xem trong bao nhiêu phương án thì vị trí chúng ta quan tâm có kim cương và cộng tất cả xác suất đó lại. Tất cả những điều này không dễ để làm đúng, nhưng hoàn toàn có thể thực hiện được.

Bộ test lớn (Large case)

Đối với bộ test lớn, chúng ta cần thông minh hơn — mô phỏng tất cả các phương án rõ ràng không phải là lựa chọn cho \(10^6\) viên kim cương. Chúng ta sẽ bắt đầu với quan sát sau:

Thật vậy, hãy lưu ý rằng một viên kim cương trượt sang một bên không làm thay đổi lớp mà nó thuộc về, vì nó luôn bắt đầu trượt ở một vị trí \((0, 2k)\), và vị trí \((0, 2k)\) luôn là vị trí cuối cùng trong một lớp được lấp đầy.

Do đó, khi \(N\) viên kim cương rơi, sự không chắc chắn duy nhất về hình dạng của chúng nằm ở lớp cuối cùng, và đây là những gì chúng ta phải tính toán. Nếu vị trí chúng ta đang xem xét không nằm trong lớp này, chúng ta có thể trả lời ngay lập tức (xác suất là 1 nếu lớp đó đã đầy, và 0 nếu lớp đó chưa bắt đầu). Vì vậy, chúng ta chỉ cần tính toán xác suất trong lớp cuối cùng.

Cách tiếp cận Quy hoạch động (Dynamic Programming)

Trước tiên, hãy ước tính lớp cuối cùng có thể lớn như thế nào. Nếu chúng ta có tối đa một triệu viên kim cương, người ta có thể tính toán rằng sẽ có không quá 710 lớp. Khi các viên kim cương rơi, trạng thái của lớp có thể được mô tả bằng hai con số — có bao nhiêu viên kim cương ở bên trái tâm (với \(X\) âm) và bao nhiêu viên ở bên phải (chúng ta giả định ở đây rằng không có đủ kim cương để lấp đầy lớp này, vì vậy vị trí trên cùng với \(X = 0\) sẽ để trống). Điều này có nghĩa là khi các viên kim cương rơi vào lớp cuối cùng, có khoảng 500.000 trạng thái khác nhau để xem xét.

Một cách tiếp cận cho bài toán này là quy hoạch động. Đối với mỗi trạng thái có thể có của lớp cuối cùng, chúng ta tính xác suất đạt được trạng thái này khi số lượng kim cương thích hợp đã rơi vào lớp đó (mỗi trạng thái xác định duy nhất số lượng kim cương ở mỗi bên).

Cách tiếp cận Công thức (Formulaic approach)

Người ta cũng có thể nhận thấy rằng điều quan trọng là có bao nhiêu viên kim cương trong số những viên chạm vào đỉnh quyết định đi sang trái, và bao nhiêu viên đi sang phải. Cụ thể viên kim cương nào đi hướng nào không quan trọng đối với trạng thái cuối cùng. Do đó, chúng ta có thể tính trước các hệ số nhị thức (hoặc chính xác hơn là các hệ số nhị thức chia cho \(2^D\), trong đó \(D\) là số lượng kim cương rơi vào lớp cuối cùng), và — một khi chúng ta biết mình đang xem lớp nào — cộng các phương án dẫn đến việc một viên kim cương rơi vào đúng vị trí cần tìm.

Cụ thể, giả sử lớp cuối cùng cần \(M\) viên kim cương để lấp đầy mỗi bên (không tính đỉnh trên cùng), và chúng ta có \(K\) viên kim cương rơi vào lớp này. Vị trí \((X, Y)\) cần \(Y+1\) viên kim cương ở phía của nó để được lấp đầy. Xác suất là tổng của \(\binom{K}{i} 0.5^K\) cho các giá trị \(i\) thỏa mãn điều kiện vị trí \((X, Y)\) được lấp đầy, có tính đến trường hợp một bên đã đầy \(M\) viên và các viên còn lại buộc phải rơi vào bên kia.

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