Test Set 1

Trong Test Set 1, mọi lõi đều phải thành công. Xác suất đó là tích

Ta sẽ chỉ ra rằng luôn nên dùng đơn vị huấn luyện cho lõi có xác suất thành công nhỏ nhất. Giả sử \(P_0<P_1\), có một lượng rất nhỏ \(Q\) để dùng, và ký hiệu \(P_2\cdots P_{N-1}\) là \(O\). Nếu tăng \(P_0\), tích trở thành \((P_0+Q)P_1O\); nếu tăng \(P_1\), tích là \(P_0(P_1+Q)O\). Sau khai triển, hai biểu thức chỉ khác ở hạng \(QP_1O\) so với \(QP_0O\). Vì \(P_0<P_1\), phương án tăng \(P_0\) tốt hơn.

Cần xử lý trường hợp tăng \(P_0\) khiến nó vượt \(P_1\). Ngay lúc đó, cùng lập luận cho biết ta nên chuyển sang tăng \(P_1\); bởi vậy khi hai giá trị bằng nhau, phải tăng chúng đồng thời. Tổng quát hơn, hãy tăng xác suất nhỏ nhất đến bằng xác suất nhỏ kế tiếp, rồi tăng đồng đều cả nhóm đến mức kế tiếp, và cứ thế. Không cần mô phỏng các lượng cực nhỏ: ta tính trực tiếp số đơn vị cần cho mỗi bước, chú ý trường hợp ngân sách không đủ hoàn thành cả bước. Đây là kỹ thuật “đổ nước”.

Test Set 2

Khi chỉ cần \(K\) lõi thành công, tăng xác suất nhỏ nhất không còn luôn tối ưu. Ví dụ \(N=2\), \(K=1\), \(U=0.01\) và hai xác suất là 0.99, 0.01. Dồn 0.01 cho lõi đầu làm nó đạt 1, bảo đảm thành công bất kể lõi kia; không có lý do cấp gì cho lõi thứ hai.

Ta mở rộng ý tưởng đầu tư chủ yếu vào một tập con và bỏ qua phần còn lại. Sắp các xác suất tăng dần và chọn một chỉ số \(i\). Bắt đầu nâng lõi \(i\) đến bằng lõi \(i+1\), rồi nâng hai lõi đó đến bằng lõi \(i+2\), v.v. Nếu mọi xác suất từ \(i\) trở đi đã đạt 1, có thể nâng lõi \(i-1\), rồi tiếp tục. Ta sẽ chứng minh có một \(i\) mà chiến lược này tối ưu; do đó thử mọi \(i\) và lấy đáp án lớn nhất. Với một \(i\) tối ưu, nhiều nhất một lõi “phía trước” \(i-1\) cần được nâng một phần: chỉ có nhiều nhất một \(i\) mà ngân sách đủ đưa \(i,i+1,\ldots,N\) lên 1 rồi còn dư để nâng \(i-1\) nhưng chưa tới 1; nếu không, ta chỉ việc chọn \(i-1\).

Trước tiên xét nên tăng lõi \(i\) hay \(i+1\). Gọi \(A_i\) và \(B_i\) lần lượt là xác suất có đúng \(K-2\) và \(K-1\) lõi thành công trong tất cả các lõi trừ \(i\) và \(i+1\). Gọi \(P_{i,d}\) là xác suất có ít nhất \(K\) lõi thành công nếu tăng xác suất của lõi \(i\) thêm \(d\), còn các lõi khác giữ nguyên. Thay định nghĩa vào và khử các hạng chung, ta được

Vì \((P_{i+1}-P_i)d\) dương, tăng lõi \(i+1\) tốt hơn tăng lõi \(i\) khi và chỉ khi \(B_i>A_i\). Điều này không phụ thuộc vào trị số ban đầu của hai xác suất, ngoài thứ tự tương đối của chúng. Vì vậy, sau khi tăng lõi \(i+1\) một chút, nếu vẫn có thể tăng nó thì không có lý do chuyển sang lõi \(i\).

Tiếp theo cần chỉ ra tồn tại \(i_0\) sao cho \(B_i>A_i\) khi và chỉ khi \(i\ge i_0\); đó là lõi bắt đầu được nâng. \(A_i\) và \(A_{i+1}\) đều phụ thuộc vào \(N-2\) xác suất, trong đó có \(N-3\) xác suất chung. Giữ cố định \(N-3\) lõi đó; gọi \(A(p)\) là xác suất có đúng \(K-1\) thành công khi thêm một lõi có xác suất \(p\), và định nghĩa \(B(p)\) tương tự theo số thành công tương ứng. Gọi \(U,V,W\) lần lượt là xác suất có đúng \(K-3,K-2,K-1\) thành công trong \(N-3\) lõi cố định. Khi ấy

\(B(p)-A(p)\) là hàm tuyến tính theo \(p\). Nếu nó đổi từ dương sang âm thì phải có \(B(0)-A(0)>0\) và \(B(1)-A(1)<0\), kéo theo \(W>V\) và \(V<U\). Điều này là không thể: phân phối số lần thành công trong một tập phép thử Bernoulli độc lập là đơn đỉnh/log-concave, nên không thể có cực tiểu cục bộ tại \(K-2\). Do đó dấu chỉ đổi theo một ngưỡng, chứng minh dạng hậu tố ở trên.

Sau khi thử từng \(i\), ta tính xác suất có ít nhất \(K\) thành công bằng quy hoạch động tương tự bài Red Tape Committee. Đặt dp[j] là xác suất đúng \(j\) lõi trong số đã xét thành công. Với lõi có xác suất \(p\):

new[j] = dp[j] * (1 - p) + dp[j - 1] * p.

Tổng dp[K] + ... + dp[N] là giá trị của phương án. Có \(O(N)\) chỉ số và mỗi lần tính DP mất \(O(N^2)\), nên cách cài đặt trực tiếp là \(O(N^3)\), đủ với \(N\le50\).

Khó chứng minh phương pháp này dưới áp lực cuộc thi, nhưng có thể khám phá nó bằng mô phỏng vét cạn: chia ngân sách thành các lượng tử nhỏ, thử mọi cách phân chia cho một số ít lõi và quan sát phương án tốt nhất. Cũng có thể tìm đáp án đúng bằng những phương pháp số như gradient descent.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1C, bài Core Training; kho Google Coding Competitions (Apache-2.0).