Questo è un problema interattivo.
Al pigro Sam e alla diligente Sarah è stato assegnato il compito di ideare due distribuzioni interessanti sull'insieme delle stringhe di lunghezza $n$ sull'alfabeto $\{H, T\}$. Il pigro Sam si limiterà a lanciare una moneta $n$ volte (con ciascuna faccia che esce con probabilità $\frac{1}{2}$; tutti i lanci sono indipendenti) e a scrivere "H" per ogni testa e "T" per ogni croce. Vuoi aiutare la diligente Sarah a dare una lezione al pigro Sam. Ti viene dato un intero $t$. Aiuta Sarah a ideare una distribuzione che sia $t$-vicina alla distribuzione uniforme, dimostrando al contempo in modo interattivo che puoi distinguere tra le distribuzioni del pigro Sam e della diligente Sarah con un accesso all'oracolo di lunghezza $t$.
Formalmente, per un certo intero $n$, considera l'insieme $S = \{H, T\}^n$ di dimensione $2^n$, costituito da tutte le possibili stringhe di lunghezza $n$ sull'alfabeto di due caratteri: "H" e "T". Una distribuzione sull'insieme $S$ è definita come un array di numeri reali non negativi $\{a_s\}_{s \in S}$ di lunghezza $2^n$ indicizzato dagli elementi di $S$, tale che la loro somma sia uguale a $1$. Una delle distribuzioni più semplici è la distribuzione uniforme, in cui tutti gli $a_s$ sono uguali a $2^{-n}$.
Per una coppia di numeri $\varepsilon \in [0; +\infty)$ e $k \in \{0, 1, \dots, n\}$, diciamo che $\{a_s\}_{s \in S}$ è una distribuzione $(\varepsilon, k)$-indipendente se, per qualsiasi scelta di $k$ indici $1 \le i_1 < i_2 < \dots < i_k \le n$ e qualsiasi sottoinsieme $T \subseteq \{H, T\}^k$ di stringhe di lunghezza $k$ sull'alfabeto $\{H, T\}$, vale quanto segue: la somma di $a_s$ sulle $2^{n-k}|T|$ stringhe $s$ la cui sottosequenza $s[i_1]s[i_2]\dots s[i_k]$ appartiene a $T$ differisce da $\frac{|T|}{2^k}$ per non più di $\varepsilon$. In termini probabilistici, ciò può essere espresso come:
$$\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, ciò significa che per distinguere la distribuzione da quella uniforme dovrai o distinguere probabilità la cui differenza non supera $\varepsilon$, oppure osservare più di $k$ bit delle stringhe prodotte dalla distribuzione.
La distribuzione $\{a_s\}_{s \in S}$ è detta $t$-vicina alla distribuzione uniforme se è $(2^{-t}t, t)$-indipendente.
Nella definizione di $(\varepsilon, k)$-indipendenza era implicito che si dovessero prima scegliere $k$ indici e solo allora studiare la distribuzione di probabilità su quei $k$ indici. Nel modello di accesso all'oracolo di lunghezza $k$, tutto è diverso. Viene generata una stringa casuale di lunghezza $n$, e poi vengono condotti $k$ turni del seguente formato: tu dichiari un intero $i \in \{1, 2, \dots, n\}$ e, in risposta, ti verrà comunicato $s[i]$. Puoi decidere quale indice chiamare successivamente tenendo conto di tutte le domande poste in precedenza e delle relative risposte.
Per dimostrare che puoi distinguere le distribuzioni del pigro Sam e della diligente Sarah, dovrai, avendo accesso all'oracolo di lunghezza $t$ su $m$ stringhe di lunghezza $n$ campionate dalle loro distribuzioni (ciascuna generata in modo indipendente e uniforme dalla distribuzione del pigro Sam o da quella della diligente Sarah), concludere per ciascuna di esse da quale distribuzione è stata tratta, e indovinare correttamente almeno $0.75m - 2\sqrt{m}$ volte.
Protocollo di interazione
La prima riga contiene un intero $t$, che indica la vicinanza richiesta a una distribuzione uniforme e la lunghezza dell'accesso all'oracolo ($1 \le t \le 5$).
In risposta, stampa una riga con un singolo intero $n$, che indica la lunghezza delle stringhe per le quali sei pronto a fornire la distribuzione e una prova interattiva di distinguibilità ($t \le n \le 20$).
Nella riga successiva, stampa una riga con $2^n$ interi $b_s$, che definiscono la tua distribuzione ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Sulla base di questi dati, la giuria sceglierà la distribuzione $\{a_s\}_{s \in S}$ secondo la regola $a_s = b_s / \sum_{s \in S} b_s$. I valori di $b_s$ devono essere elencati nell'ordine lessicografico delle stringhe $s$: ad esempio, per $n = 3$, i numeri devono essere stampati nel seguente ordine: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.
Successivamente, leggi un intero $m$, che indica il numero di verifiche interattive ($1 \le m \le 10^4$). In seguito verranno presentate le $m$ verifiche, che dovranno essere completate una dopo l'altra.
All'inizio di ogni verifica, la giuria sceglierà prima la distribuzione $\{a_s\}_{s \in S}$ del pigro Sam oppure della diligente Sarah con probabilità $\frac{1}{2}$. Dopodiché, la giuria campiona una stringa casuale $s \sim \{a_s\}_{s \in S}$: qualsiasi stringa $s$ può essere ottenuta con probabilità $a_s$. La giuria ti dà quindi l'opportunità di porre non più di $t$ domande sui caratteri della stringa $s$. Per porre una domanda, stampa una riga con un intero $q \in \{1, 2, \dots, n\}$, che indica l'indice del carattere di interesse. Dopodiché, leggi il carattere "H" o "T" che rappresenta la risposta alla query. Dopo aver posto da $0$ a $t$ domande, stampa una riga con il nome "Sam" se ritieni che $s$ sia stata presa dalla distribuzione del pigro Sam, oppure "Sarah" se ritieni che $s$ sia stata presa dalla distribuzione della diligente Sarah. Subito dopo, passa alla verifica successiva finché non le avrai completate tutte e $m$.
Le stringhe possono essere stampate indifferentemente in maiuscolo o minuscolo.
Dopo ogni riga stampata, non dimenticare di svuotare il buffer di output (flush).
Esempio
Input 1
2 3 T T T T T
Output 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH