Universal Cup Judging System

Universal Cup

时间限制: 1.0 s 内存限制: 1024 MB 总分: 100 交互 可 Hack ✓
统计

Dies ist ein interaktives Problem.

Der faule Sam und die fleißige Sarah haben die Aufgabe erhalten, sich zwei interessante Wahrscheinlichkeitsverteilungen über der Menge der Zeichenketten der Länge $n$ über dem Alphabet $\{H, T\}$ auszudenken. Der faule Sam wirft einfach $n$-mal eine Münze (wobei jede Seite mit einer Wahrscheinlichkeit von $\frac{1}{2}$ erscheint; alle Münzwürfe sind unabhängig) und notiert „H“ für Kopf und „T“ für Zahl. Du möchtest der fleißigen Sarah helfen, dem faulen Sam eine Lektion zu erteilen. Dir ist eine ganze Zahl $t$ gegeben. Hilf Sarah, eine Verteilung zu finden, die $t$-nah an der Gleichverteilung liegt, während du interaktiv beweist, dass du mit Orakelzugriff der Länge $t$ zwischen den Verteilungen des faulen Sam und der fleißigen Sarah unterscheiden kannst.

Formal betrachten wir für eine ganze Zahl $n$ die Menge $S = \{H, T\}^n$ der Größe $2^n$, die aus allen möglichen Zeichenketten der Länge $n$ über dem Alphabet aus den zwei Zeichen „H“ und „T“ besteht. Eine Verteilung über der Menge $S$ ist definiert als ein Array nichtnegativer reeller Zahlen $\{a_s\}_{s \in S}$ der Länge $2^n$, indiziert durch die Elemente von $S$, sodass deren Summe gleich $1$ ist. Eine der einfachsten Verteilungen ist die Gleichverteilung, bei der alle $a_s$ gleich $2^{-n}$ sind.

Für ein Zahlenpaar $\varepsilon \in [0; +\infty)$ und $k \in \{0, 1, \dots, n\}$ sagen wir, dass $\{a_s\}_{s \in S}$ eine $(\varepsilon, k)$-unabhängige Verteilung ist, wenn für jede Wahl von $k$ Indizes $1 \le i_1 < i_2 < \dots < i_k \le n$ und jede Teilmenge $T \subseteq \{H, T\}^k$ von Zeichenketten der Länge $k$ über dem Alphabet $\{H, T\}$ Folgendes gilt: Die Summe der $a_s$ über die $2^{n-k}|T|$ Zeichenketten $s$, deren Teilfolge $s[i_1]s[i_2]\dots s[i_k]$ zu $T$ gehört, weicht von $\frac{|T|}{2^k}$ um höchstens $\varepsilon$ ab. In wahrscheinlichkeitstheoretischen Begriffen lässt sich dies ausdrücken als:

$$\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.$$

Intuitiv bedeutet dies: Um die Verteilung von der Gleichverteilung zu unterscheiden, musst du entweder Wahrscheinlichkeiten unterscheiden, deren Differenz $\varepsilon$ nicht überschreitet, oder mehr als $k$ Bits der von der Verteilung erzeugten Zeichenketten betrachten.

Die Verteilung $\{a_s\}_{s \in S}$ heißt $t$-nah an der Gleichverteilung, wenn sie $(2^{-t}t, t)$-unabhängig ist.

In der Definition der $(\varepsilon, k)$-Unabhängigkeit war impliziert, dass man zuerst $k$ Indizes wählen muss und erst dann die Wahrscheinlichkeitsverteilung über diesen $k$ Indizes untersuchen kann. Im Modell des Orakelzugriffs der Länge $k$ ist alles anders. Es wird eine zufällige Zeichenkette der Länge $n$ erzeugt, und anschließend werden $k$ Runden des folgenden Formats durchgeführt: Du nennst eine ganze Zahl $i \in \{1, 2, \dots, n\}$, und als Antwort wird dir $s[i]$ mitgeteilt. Du kannst unter Berücksichtigung aller zuvor gestellten Fragen und ihrer Antworten entscheiden, welchen Index du als Nächstes abfragst.

Um zu beweisen, dass du die Verteilungen des faulen Sam und der fleißigen Sarah unterscheiden kannst, musst du bei einem Orakelzugriff der Länge $t$ auf $m$ Zeichenketten der Länge $n$, die aus ihren Verteilungen gezogen wurden (jede unabhängig und gleichverteilt entweder aus der Verteilung des faulen Sam oder der fleißigen Sarah erzeugt), für jede von ihnen entscheiden, aus wessen Verteilung sie stammt, und dabei mindestens $0.75m - 2\sqrt{m}$ Mal richtig liegen.

Interaktionsprotokoll

Die erste Zeile enthält eine ganze Zahl $t$, welche die geforderte Nähe zu einer Gleichverteilung sowie die Länge des Orakelzugriffs angibt ($1 \le t \le 5$).

Gib als Antwort eine Zeile mit einer einzigen ganzen Zahl $n$ aus, welche die Länge der Zeichenketten angibt, für die du bereit bist, die Verteilung und einen interaktiven Beweis der Unterscheidbarkeit anzugeben ($t \le n \le 20$).

Gib in der nächsten Zeile $2^n$ ganze Zahlen $b_s$ aus, die deine Verteilung definieren ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Auf Basis dieser Daten wählt die Jury die Verteilung $\{a_s\}_{s \in S}$ gemäß der Regel $a_s = b_s / \sum_{s \in S} b_s$. Die Werte von $b_s$ müssen in lexikographischer Reihenfolge der Zeichenketten $s$ angegeben werden: Für $n = 3$ müssen die Zahlen beispielsweise in der folgenden Reihenfolge ausgegeben werden: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Lies als Nächstes eine ganze Zahl $m$ ein, welche die Anzahl der interaktiven Überprüfungen angibt ($1 \le m \le 10^4$). Daraufhin werden die $m$ Überprüfungen präsentiert, die nacheinander absolviert werden müssen.

Zu Beginn jeder Überprüfung wählt die Jury zunächst mit einer Wahrscheinlichkeit von $\frac{1}{2}$ entweder die Verteilung $\{a_s\}_{s \in S}$ des faulen Sam oder die der fleißigen Sarah. Danach zieht die Jury eine zufällige Zeichenkette $s \sim \{a_s\}_{s \in S}$: Jede Zeichenkette $s$ wird mit Wahrscheinlichkeit $a_s$ erhalten. Die Jury gibt dir dann die Möglichkeit, höchstens $t$ Fragen zu den Zeichen der Zeichenkette $s$ zu stellen. Um eine Frage zu stellen, gib eine Zeile mit einer ganzen Zahl $q \in \{1, 2, \dots, n\}$ aus, die den Index des gewünschten Zeichens bezeichnet. Lies danach das Zeichen „H“ oder „T“ ein, das die Antwort auf die Anfrage darstellt. Nachdem du zwischen $0$ und $t$ Fragen gestellt hast, gib eine Zeile mit dem Namen „Sam“ aus, wenn du glaubst, dass $s$ aus der Verteilung des faulen Sam stammt, oder „Sarah“, wenn du glaubst, dass $s$ aus der Verteilung der fleißigen Sarah stammt. Gehe danach sofort zur nächsten Überprüfung über, bis du alle $m$ abgeschlossen hast.

Zeichenketten können in beliebiger Groß-/Kleinschreibung ausgegeben werden.

Vergiss nicht, nach jeder ausgegebenen Zeile den Ausgabepuffer zu leeren (flush).

Beispiel

Eingabe 1

2
3
T
T
T
T
T

Ausgabe 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.