Đây là một bài toán tương tác.
Sam lười biếng và Sarah chăm chỉ được giao nhiệm vụ nghĩ ra hai phân phối xác suất thú vị trên tập hợp các xâu độ dài $n$ trên bảng chữ cái $\{H, T\}$. Sam lười biếng sẽ chỉ đơn giản tung đồng xu $n$ lần (mỗi mặt xuất hiện với xác suất $\frac{1}{2}$; tất cả các lần tung đồng xu đều độc lập) và viết ra "H" cho mỗi lần ngửa và "T" cho mỗi lần sấp. Bạn muốn giúp Sarah chăm chỉ dạy cho Sam lười biếng một bài học. Bạn được cho một số nguyên $t$. Hãy giúp Sarah nghĩ ra một phân phối $t$-gần với phân phối đều, đồng thời chứng minh một cách tương tác rằng bạn có thể phân biệt giữa phân phối của Sam lười biếng và Sarah chăm chỉ với quyền truy cập oracle có độ dài $t$.
Một cách hình thức, với một số nguyên $n$ nào đó, xét tập hợp $S = \{H, T\}^n$ có kích thước $2^n$, bao gồm tất cả các xâu độ dài $n$ có thể có trên bảng chữ cái gồm hai ký tự: "H" và "T". Một phân phối trên tập $S$ được định nghĩa là một mảng các số thực không âm $\{a_s\}_{s \in S}$ có độ dài $2^n$ được đánh chỉ số bởi các phần tử của $S$, sao cho tổng của chúng bằng $1$. Một trong những phân phối đơn giản nhất là phân phối đều, trong đó tất cả các $a_s$ đều bằng $2^{-n}$.
Đối với một cặp số $\varepsilon \in [0; +\infty)$ và $k \in \{0, 1, \dots, n\}$, ta nói rằng $\{a_s\}_{s \in S}$ là một phân phối $(\varepsilon, k)$-độc lập nếu, với mọi cách chọn $k$ chỉ số $1 \le i_1 < i_2 < \dots < i_k \le n$ và mọi tập con $T \subseteq \{H, T\}^k$ gồm các xâu độ dài $k$ trên bảng chữ cái $\{H, T\}$, điều sau đây luôn đúng: tổng của $a_s$ trên $2^{n-k}|T|$ xâu $s$ có dãy con $s[i_1]s[i_2]\dots s[i_k]$ thuộc $T$ sai khác so với $\frac{|T|}{2^k}$ không quá $\varepsilon$. Theo thuật ngữ xác suất, điều này có thể được biểu diễn như sau:
$$\forall 1 \le i_1 < i_2 < \dots < i_k \le n \quad \forall T \subseteq \{H, T\}^k \quad \frac{|T|}{2^k} - \varepsilon \le \mathbb{P}_{s \leftarrow \{a_s\}_{s \in S}} \{s[i_1]s[i_2]\dots s[i_k] \in T\} \le \frac{|T|}{2^k} + \varepsilon.$$
Về mặt trực giác, điều này có nghĩa là để phân biệt phân phối này với phân phối đều, bạn sẽ cần hoặc phân biệt được các xác suất có độ chênh lệch không vượt quá $\varepsilon$, hoặc nhìn vào nhiều hơn $k$ bit của các xâu được sinh ra bởi phân phối đó.
Phân phối $\{a_s\}_{s \in S}$ được gọi là $t$-gần với phân phối đều nếu nó là $(2^{-t}t, t)$-độc lập.
Trong định nghĩa về tính $(\varepsilon, k)$-độc lập, người ta ngầm hiểu rằng trước tiên bạn phải chọn $k$ chỉ số rồi sau đó mới nghiên cứu phân phối xác suất trên $k$ chỉ số đó. Trong mô hình truy cập oracle độ dài $k$, mọi thứ hoàn toàn khác. Một xâu ngẫu nhiên độ dài $n$ được sinh ra, và sau đó $k$ vòng theo định dạng sau được tiến hành: bạn gọi một số nguyên $i \in \{1, 2, \dots, n\}$, và để đáp lại, bạn sẽ được cho biết $s[i]$. Bạn có thể quyết định chỉ số nào sẽ gọi tiếp theo, có tính đến tất cả các câu hỏi đã hỏi trước đó và câu trả lời của chúng.
Để chứng minh rằng bạn có thể phân biệt các phân phối của Sam lười biếng và Sarah chăm chỉ, bạn sẽ cần, khi có quyền truy cập oracle độ dài $t$ vào $m$ xâu độ dài $n$ được lấy mẫu từ phân phối của họ (mỗi xâu được sinh độc lập và đồng đều từ phân phối của Sam lười biếng hoặc của Sarah chăm chỉ), kết luận cho từng xâu xem nó được lấy từ phân phối của ai, và đoán đúng ít nhất $0.75m - 2\sqrt{m}$ lần.
Giao thức tương tác
Dòng đầu tiên chứa một số nguyên $t$, biểu thị độ gần cần thiết với phân phối đều và độ dài của truy cập oracle ($1 \le t \le 5$).
Để đáp lại, hãy in ra một dòng chứa một số nguyên duy nhất $n$, biểu thị độ dài của các xâu mà bạn sẵn sàng cung cấp phân phối và bằng chứng tương tác về khả năng phân biệt ($t \le n \le 20$).
Ở dòng tiếp theo, hãy in ra một dòng gồm $2^n$ số nguyên $b_s$, xác định phân phối của bạn ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Dựa trên dữ liệu này, máy chấm sẽ chọn phân phối $\{a_s\}_{s \in S}$ theo quy tắc $a_s = b_s / \sum_{s \in S} b_s$. Các giá trị của $b_s$ phải được liệt kê theo thứ tự từ điển của các xâu $s$: ví dụ, với $n = 3$, các số phải được in theo thứ tự sau: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.
Tiếp theo, đọc một số nguyên $m$, biểu thị số lần kiểm tra tương tác ($1 \le m \le 10^4$). Sau đó, $m$ lần kiểm tra sẽ được đưa ra, cần được hoàn thành lần lượt từng cái một.
Vào đầu mỗi lần kiểm tra, máy chấm trước tiên sẽ chọn phân phối $\{a_s\}_{s \in S}$ từ Sam lười biếng hoặc Sarah chăm chỉ với xác suất $\frac{1}{2}$. Sau đó, máy chấm lấy mẫu một xâu ngẫu nhiên $s \sim \{a_s\}_{s \in S}$: bất kỳ xâu $s$ nào cũng có thể nhận được với xác suất $a_s$. Máy chấm sau đó cho bạn cơ hội hỏi không quá $t$ câu hỏi về các ký tự của xâu $s$. Để đặt câu hỏi, hãy in ra một dòng chứa một số nguyên $q \in \{1, 2, \dots, n\}$, biểu thị chỉ số của ký tự cần quan tâm. Sau đó, đọc ký tự "H" hoặc "T" là câu trả lời cho truy vấn. Sau khi hỏi từ $0$ đến $t$ câu hỏi, hãy in ra một dòng có tên "Sam" nếu bạn tin rằng $s$ được lấy từ phân phối của Sam lười biếng, hoặc "Sarah" nếu bạn tin rằng $s$ được lấy từ phân phối của Sarah chăm chỉ. Sau đó, lập tức chuyển sang lần kiểm tra tiếp theo cho đến khi bạn hoàn thành tất cả $m$ lần.
Các xâu có thể được in bằng chữ hoa hoặc chữ thường tùy ý.
Sau mỗi dòng in ra, đừng quên làm rỗng bộ đệm đầu ra (flush).
Ví dụ
Dữ liệu vào 1
2 3 T T T T T
Kết quả 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH