Phân tích

Gọi \(P(N,K)\) là xác suất phòng \(K\) có người ở khi biển HẾT PHÒNG được bật. Đây chính là đại lượng bài toán yêu cầu, ngoại trừ việc kết quả phải được xuất theo một định dạng đặc biệt; ta sẽ bàn đến điều đó sau.

Test Set nhỏ

Trước tiên, ta trình bày thuật toán cho Test Set nhỏ. Có \(N-1\) cách xếp gia đình đầu tiên, mỗi cách có xác suất \(1/(N-1)\). Giả sử ta giao cho họ hai phòng kề nhau \(i\) và \(i+1\). Nếu một trong hai phòng là \(K\) thì ta đã xong. Nếu không, \(K\) nằm trong đoạn \([1,i-1]\) hoặc đoạn \([i+2,N]\). Không mất tính tổng quát, xét trường hợp thứ nhất. Mọi điều xảy ra trong đoạn \([i+2,N]\) lúc này đều không liên quan, nên bài toán thu về việc tìm \(P(i-1,K)\). Biến đổi đại số cho ta truy hồi:

• \(P(1,1)=0\); và
• với \(1\le K\le N\), \(2\le N\),

trong đó \(\mu(\text{điều kiện})=1\) nếu điều kiện đúng và bằng 0 nếu điều kiện sai.

Tạm bỏ qua vấn đề độ chính xác và định dạng đầu ra đặc biệt, ta có thể dùng quy hoạch động để tính \(P(N,K)\) trong \(O(N^3)\), vẫn quá chậm ngay cả cho Test Set nhỏ. Tuy nhiên, nếu định nghĩa

truy hồi trở thành

Truy hồi này cho thuật toán \(O(N^2)\), đủ nhanh cho Test Set nhỏ.

Số học modulo

Trước khi tìm lời giải nhanh hơn cho Test Set lớn, ta xử lý định dạng đầu ra. Gọi \(M=10^9+7\) là số nguyên tố trong đề. Với đáp án hữu tỉ \(p/q\), ta cần in số nguyên duy nhất \(y\) sao cho \(0\le y<M\) và \(yq=p\pmod M\). Trong trường \((\mathbb Z_M,+,\times)\), ta chỉ cần tính

trong đó nghịch đảo modulo của \(q\) bằng \(q^{M-2}\) theo định lý Euler (hoặc định lý nhỏ Fermat). Lũy thừa modulo chỉ cần số phép toán theo logarithm trên các số nguyên nhỏ hơn \(M^2\). Thực tế, toàn bộ phép tính có thể thực hiện trong trường này, nên không cần số nguyên lớn hay số thực dấu phẩy động. Phép chia trong truy hồi luôn xác định vì ta không bao giờ chia cho một bội của \(M\).

Test Set lớn

Để giải Test Set lớn, ta dùng nhận xét sau.

Mệnh đề.

trong đó \(F(q)=1-P(q,1)\) là xác suất phòng ngoài cùng bên trái vẫn trống vào cuối ngày.

Chứng minh. Có thể chứng minh chặt chẽ bằng quy nạp, với các trường hợp cơ sở \(K\in\{1,N\}\), rồi dùng truy hồi trên. Tuy nhiên, có một chứng minh thanh thoát hơn.

Giả sử phòng \(K\) vẫn trống cho tới cuối ngày. Khi ấy về bản chất ta có hai khách sạn độc lập: một khách sạn gồm các phòng từ 1 đến \(K\), và khách sạn kia gồm các phòng từ \(K\) đến \(N\). Khách sạn thứ nhất nhận những vị khách được gán vào các cặp từ \((1,2)\) đến \((K-1,K)\); khách sạn thứ hai nhận những vị khách được gán vào các cặp từ \((K,K+1)\) đến \((N-1,N)\). Dễ thấy hai “luồng con” khách đi đến mỗi khách sạn cũng phân bố đều và độc lập. Khác biệt duy nhất giữa hai khách sạn như vậy với một khách sạn lớn là trong mô hình hai khách sạn, phòng \(K\) có thể bị dùng hai lần; nhưng vì ta đang xét trường hợp nó vẫn trống nên điều đó không xảy ra. Hai khách sạn độc lập, vì vậy ta chỉ cần nhân hai xác suất để phòng \(K\) — một phòng biên trong cả hai khách sạn — vẫn trống. \(\blacksquare\)

Khi \(K=1\), truy hồi của \(P(N,K)\) đơn giản hơn:

• \(P(1,1)=0\); và
• \(P(N,1)=\dfrac{1}{N-1}[1+S(N-2,1)]\) với \(N\ge2\).

Hai mảng một chiều có thể được điền đồng thời, nên có thuật toán \(O(N)\) để tính mọi giá trị \(P(N,1)\), từ đó có \(F(N)\). Sau bước tiền xử lý này, mỗi truy vấn \(P(N,K)\) trong đầu vào được trả lời trong thời gian hằng số.

Nhận xét cuối

Với bạn đọc tò mò, truy hồi trên cho công thức

Công thức cũng có ý nghĩa tổ hợp. Xét một hoán vị \(\pi\) của \(1,\ldots,N-1\), trong đó \(\pi_i\) biểu thị thời điểm ta thử gán cặp phòng \(i\) và \(i+1\) (nếu cả hai còn trống). Có thể thấy số hoán vị tạo ra một kết quả gán phòng nhất định tỉ lệ với xác suất của kết quả ấy. Khi đó \(F(q)\) bằng xác suất độ dài của dãy giảm ở đầu \(\pi\) là số chẵn. Ta tính xác suất này bằng nguyên lý bù trừ.

Vì mệnh đề trên là điểm mấu chốt của lời giải Test Set lớn, cũng đáng lưu ý rằng một số thí sinh tìm ra ý tưởng chỉ bằng cách quan sát bảng \(1-P(N,K)\) với các giá trị nhỏ của \(N\) và \(K\).

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - World Finals - Family Hotel, kho Google Coding Competitions (Apache-2.0).