Hướng dẫn giải của HILO

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

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$ .
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.
Công thức DP: Định nghĩa $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:

$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).
$dp [1] [j] [k] = 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 [# (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 [# (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} \cdot \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)

Bình luận

Không có bình luận tại thời điểm này.