Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100 Interactive Hackable ✓
Statistics

이 문제는 인터랙티브 문제입니다.

게으른 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

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.