Phân tích

Bối cảnh của bài toán này chắc chắn là xác suất rời rạc. Theo định nghĩa, không gian mẫu bao gồm \(N^T\) kết quả có khả năng xảy ra như nhau. Với các giới hạn của chúng ta, con số này có thể lớn tới \(10^{450}\). Rõ ràng, một cách tiếp cận ngây thơ là không khả thi.

Nhưng chúng ta hãy thực hiện một bài tập nhỏ về xác suất. Định nghĩa biến ngẫu nhiên \(X_i\) là số lượng cuộc thi vào ngày thứ \(i\), đại lượng chúng ta muốn tính là trung bình của \(X_i^2\), tức là kỳ vọng \(E(\sum X_i^2)\). Theo tính tuyến tính của kỳ vọng, ta có:

Vì vậy, hãy tập trung vào việc tính toán biến cho một ngày cố định tại thời điểm này. Chọn bất kỳ \(i\) nào, và đặt \(X := X_i\). Hãy định nghĩa thêm các biến ngẫu nhiên. Định nghĩa \(Y_j\) là biến chỉ thị (indicator) cho việc giải đấu thứ \(j\) có vòng thi vào ngày thứ \(i\) hay không. Rõ ràng, \(X = \sum_j Y_j\). Do đó,

Chúng ta quan sát thấy rằng mỗi số hạng trong biểu thức cuối cùng đều dễ tính toán. Vì là các biến ngẫu nhiên chỉ thị, các \(Y\) nhận giá trị 0 hoặc 1. Vì vậy:

• \(Y_j^2\) luôn có cùng giá trị với \(Y_j\), và kỳ vọng của nó chính là xác suất \(Y_j\) bằng 1, tức là giải đấu \(j\) có một vòng thi vào ngày \(i\).
• \(Y_j Y_k\) bằng 1 khi và chỉ khi cả \(Y_j\) và \(Y_k\) đều bằng 1. Kỳ vọng là xác suất cả giải đấu thứ \(j\) và thứ \(k\) đều có một vòng thi vào ngày \(i\).

Giả sử dữ liệu cho giải đấu \(j\), tức là mẫu các vòng thi là \(d_1=1, d_2, \dots, d_m\). Ký hiệu \(D(i, j)\) là số lượng các giá trị \(d\) của giải đấu \(j\) sao cho \(d \le i\). Có \(N\) lựa chọn cho ngày bắt đầu của một giải đấu cụ thể. Dễ dàng thấy rằng xác suất đầu tiên ở trên là \(D(i, j) / N\); trong khi xác suất thứ hai là \(D(i, j) D(i, k) / N^2\).

Cho đến nay, chúng ta đã giải quyết vấn đề chỉ cho một ngày \(i\) duy nhất. Chúng ta cần làm điều này cho mọi \(i\). Có \(10^9\) ngày như vậy. Nhưng lưu ý rằng, miễn là không có dữ liệu đầu vào nào mà \(d_t = i\), thì \(D(i-1, j) = D(i, j)\) cho mọi \(j\). Điều này có nghĩa là kỳ vọng cho ngày thứ \(i\) giống như kỳ vọng cho ngày thứ \((i-1)\). Có tối đa \(T \times \max(m) \le 2500\) giá trị \(d\) như vậy trong dữ liệu vào, vì vậy chúng ta cần tính toán \((*)\) cho tối đa 2500 ngày. Đối với bài toán của chúng ta, chỉ cần nhận ra rằng không có \(d > 10000\). Vì vậy, tất cả các kỳ vọng sau ngày thứ 10000 đều giống nhau. Chúng ta có thể thực hiện tính toán cho 10000 ngày đầu tiên, và đối với phần còn lại, chỉ cần một phép nhân đơn giản.

Vấn đề cuối cùng là nhu cầu về số nguyên lớn. Thoạt nhìn, chúng ta có thể có cả tử số và mẫu số lớn tới \(10^{450}\). Nhưng đó không phải là sự thật. Chỉ cần quan sát câu trả lời ở trên, đó là tổng của các giá trị \(D(i, j) / N\) và \(D(i, j) D(i, k) / N^2\) khác nhau. Chúng ta thực sự đã chứng minh rằng mẫu số không bao giờ lớn hơn \(N^2\). Việc cài đặt cẩn thận với số nguyên 64-bit là đủ tốt.

Để tăng tốc hơn nữa: Công thức trong \((*)\) liên quan đến việc tính toán \(O(T^2)\) số hạng. Nhưng nếu chúng ta thực hiện từ ngày 1, giữ \(D(i, j)\) cho mỗi \(j\) và thêm hai biến nữa — \(S_1\) cho tổng của tất cả các \(D(i, j)\), và \(S_2\) cho tổng của các \(D(i, j)^2\), thì chúng ta chỉ cần thời gian cập nhật hằng số khi thấy một giá trị \(d\) đầu vào, và cũng là thời gian tính toán hằng số cho mỗi ngày chúng ta muốn tính \((*)\).

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