Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100 インタラクティブ ハック可能 ✓
統計

Dette er et interaktivt problem.

Late Sam og flittige Sarah har fått i oppgave å komme opp med to interessante sannsynlighetsfordelinger over mengden av strenger med lengde $n$ over alfabetet $\{H, T\}$. Late Sam vil rett og slett kaste en mynt $n$ ganger (der hver side vises med sannsynlighet $\frac{1}{2}$; alle myntkastene er uavhengige) og skrive ned «H» for hver kron og «T» for hver mynt. Du ønsker å hjelpe flittige Sarah med å gi late Sam en lærepenge. Du får oppgitt et heltall $t$. Hjelp Sarah med å lage en fordeling som er $t$-nær den uniforme fordelingen, samtidig som du interaktivt beviser at du kan skille mellom fordelingene til late Sam og flittige Sarah med orakeltilgang av lengde $t$.

Formelt, for et heltall $n$, betrakt mengden $S = \{H, T\}^n$ av størrelse $2^n$, som består av alle mulige strenger med lengde $n$ over alfabetet med to tegn: «H» og «T». En fordeling over mengden $S$ defineres som en tabell av ikke-negative reelle tall $\{a_s\}_{s \in S}$ med lengde $2^n$ indeksert av elementene i $S$, slik at summen deres er lik $1$. En av de enkleste fordelingene er den uniforme fordelingen, der alle $a_s$ er lik $2^{-n}$.

For et tallpar $\varepsilon \in [0; +\infty)$ og $k \in \{0, 1, \dots, n\}$ sier vi at $\{a_s\}_{s \in S}$ er en $(\varepsilon, k)$-uavhengig fordeling hvis følgende gjelder for ethvert valg av $k$ indekser $1 \le i_1 < i_2 < \dots < i_k \le n$ og enhver delmengde $T \subseteq \{H, T\}^k$ av strenger med lengde $k$ over alfabetet $\{H, T\}$: summen av $a_s$ over de $2^{n-k}|T|$ strengene $s$ hvis delsekvens $s[i_1]s[i_2]\dots s[i_k]$ tilhører $T$, avviker fra $\frac{|T|}{2^k}$ med høyst $\varepsilon$. Med sannsynlighetsteoretiske termer kan dette uttrykkes som:

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

Intuitivt betyr dette at for å skille fordelingen fra den uniforme, må du enten skille mellom sannsynligheter hvis forskjell ikke overstiger $\varepsilon$, eller se på flere enn $k$ biter av strengene som produseres av fordelingen.

Fordelingen $\{a_s\}_{s \in S}$ kalles $t$-nær den uniforme fordelingen hvis den er $(2^{-t}t, t)$-uavhengig.

I definisjonen av $(\varepsilon, k)$-uavhengighet var det underforstått at du først må velge $k$ indekser og først deretter studere sannsynlighetsfordelingen over disse $k$ indeksene. I modellen med orakeltilgang av lengde $k$ er alt annerledes. En tilfeldig streng med lengde $n$ blir generert, og deretter gjennomføres $k$ runder på følgende format: du oppgir et heltall $i \in \{1, 2, \dots, n\}$, og som svar får du vite $s[i]$. Du kan bestemme hvilken indeks du vil spørre om neste gang ved å ta hensyn til alle tidligere stilte spørsmål og svarene på dem.

For å bevise at du kan skille mellom fordelingene til late Sam og flittige Sarah, må du, med orakeltilgang av lengde $t$ til $m$ strenger med lengde $n$ trukket fra fordelingene deres (hver enkelt generert uavhengig og uniformt fra enten late Sams eller flittige Sarahs fordeling), konkludere for hver av dem hvem sin fordeling den ble hentet fra, og gjette riktig minst $0.75m - 2\sqrt{m}$ ganger.

Interaksjonsprotokoll

Den første linjen inneholder et heltall $t$, som angir den påkrevde nærheten til en uniform fordeling samt lengden på orakeltilgangen ($1 \le t \le 5$).

Som svar skal du skrive ut en linje med et enkelt heltall $n$, som angir lengden på strengene du er klar til å oppgi fordelingen og et interaktivt bevis på skjelnbarhet for ($t \le n \le 20$).

På neste linje skal du skrive ut en linje med $2^n$ heltall $b_s$, som definerer fordelingen din ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Basert på disse dataene vil juryen velge fordelingen $\{a_s\}_{s \in S}$ etter regelen $a_s = b_s / \sum_{s \in S} b_s$. Verdiene til $b_s$ må listes opp i leksikografisk rekkefølge etter strengene $s$: for eksempel for $n = 3$ skal tallene skrives ut i følgende rekkefølge: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Deretter leser du inn et heltall $m$, som angir antallet interaktive sjekker ($1 \le m \le 10^4$). Etter dette følger de $m$ sjekkene, som må fullføres én etter én.

På begynnelsen av hver sjekk vil juryen først velge fordelingen $\{a_s\}_{s \in S}$ enten fra late Sam eller flittige Sarah med sannsynlighet $\frac{1}{2}$. Deretter trekker juryen en tilfeldig streng $s \sim \{a_s\}_{s \in S}$: enhver streng $s$ kan oppnås med sannsynlighet $a_s$. Juryen gir deg så muligheten til å stille høyst $t$ spørsmål om tegnene i strengen $s$. For å stille et spørsmål skriver du ut en linje med et heltall $q \in \{1, 2, \dots, n\}$, som angir indeksen til tegnet du er interessert i. Deretter leser du inn tegnet «H» eller «T» som er svaret på spørringen. Etter å ha stilt fra $0$ til $t$ spørsmål, skriver du ut en linje med navnet «Sam» hvis du tror at $s$ ble hentet fra late Sams fordeling, eller «Sarah» hvis du tror at $s$ ble hentet fra flittige Sarahs fordeling. Gå deretter umiddelbart videre til neste sjekk til du har fullført alle $m$.

Strenger kan skrives ut med store eller små bokstaver.

Etter hver utskrevne linje må du ikke glemme å tømme utdatabufferen (flush).

Eksempel

Inndata 1

2
3
T
T
T
T
T

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