Phân tích

Tập dữ liệu nhỏ

Trong bài toán này, chúng ta quan tâm đến việc tính số tiền trung bình thu được từ việc làm đầy mọi cabin trên vòng quay quan sát. Do tính tuyến tính của kỳ vọng, điều này tương đương với việc cộng tổng số tiền kỳ vọng mà mỗi người trả. Vì số tiền một người trả không phụ thuộc vào thứ tự các cabin bị chiếm chỗ, chúng ta có thể biểu diễn trạng thái trống/đầy hiện tại của các cabin dưới dạng một mặt nạ bit (bitmask) và sử dụng quy hoạch động để giải quyết trường hợp nhỏ.

Gọi \(E(\text{mask})\) là số tiền kỳ vọng chúng ta kiếm được bắt đầu từ cấu hình được biểu diễn bởi \(\text{mask}\), trong đó 0 đại diện cho một cabin trống và 1 đại diện cho một cabin đã bị chiếm. Một người có xác suất \(1/N\) bắt đầu tại bất kỳ vị trí nào. Khi vị trí bắt đầu đó được cố định, chúng ta chỉ cần tìm số 0 đầu tiên theo sau nó (theo thứ tự vòng tròn), và đó là nơi người đó cuối cùng sẽ vào.

Chúng ta định nghĩa \(f(i)\) là chỉ số của cabin bị chiếm bởi một người bắt đầu tại vị trí \(i\). Tương tự, gọi \(c(i)\) là số tiền người này trả, theo mô tả bài toán. Khi đó chúng ta có công thức truy hồi sau:

\(E(\text{mask}) = \frac{1}{N} \cdot \sum_{i=0}^{N-1} (E(\text{mask} \mid (1 \ll f(i))) + c(i))\)

Phép toán bit ở đây chỉ đơn giản là đặt bit tương ứng với cabin mà người dùng đã chiếm. Trường hợp cơ sở là khi không còn vị trí trống nào, trong đó số tiền kỳ vọng là 0.

Có \(2^N\) trạng thái, mỗi trạng thái có thể được tính toán trong thời gian tuyến tính, vì vậy độ phức tạp thời gian của chúng ta là \(O(N \cdot 2^N)\). Điều này khá dễ dàng cho tập dữ liệu nhỏ, nhưng không may là nó quá chậm cho trường hợp lớn.

Tập dữ liệu lớn

Hãy phân tích bài toán từ cuối: một trong các cabin của chúng ta sẽ là cabin cuối cùng bị chiếm chỗ, vì vậy chúng ta có một vài trường hợp, mỗi trường hợp ứng với một cabin trống lúc ban đầu. Số tiền kỳ vọng chúng ta sẽ nhận được bằng tổng số tiền kỳ vọng chúng ta kiếm được trong mỗi trường hợp đó nhân với xác suất của trường hợp đó.

Lúc đầu, có vẻ như chúng ta không giảm được độ phức tạp của bài toán: thay vì chỉ phải tìm số tiền kỳ vọng cho toàn bộ quá trình, bây giờ chúng ta phải tìm cả số tiền kỳ vọng và xác suất cho nhiều trường hợp! Tuy nhiên, chúng ta có thể lặp lại mẹo trên. Giả sử cabin \(i\) là cabin cuối cùng bị chiếm chỗ. Hãy xem cabin nào sẽ bị chiếm ngay trước nó. Giả sử đó là cabin \(j\). Và đây là bước đột phá: ngay khi chúng ta cố định rằng các cabin \(i\) và \(j\) là hai cabin cuối cùng bị chiếm, vòng quay quan sát đã được tách thành hai phần độc lập không ảnh hưởng đến nhau: những cabin giữa \(i\) và \(j\), và những cabin giữa \(j\) và \(i\). Chúng không ảnh hưởng đến nhau vì \(i\) và \(j\) vẫn trống, và do đó không có người nào tiếp cận một phần của vòng quay lại kết thúc ở phần kia.

Cách tiếp cận chung của chúng ta sẽ là tính \(E(i, j)\), số tiền kỳ vọng chúng ta nhận được từ tất cả các cabin từ thứ \(i\) cho đến thứ \((j-1)\), không bao gồm chính cabin thứ \(j\) sẽ vẫn trống. Có thể có \(i > j\) vì chúng ta đang xử lý một bài toán vòng tròn, vì vậy hãy lưu ý điều này khi cài đặt. Về cơ bản, chúng ta bắt đầu tại \(i\) và đi quanh vòng tròn, dừng lại ngay trước \(j\).

Để tính kỳ vọng, chúng ta sẽ cần xác suất, vì vậy trước tiên hãy xem xét \(P(i, j)\), xác suất cabin thứ \(j\) sẽ vẫn trống trong khi chúng ta làm đầy tất cả các cabin từ khoảng \([i, j)\) giả sử mỗi người đến tiếp cận một cabin nào đó trong khoảng \([i, j]\) (lưu ý rằng \(j\) được bao gồm ở đây). Chúng ta có thể phát triển một công thức truy hồi để tính toán điều này.

Giả sử chúng ta biết rằng người cuối cùng vào cabin tại vị trí \((i + k)\). Điều này chia khoảng thành hai phần, với \(a\) ô trống ở bên trái, \(b\) ô trống ở bên phải, và thêm 1 ô trống nữa tại \((i+k)\).

Xác suất cabin \(j\) vẫn trống trong khi chúng ta làm đầy khoảng \([i, j)\) và cabin tại vị trí \((i+k)\) được làm đầy cuối cùng là \(P(i, j, k)\) và có thể được tính như sau:

\(P(i, j, k) = C(a+b, a) \cdot \left(\frac{k+1}{j-i+1}\right)^{a+1} \cdot \left(\frac{j-i-k}{j-i+1}\right)^b \cdot P(i, i+k) \cdot P(i+k+1, j)\)

Ở đây \(C(n, k)\) là hệ số nhị thức đại diện cho số cách chọn \(k\) đối tượng từ một tập hợp \(n\). Phương trình trên tương đương với việc chọn \(a\) người từ \((a+b)\) người để đi vào phía bên trái của không gian trống cuối cùng, và sau đó đảm bảo rằng \((a+1)\) người đi vào phía bên trái (bao gồm cả người làm đầy cabin \(i+k\)) và \(b\) người đi vào phía bên phải. Xác suất cabin \(i+k\) sẽ vẫn trống là \(P(i, i+k)\), và xác suất cabin \(j\) sẽ vẫn trống là \(P(i+k+1, j)\).

Điều này giả định rằng \((i+k)\) ban đầu trống, nếu không chúng ta định nghĩa \(P(i, j, k) = 0\).

Tất nhiên, chúng ta không thể thực sự cố định người cuối cùng, nhưng vì mọi cách để làm đầy khoảng đều có một người cuối cùng nào đó, chúng ta có thể tính xác suất cabin \(j\) sẽ vẫn trống bằng tổng của \(P(i, j, k)\) trên tất cả các vị trí cuối cùng \(k\) có thể:

\(P(i, j) = \sum_{k=0}^{j-i-1} P(i, j, k)\)

Đối với trường hợp cơ sở, chúng ta có \(P(i, j, k) = 1\) nếu khoảng \([i, j)\) không chứa cabin trống nào. Điều này cũng bao gồm trường hợp khoảng có kích thước 0. Đừng quên, chúng ta vẫn đang trong tình huống vòng tròn!

Tiếp theo là tính toán kỳ vọng! Chúng ta sẽ sử dụng cùng một mẹo chia tách xung quanh người cuối cùng. Số tiền kỳ vọng chúng ta nhận được trong khi làm đầy khoảng \([i, j)\) sao cho cabin được làm đầy cuối cùng ở vị trí \((i+k)\) là:

\(E(i, j, k) = E(i, i+k) + E(i+k+1, j) + N - k/2\)

Lấy tổng trên tất cả các \(k\) có thể để có được kỳ vọng, chúng ta được:

\(E(i, j) = \frac{\sum_{k=0}^{j-i-1} P(i, j, k) \cdot E(i, j, k)}{P(i, j)}\)

Cách phương trình đầu tiên hoạt động là kết hợp các kỳ vọng từ khoảng bên trái và khoảng bên phải, và sau đó chúng ta cần số lần bỏ qua kỳ vọng để xếp người cuối cùng. Có \((k+1)\) vị trí bắt đầu, tương ứng với 0 lần bỏ qua, 1 lần bỏ qua, ..., \(k\) lần bỏ qua. Mỗi vị trí này đều có khả năng như nhau, vì vậy kỳ vọng là \(N - \frac{1}{k+1}(0 + 1 + \dots + k) = N - k/2\).

Như trước, \(E(i, j, k) = 0\) nếu cabin tại vị trí \((i+k)\) đã bị chiếm.

Để tính câu trả lời cuối cùng, chúng ta sẽ lặp lại cùng một mẹo trong bước cuối cùng. Chúng ta thử tất cả các vị trí trống có thể làm cabin cuối cùng được làm đầy và tính số lần bỏ qua kỳ vọng. Nếu vị trí trống cuối cùng là \(i\), thì số tiền kỳ vọng chúng ta nhận được là:

\(P(i+1, i) \cdot (E(i+1, i) + (N+1)/2)\),

và tổng số tiền kỳ vọng chỉ là tổng của đại lượng này trên tất cả các vị trí trống ban đầu.

Thuật toán này là \(O(N^3)\), dễ dàng nằm trong giới hạn thời gian cho trường hợp lớn.

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