Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 1024 MB Points totaux : 100 Interactif Hackable ✓
Statistiques

Detta är ett interaktivt problem.

Late Sam och flitiga Sarah har fått i uppdrag att ta fram två intressanta sannolikhetsfördelningar över mängden av strängar av längd $n$ över alfabetet $\{H, T\}$. Late Sam kommer helt enkelt att singla slant $n$ gånger (där varje sida visas med sannolikheten $\frac{1}{2}$; alla slantsinglingar är oberoende) och skriva ner ”H” för varje krona och ”T” för varje klave. Du vill hjälpa flitiga Sarah att ge late Sam en läxa. Du får ett heltal $t$. Hjälp Sarah att ta fram en fördelning som är $t$-nära den likformiga fördelningen, samtidigt som du interaktivt bevisar att du kan skilja mellan late Sams och flitiga Sarahs fördelningar med orakelåtkomst av längd $t$.

Formellt, för något heltal $n$, betrakta mängden $S = \{H, T\}^n$ av storlek $2^n$, som består av alla möjliga strängar av längd $n$ över alfabetet med de två tecknen ”H” och ”T”. En fördelning över mängden $S$ definieras som en array av icke-negativa reella tal $\{a_s\}_{s \in S}$ av längd $2^n$ indexerad av elementen i $S$, sådan att deras summa är lika med $1$. En av de enklaste fördelningarna är den likformiga fördelningen, där alla $a_s$ är lika med $2^{-n}$.

För ett talpar $\varepsilon \in [0; +\infty)$ och $k \in \{0, 1, \dots, n\}$ säger vi att $\{a_s\}_{s \in S}$ är en $(\varepsilon, k)$-oberoende fördelning om följande gäller för varje val av $k$ index $1 \le i_1 < i_2 < \dots < i_k \le n$ och varje delmängd $T \subseteq \{H, T\}^k$ av strängar av längd $k$ över alfabetet $\{H, T\}$: summan av $a_s$ över de $2^{n-k}|T|$ strängar $s$ vars delsekvens $s[i_1]s[i_2]\dots s[i_k]$ tillhör $T$ avviker från $\frac{|T|}{2^k}$ med högst $\varepsilon$. I sannolikhetsteoretiska termer kan detta uttryckas 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 betyder detta att du för att skilja fördelningen från den likformiga antingen måste kunna skilja på sannolikheter vars skillnad inte överstiger $\varepsilon$, eller titta på fler än $k$ bitar i strängarna som genereras av fördelningen.

Fördelningen $\{a_s\}_{s \in S}$ kallas $t$-nära den likformiga fördelningen om den är $(2^{-t}t, t)$-oberoende.

I definitionen av $(\varepsilon, k)$-oberoende underförstods det att du först måste välja $k$ index och först därefter studera sannolikhetsfördelningen över dessa $k$ index. I modellen med orakelåtkomst av längd $k$ är allt annorlunda. En slumpmässig sträng av längd $n$ genereras, och därefter genomförs $k$ rundor enligt följande format: du anger ett heltal $i \in \{1, 2, \dots, n\}$, och som svar får du veta $s[i]$. Du kan bestämma vilket index du vill fråga om härnäst med hänsyn tagen till alla tidigare ställda frågor och deras svar.

För att bevisa att du kan skilja på late Sams och flitiga Sarahs fördelningar måste du, med orakelåtkomst av längd $t$ till $m$ strängar av längd $n$ dragna ur deras fördelningar (var och en oberoende och likformigt genererad från antingen late Sams eller flitiga Sarahs fördelning), för var och en av dem avgöra från vems fördelning den togs, och gissa rätt minst $0.75m - 2\sqrt{m}$ gånger.

Interaktionsprotokoll

Den första raden innehåller ett heltal $t$, som anger den krävda närheten till en likformig fördelning samt längden på orakelåtkomsten ($1 \le t \le 5$).

Som svar ska du skriva ut en rad med ett enda heltal $n$, som anger längden på de strängar för vilka du är redo att ange fördelningen och ett interaktivt bevis på särskiljbarhet ($t \le n \le 20$).

På nästa rad ska du skriva ut en rad med $2^n$ heltal $b_s$, som definierar din fördelning ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Baserat på dessa data kommer juryn att välja fördelningen $\{a_s\}_{s \in S}$ enligt regeln $a_s = b_s / \sum_{s \in S} b_s$. Värdena på $b_s$ måste anges i lexikografisk ordning för strängarna $s$: till exempel för $n = 3$ ska talen skrivas ut i följande ordning: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Läs därefter in ett heltal $m$, som anger antalet interaktiva kontroller ($1 \le m \le 10^4$). Efter detta presenteras de $m$ kontrollerna, vilka måste genomföras en efter en.

I början av varje kontroll väljer juryn först fördelningen $\{a_s\}_{s \in S}$ antingen från late Sam eller flitiga Sarah med sannolikheten $\frac{1}{2}$. Därefter drar juryn en slumpmässig sträng $s \sim \{a_s\}_{s \in S}$: varje sträng $s$ kan erhållas med sannolikheten $a_s$. Juryn ger dig sedan möjlighet att ställa högst $t$ frågor om tecknen i strängen $s$. För att ställa en fråga skriver du ut en rad med ett heltal $q \in \{1, 2, \dots, n\}$, som anger indexet för det tecken du är intresserad av. Därefter läser du in tecknet ”H” eller ”T” som är svaret på frågan. Efter att ha ställt från $0$ till $t$ frågor skriver du ut en rad med namnet ”Sam” om du tror att $s$ togs från late Sams fördelning, eller ”Sarah” om du tror att $s$ togs från flitiga Sarahs fördelning. Gå därefter omedelbart vidare till nästa kontroll tills du har slutfört alla $m$.

Strängar kan skrivas ut med valfria versaler eller gemener.

Glöm inte att tömma utdatabufferten (flush) efter varje utskriven rad.

Exempel

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