이 문제는 인터랙티브 문제입니다.
게으른 Sam과 부지런한 Sarah는 알파벳 $\{H, T\}$로 이루어진 길이 $n$인 문자열들의 집합 위에서 두 개의 흥미로운 확률 분포를 만들어야 하는 과제를 받았습니다. 게으른 Sam은 단순히 동전을 $n$번 던져서(각 면이 나올 확률은 $\frac{1}{2}$이며, 모든 동전 던지기는 서로 독립입니다) 앞면이 나올 때마다 "H"를, 뒷면이 나올 때마다 "T"를 적습니다. 여러분은 부지런한 Sarah를 도와 게으른 Sam에게 한 수 가르쳐 주고 싶습니다. 정수 $t$가 주어집니다. Sarah가 균등 분포에 $t$-가까운 분포를 만들도록 돕고, 동시에 길이 $t$의 오라클 접근(oracle access)을 통해 게으른 Sam의 분포와 부지런한 Sarah의 분포를 구별할 수 있음을 인터랙티브하게 증명하세요.
공식적으로, 어떤 정수 $n$에 대해 두 문자 "H"와 "T"로 이루어진 알파벳 상의 가능한 모든 길이 $n$인 문자열들로 구성된 크기 $2^n$의 집합 $S = \{H, T\}^n$을 생각해 봅시다. 집합 $S$ 위의 분포는 $S$의 원소로 인덱싱되는 길이 $2^n$의 음이 아닌 실수 배열 $\{a_s\}_{s \in 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의 분포를 구별할 수 있음을 증명하기 위해, 여러분은 두 사람의 분포에서 샘플링된 길이 $n$인 문자열 $m$개(각각 게으른 Sam 또는 부지런한 Sarah의 분포 중 하나에서 독립적이고 균등한 확률로 생성됨)에 대해 길이 $t$의 오라클 접근을 수행하여, 각 문자열이 누구의 분포에서 나왔는지 결론을 내리고 최소 $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