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

Este es un problema interactivo.

A Sam el perezoso y a Sarah la diligente se les ha encomendado la tarea de idear dos distribuciones interesantes sobre el conjunto de cadenas de longitud $n$ sobre el alfabeto $\{H, T\}$. Sam el perezoso simplemente lanzará una moneda $n$ veces (cada cara aparece con una probabilidad de $\frac{1}{2}$; todos los lanzamientos de moneda son independientes) y escribirá "H" por cada cara y "T" por cada cruz. Quieres ayudar a Sarah la diligente a darle una lección a Sam el perezoso. Se te da un entero $t$. Ayuda a Sarah a idear una distribución que sea $t$-cercana a la distribución uniforme, mientras demuestras interactivamente que puedes distinguir entre las distribuciones de Sam el perezoso y Sarah la diligente con acceso de oráculo de longitud $t$.

Formalmente, para algún entero $n$, considera el conjunto $S = \{H, T\}^n$ de tamaño $2^n$, que consta de todas las cadenas posibles de longitud $n$ sobre el alfabeto de dos caracteres: "H" y "T". Una distribución sobre el conjunto $S$ se define como un arreglo de números reales no negativos $\{a_s\}_{s \in S}$ de longitud $2^n$ indexado por los elementos de $S$, tal que su suma es igual a $1$. Una de las distribuciones más simples es la distribución uniforme, donde todos los $a_s$ son iguales a $2^{-n}$.

Para un par de números $\varepsilon \in [0; +\infty)$ y $k \in \{0, 1, \dots, n\}$, decimos que $\{a_s\}_{s \in S}$ es una distribución $(\varepsilon, k)$-independiente si, para cualquier elección de $k$ índices $1 \le i_1 < i_2 < \dots < i_k \le n$ y cualquier subconjunto $T \subseteq \{H, T\}^k$ de cadenas de longitud $k$ sobre el alfabeto $\{H, T\}$, se cumple lo siguiente: la suma de $a_s$ sobre las $2^{n-k}|T|$ cadenas $s$ cuya subsecuencia $s[i_1]s[i_2]\dots s[i_k]$ pertenece a $T$ difiere de $\frac{|T|}{2^k}$ en a lo sumo $\varepsilon$. En términos probabilísticos, esto se puede expresar como:

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

Intuitivamente, esto significa que para distinguir la distribución de la uniforme, necesitarás distinguir probabilidades cuya diferencia no exceda $\varepsilon$, o bien observar más de $k$ bits de las cadenas producidas por la distribución.

La distribución $\{a_s\}_{s \in S}$ se llama $t$-cercana a la distribución uniforme si es $(2^{-t}t, t)$-independiente.

En la definición de $(\varepsilon, k)$-independencia, estaba implícito que primero debes elegir $k$ índices y solo entonces estudiar la distribución de probabilidad sobre esos $k$ índices. En el modelo de acceso de oráculo de longitud $k$, todo es diferente. Se genera una cadena aleatoria de longitud $n$ y luego se llevan a cabo $k$ rondas del siguiente formato: mencionas un entero $i \in \{1, 2, \dots, n\}$ y, como respuesta, se te dirá $s[i]$. Puedes decidir qué índice mencionar a continuación teniendo en cuenta todas las preguntas realizadas anteriormente y sus respuestas.

Para demostrar que puedes distinguir las distribuciones de Sam el perezoso y Sarah la diligente, deberás, teniendo acceso de oráculo de longitud $t$ a $m$ cadenas de longitud $n$ muestreadas de sus distribuciones (cada una generada de forma independiente y uniforme a partir de la distribución de Sam el perezoso o de la de Sarah la diligente), concluir para cada una de ellas de la distribución de quién fue tomada, y acertar al menos $0.75m - 2\sqrt{m}$ veces.

Protocolo de interacción

La primera línea contiene un entero $t$, que denota la cercanía requerida a una distribución uniforme y la longitud del acceso de oráculo ($1 \le t \le 5$).

En respuesta, imprime una línea con un solo entero $n$, que denota la longitud de las cadenas para las cuales estás listo para proporcionar la distribución y una prueba interactiva de distinguibilidad ($t \le n \le 20$).

En la siguiente línea, imprime una línea con $2^n$ enteros $b_s$, que definen tu distribución ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Con base en estos datos, el jurado elegirá la distribución $\{a_s\}_{s \in S}$ de acuerdo con la regla $a_s = b_s / \sum_{s \in S} b_s$. Los valores de $b_s$ deben listarse en el orden lexicográfico de las cadenas $s$: por ejemplo, para $n = 3$, los números deben imprimirse en el siguiente orden: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

A continuación, lee un entero $m$, que denota el número de comprobaciones interactivas ($1 \le m \le 10^4$). Después de esto, se presentarán las $m$ comprobaciones, que deberán completarse una tras otra.

Al comienzo de cada comprobación, el jurado elegirá primero la distribución $\{a_s\}_{s \in S}$ ya sea de Sam el perezoso o de Sarah la diligente con una probabilidad de $\frac{1}{2}$. Después de eso, el jurado muestrea una cadena aleatoria $s \sim \{a_s\}_{s \in S}$: cualquier cadena $s$ puede obtenerse con probabilidad $a_s$. Luego, el jurado te da la oportunidad de hacer no más de $t$ preguntas sobre los caracteres de la cadena $s$. Para hacer una pregunta, imprime una línea con un entero $q \in \{1, 2, \dots, n\}$, que denota el índice del carácter de interés. Después de eso, lee el carácter "H" o "T" que es la respuesta a la consulta. Después de hacer entre $0$ y $t$ preguntas, imprime una línea con el nombre "Sam" si crees que $s$ fue tomada de la distribución de Sam el perezoso, o "Sarah" si crees que $s$ fue tomada de la distribución de Sarah la diligente. Después de esto, pasa inmediatamente a la siguiente comprobación hasta que hayas completado las $m$.

Las cadenas se pueden imprimir en mayúsculas o minúsculas.

Después de cada línea impresa, no olvides vaciar el búfer de salida (flush).

Ejemplo

Entrada 1

2
3
T
T
T
T
T

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