Universal Cup Judging System

Universal Cup

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

Il s'agit d'un problème interactif.

Sam le paresseux et Sarah la diligente ont été chargés d'imaginer deux distributions de probabilité intéressantes sur l'ensemble des chaînes de longueur $n$ sur l'alphabet $\{H, T\}$. Sam le paresseux se contentera de lancer une pièce $n$ fois (chaque face apparaissant avec une probabilité de $\frac{1}{2}$ ; tous les lancers sont indépendants) et d'écrire « H » pour chaque face et « T » pour chaque pile. Vous voulez aider Sarah la diligente à donner une leçon à Sam le paresseux. On vous donne un entier $t$. Aidez Sarah à trouver une distribution qui est $t$-proche de la distribution uniforme, tout en prouvant de manière interactive que vous pouvez distinguer les distributions de Sam le paresseux et de Sarah la diligente avec un accès oracle de longueur $t$.

Formellement, pour un certain entier $n$, considérons l'ensemble $S = \{H, T\}^n$ de taille $2^n$, constitué de toutes les chaînes possibles de longueur $n$ sur l'alphabet à deux caractères : « H » et « T ». Une distribution sur l'ensemble $S$ est définie comme un tableau de nombres réels positifs ou nuls $\{a_s\}_{s \in S}$ de longueur $2^n$ indexé par les éléments de $S$, tel que leur somme soit égale à $1$. L'une des distributions les plus simples est la distribution uniforme, où tous les $a_s$ sont égaux à $2^{-n}$.

Pour un couple de nombres $\varepsilon \in [0; +\infty)$ et $k \in \{0, 1, \dots, n\}$, on dit que $\{a_s\}_{s \in S}$ est une distribution $(\varepsilon, k)$-indépendante si, pour tout choix de $k$ indices $1 \le i_1 < i_2 < \dots < i_k \le n$ et tout sous-ensemble $T \subseteq \{H, T\}^k$ de chaînes de longueur $k$ sur l'alphabet $\{H, T\}$, la propriété suivante est vérifiée : la somme des $a_s$ sur les $2^{n-k}|T|$ chaînes $s$ dont la sous-séquence $s[i_1]s[i_2]\dots s[i_k]$ appartient à $T$ diffère de $\frac{|T|}{2^k}$ d'au plus $\varepsilon$. En termes probabilistes, cela peut s'exprimer par :

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

Intuitivement, cela signifie que pour distinguer la distribution de la distribution uniforme, vous devrez soit distinguer des probabilités dont la différence n'excède pas $\varepsilon$, soit examiner plus de $k$ bits des chaînes produites par la distribution.

La distribution $\{a_s\}_{s \in S}$ est dite $t$-proche de la distribution uniforme si elle est $(2^{-t}t, t)$-indépendante.

Dans la définition de la $(\varepsilon, k)$-indépendance, il était sous-entendu que vous deviez d'abord choisir $k$ indices et seulement ensuite étudier la distribution de probabilité sur ces $k$ indices. Dans le modèle d'accès oracle de longueur $k$, tout est différent. Une chaîne aléatoire de longueur $n$ est générée, puis $k$ tours du format suivant sont effectués : vous annoncez un entier $i \in \{1, 2, \dots, n\}$ et, en réponse, on vous indique $s[i]$. Vous pouvez décider quel indice appeler ensuite en tenant compte de toutes les questions posées précédemment et de leurs réponses.

Pour prouver que vous pouvez distinguer les distributions de Sam le paresseux et de Sarah la diligente, vous devrez, en disposant d'un accès oracle de longueur $t$ à $m$ chaînes de longueur $n$ échantillonnées à partir de leurs distributions (chacune générée indépendamment et uniformément à partir de la distribution de Sam le paresseux ou de celle de Sarah la diligente), conclure pour chacune d'elles de quelle distribution elle a été tirée, et deviner correctement au moins $0.75m - 2\sqrt{m}$ fois.

Protocole d'interaction

La première ligne contient un entier $t$, désignant la proximité requise par rapport à une distribution uniforme et la longueur de l'accès oracle ($1 \le t \le 5$).

En réponse, affichez une ligne contenant un seul entier $n$, désignant la longueur des chaînes pour lesquelles vous êtes prêt à fournir la distribution et une preuve interactive de distinguabilité ($t \le n \le 20$).

Sur la ligne suivante, affichez une ligne contenant $2^n$ entiers $b_s$, définissant votre distribution ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Sur la base de ces données, le jury choisira la distribution $\{a_s\}_{s \in S}$ selon la règle $a_s = b_s / \sum_{s \in S} b_s$. Les valeurs de $b_s$ doivent être énumérées dans l'ordre lexicographique des chaînes $s$ : par exemple, pour $n = 3$, les nombres doivent être affichés dans l'ordre suivant : $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Ensuite, lisez un entier $m$, désignant le nombre de vérifications interactives ($1 \le m \le 10^4$). Après cela, les $m$ vérifications seront présentées et devront être effectuées l'une après l'autre.

Au début de chaque vérification, le jury choisira d'abord la distribution $\{a_s\}_{s \in S}$ soit de Sam le paresseux, soit de Sarah la diligente avec une probabilité de $\frac{1}{2}$. Après cela, le jury échantillonne une chaîne aléatoire $s \sim \{a_s\}_{s \in S}$ : toute chaîne $s$ peut être obtenue avec la probabilité $a_s$. Le jury vous donne alors la possibilité de poser au plus $t$ questions sur les caractères de la chaîne $s$. Pour poser une question, affichez une ligne avec un entier $q \in \{1, 2, \dots, n\}$, désignant l'indice du caractère qui vous intéresse. Ensuite, lisez le caractère « H » ou « T » qui est la réponse à la requête. Après avoir posé entre $0$ et $t$ questions, affichez une ligne avec le nom « Sam » si vous pensez que $s$ a été tirée de la distribution de Sam le paresseux, ou « Sarah » si vous pensez que $s$ a été tirée de la distribution de Sarah la diligente. Passez ensuite immédiatement à la vérification suivante jusqu'à ce que vous ayez terminé les $m$ vérifications.

Les chaînes peuvent être affichées sans distinction de casse.

Après chaque ligne affichée, n'oubliez pas de vider le tampon de sortie (flush).

Exemple

Entrée 1

2
3
T
T
T
T
T

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