Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100 インタラクティブ ハック可能 ✓
統計

這是一道互動題。

懶惰的 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

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1215EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.