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