HILO

Lời giải: HILO

Hướng tiếp cận

Ta cần tính tổng số lần "HILO" xuất hiện trong xâu phản hồi, trên tất cả $N!$ hoán vị, với giá trị bí mật cố định $x+0.5$.

Thay vì đếm trực tiếp trên mỗi hoán vị, ta sử dụng kỳ vọng tuyến tính (linearity of expectation): tính kỳ vọng số lần "HILO" trên một hoán vị ngẫu nhiên, rồi nhân với $N!$.

Nhận xét quan trọng

1. Cấu trúc phản hồi: Mỗi hoán vị tạo ra một xâu phản hồi gồm các ký tự "HI" và "LO". Elsie bỏ qua các lần đoán thừa, nên xâu phản hồi thực chất chỉ chứa các giá trị "không bị loại" — những giá trị thu hẹp khoảng chứa $x+0.5$.

2. Chia bài toán: Có $x$ giá trị nhỏ hơn $x+0.5$ (cho "LO") và $N-x$ giá trị lớn hơn (cho "HI"). Xâu phản hồi là một hoán vị xen kẽ giữa "HI" và "LO" với các giá trị không bị loại.

3. Công thức DP: Định nghĩa $\text{dp}[b][j][k]$ = kỳ vọng số "HILO" khi:

   • $b=0$: phản hồi cuối là "LO"; $b=1$: phản hồi cuối là "HI"
   • $j$ = số giá trị chưa đoán phía dưới $x+0.5$
   • $k$ = số giá trị chưa đoán phía trên $x+0.5$

Thuật toán

Cách 1: DP $O(N^2)$

Dựa trên trạng thái $(b,j,k)$, ở mỗi bước giá trị tiếp theo (không bị loại) có xác suất $\frac{1}{j+k}$ là bất kỳ giá trị nào trong $j+k$ giá trị còn lại.

Quan hệ truy hồi:

• $\text{dp}[0][j][k]$: chọn giá trị dưới (chuyển sang trạng thái LO với $j-1$ giá trị dưới) hoặc giá trị trên (chuyển sang HI).
• $\text{dp}[1][j][k]=\text{dp}[0][j][k]+\frac{j}{j+k}$: nếu phản hồi trước là "HI" và bây giờ chọn giá trị dưới, ta có thêm một "HILO".

Tối ưu bằng prefix sum để đạt $O(N^2)$.

Cách 2: Công thức đóng $O(N)$

Sử dụng kỳ vọng tuyến tính và phân tích tổ hợp, ta có công thức đóng:

Với $0<x<N$: $$E[\#(\text{HILO})]=\frac{1}{2}(H_x+H_{N-x}-H_N+\frac{N-x}{N})$$

trong đó $H_k={\sum }_{i=1}^k\frac{1}{i}$ là số điều hòa (harmonic number) bậc $k$.

Với $x=0$ hoặc $x=N$: tất cả phản hồi đều cùng loại ("HI" hoặc "LO"), nên không có "HILO", kết quả là $0$.

Đáp án cuối cùng: $N!\times E[\#(\text{HILO})]mod({10}^9+7)$.

Kiểm tra với ví dụ

$N=4$, $x=2$: $H_2=\frac{3}{2}$, $H_4=\frac{25}{12}$.

$$E=\frac{1}{2}(\frac{3}{2}+\frac{3}{2}-\frac{25}{12}+\frac{2}{4})=\frac{1}{2}·\frac{17}{12}=\frac{17}{24}$$

Đáp án: $24\times \frac{17}{24}=17$. Đúng!

Độ phức tạp

• Thời gian: $O(N)$ (tính số điều hòa và giai thừa)
• Bộ nhớ: $O(N)$ (bảng nghịch đảo modular)