Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Etkileşimli Hack'lenebilir ✓
İstatistikler

Это интерактивная задача.

Ленивому Сэму и прилежной Саре поручили придумать два интересных распределения вероятностей на множестве строк длины $n$ над алфавитом $\{H, T\}$. Ленивый Сэм просто подбросит монетку $n$ раз (каждая сторона выпадает с вероятностью $\frac{1}{2}$; все броски независимы) и запишет «H» для каждого орла и «T» для каждой решки. Вы хотите помочь прилежной Саре проучить ленивого Сэма. Вам дано целое число $t$. Помогите Саре придумать распределение, которое является $t$-близким к равномерному распределению, и одновременно интерактивно докажите, что вы можете различить распределения ленивого Сэма и прилежной Сары при помощи оракульного доступа длины $t$.

Формально, для некоторого целого числа $n$ рассмотрим множество $S = \{H, T\}^n$ размера $2^n$, состоящее из всех возможных строк длины $n$ над алфавитом из двух символов: «H» и «T». Распределение на множестве $S$ определяется как массив неотрицательных вещественных чисел $\{a_s\}_{s \in S}$ длины $2^n$, индексированный элементами множества $S$, сумма которых равна $1$. Одним из простейших распределений является равномерное распределение, в котором все $a_s$ равны $2^{-n}$.

Для пары чисел $\varepsilon \in [0; +\infty)$ и $k \in \{0, 1, \dots, n\}$ мы говорим, что $\{a_s\}_{s \in S}$ является $(\varepsilon, k)$-независимым распределением, если для любого набора из $k$ индексов $1 \le i_1 < i_2 < \dots < i_k \le n$ и любого подмножества $T \subseteq \{H, T\}^k$ строк длины $k$ над алфавитом $\{H, T\}$ выполняется следующее: сумма $a_s$ по $2^{n-k}|T|$ строкам $s$, у которых подпоследовательность $s[i_1]s[i_2]\dots s[i_k]$ принадлежит $T$, отличается от $\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}$ называется $t$-близким к равномерному распределению, если оно является $(2^{-t}t, t)$-независимым.

В определении $(\varepsilon, k)$-независимости подразумевалось, что вы должны сначала выбрать $k$ индексов и только затем изучать распределение вероятностей на этих $k$ индексах. В модели оракульного доступа длины $k$ всё иначе. Генерируется случайная строка длины $n$, а затем проводится $k$ раундов следующего вида: вы называете целое число $i \in \{1, 2, \dots, n\}$, а в ответ вам сообщают $s[i]$. Вы можете решать, какой индекс назвать следующим, учитывая все ранее заданные вопросы и ответы на них.

Чтобы доказать, что вы можете различить распределения ленивого Сэма и прилежной Сары, вам нужно, имея оракульный доступ длины $t$ к $m$ строкам длины $n$, сэмплированным из их распределений (каждая строка независимо и равновероятно сгенерирована либо из распределения ленивого Сэма, либо из распределения прилежной Сары), для каждой из них сделать вывод, из чьего распределения она была взята, и угадать правильно хотя бы $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\}_{s \in S}$ по правилу $a_s = b_s / \sum_{s \in S} b_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}$ выбирает распределение $\{a_s\}_{s \in S}$ либо ленивого Сэма, либо прилежной Сары. После этого жюри сэмплирует случайную строку $s \sim \{a_s\}_{s \in S}$: любая строка $s$ может быть получена с вероятностью $a_s$. Затем жюри даёт вам возможность задать не более $t$ вопросов о символах строки $s$. Чтобы задать вопрос, выведите строку с целым числом $q \in \{1, 2, \dots, n\}$, обозначающим индекс интересующего вас символа. После этого считайте символ «H» или «T», являющийся ответом на запрос. Задав от $0$ до $t$ вопросов, выведите строку с именем «Sam», если вы считаете, что строка $s$ была взята из распределения ленивого Сэма, или «Sarah», если вы считаете, что $s$ была взята из распределения прилежной Сары. После этого немедленно переходите к следующей проверке, пока не завершите все $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.