這是一道互動題。
懶惰的 Sam 和勤奮的 Sarah 被交派了一項任務:在字母表 $\{H, T\}$ 上長度為 $n$ 的字串集合中,構思出兩個有趣的機率分佈。懶惰的 Sam 只會單純地擲 $n$ 次硬幣(每一面出現的機率皆為 $\frac{1}{2}$;所有擲硬幣結果彼此獨立),並在每次出現正面時寫下 "H"、出現反面時寫下 "T"。你想幫助勤奮的 Sarah 給懶惰的 Sam 上一課。給定一個整數 $t$,請幫助 Sarah 設計一個與均勻分佈 $t$-接近的分佈,同時透過互動的方式證明:在長度為 $t$ 的神諭存取(oracle access)下,你可以區分出懶惰的 Sam 與勤奮的 Sarah 的分佈。
形式化地說,對於某個整數 $n$,考慮大小為 $2^n$ 的集合 $S = \{H, T\}^n$,它由兩個字元 "H" 與 "T" 的字母表所構成之所有可能長度為 $n$ 的字串所組成。集合 $S$ 上的一個分佈定義為一個長度為 $2^n$、由非負實數組成的陣列 $\{a_s\}_{s \in S}$,以 $S$ 的元素為索引,且其總和等於 $1$。最簡單的分佈之一是均勻分佈,其中所有的 $a_s$ 皆等於 $2^{-n}$。
對於一對數 $\varepsilon \in [0; +\infty)$ 與 $k \in \{0, 1, \dots, n\}$,若對於任意選擇的 $k$ 個索引 $1 \le i_1 < i_2 < \dots < i_k \le n$ 以及字母表 $\{H, T\}$ 上長度為 $k$ 的字串之任意子集 $T \subseteq \{H, T\}^k$,以下性質皆成立,則我們稱 $\{a_s\}_{s \in S}$ 是一個 $(\varepsilon, k)$-獨立分佈:在子序列 $s[i_1]s[i_2]\dots s[i_k]$ 屬於 $T$ 的那 $2^{n-k}|T|$ 個字串 $s$ 上,$a_s$ 的總和與 $\frac{|T|}{2^k}$ 的差值不超過 $\varepsilon$。用機率論的術語來說,這可以表示為:
$$\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.$$
直觀而言,這意味著若要將此分佈與均勻分佈區分開來,你要麼需要區分差值不超過 $\varepsilon$ 的機率,要麼需要檢視該分佈所產生的字串中超過 $k$ 個位元。
若分佈 $\{a_s\}_{s \in S}$ 是 $(2^{-t}t, t)$-獨立的,則稱其與均勻分佈是 $t$-接近的。
在 $(\varepsilon, k)$-獨立的定義中,隱含了你必須先選定 $k$ 個索引,然後才能研究這 $k$ 個索引上的機率分佈。然而在長度為 $k$ 的神諭存取模型中,情況截然不同。系統會先產生一個長度為 $n$ 的隨機字串,接著進行 $k$ 輪如下格式的互動:你指定一個整數 $i \in \{1, 2, \dots, n\}$,作為回應,你會得知 $s[i]$。你可以將先前問過的所有問題及其答案納入考量,來決定下一步要詢問哪個索引。
為了證明你能區分懶惰的 Sam 與勤奮的 Sarah 的分佈,你必須在擁有長度為 $t$ 的神諭存取權限下,針對從他們的分佈中抽樣出的 $m$ 個長度為 $n$ 的字串(每個字串皆獨立且等機率地從懶惰的 Sam 或勤奮的 Sarah 的分佈中產生),分別判斷每一個字串是取自誰的分佈,並且至少猜對 $0.75m - 2\sqrt{m}$ 次。
互動協定
第一行包含一個整數 $t$,代表與均勻分佈所需的接近程度以及神諭存取的長度($1 \le t \le 5$)。
作為回應,請輸出一行包含一個整數 $n$,代表你準備提供分佈及可區分性互動證明的字串長度($t \le n \le 20$)。
在下一行中,請輸出一行包含 $2^n$ 個整數 $b_s$,用以定義你的分佈($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$)。根據這些資料,裁判程式將依照規則 $a_s = b_s / \sum_{s \in S} b_s$ 選定分佈 $\{a_s\}_{s \in S}$。$b_s$ 的值必須按照字串 $s$ 的字典序排列:例如當 $n = 3$ 時,數字應按以下順序輸出:$b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$。
接著,請讀入一個整數 $m$,代表互動檢查的次數($1 \le m \le 10^4$)。隨後將依序進行 $m$ 次檢查,需逐一完成。
在每次檢查開始時,裁判程式會先以 $\frac{1}{2}$ 的機率選擇懶惰的 Sam 或勤奮的 Sarah 的分佈 $\{a_s\}_{s \in S}$。之後,裁判程式會抽樣一個隨機字串 $s \sim \{a_s\}_{s \in S}$:任何字串 $s$ 被抽出的機率為 $a_s$。接著裁判程式會給你機會對字串 $s$ 的字元提出不超過 $t$ 個問題。若要提問,請輸出一行包含一個整數 $q \in \{1, 2, \dots, n\}$,代表你感興趣的字元索引。之後,讀入字元 "H" 或 "T" 作為該詢問的回答。在提出 $0$ 到 $t$ 個問題之後,若你認為 $s$ 取自懶惰的 Sam 的分佈,請輸出一行名稱 "Sam";若你認為 $s$ 取自勤奮的 Sarah 的分佈,請輸出一行名稱 "Sarah"。在此之後,請立即進入下一次檢查,直到完成所有 $m$ 次檢查。
輸出的字串不區分大小寫。
在輸出每一行之後,請別忘了清空輸出緩衝區(flush)。
範例
範例輸入 1
2 3 T T T T T
範例輸出 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH