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

זוהי בעיה אינטראקטיבית.

סם העצלן ושרה החרוצה קיבלו משימה להמציא שתי התפלגויות מעניינות מעל קבוצת המחרוזות באורך $n$ מעל האלף-בית $\{H, T\}$. סם העצלן פשוט יטיל מטבע $n$ פעמים (כאשר כל צד מופיע בהסתברות $\frac{1}{2}$; כל הטלות המטבע הן בלתי תלויות) וירשום "H" עבור כל עץ ו-"T" עבור כל פלי. אתם רוצים לעזור לשרה החרוצה ללמד את סם העצלן לקח. נתון לכם מספר שלם $t$. עזרו לשרה להמציא התפלגות שהיא $t$-קרובה להתפלגות האחידה, תוך הוכחה אינטראקטיבית שאתם יכולים להבחין בין ההתפלגויות של סם העצלן ושרה החרוצה באמצעות גישת אורקל באורך $t$.

באופן פורמלי, עבור מספר שלם כלשהו $n$, נתבונן בקבוצה $S = \{H, T\}^n$ בגודל $2^n$, המורכבת מכל המחרוזות האפשריות באורך $n$ מעל האלף-בית בן שני התווים: "H" ו-"T". התפלגות מעל הקבוצה $S$ מוגדרת כמערך של מספרים ממשיים אי-שליליים $\{a_s\}_{s \in S}$ באורך $2^n$ המאונדקס על ידי איברי $S$, כך שסכומם שווה ל-$1$. אחת ההתפלגויות הפשוטות ביותר היא ההתפלגות האחידה, שבה כל ה-$a_s$ שווים ל-$2^{-n}$.

עבור זוג מספרים $\varepsilon \in [0; +\infty)$ ו-$k \in \{0, 1, \dots, n\}$, אנו אומרים ש-$\{a_s\}_{s \in S}$ היא התפלגות $(\varepsilon, k)$-בלתי תלויה אם, עבור כל בחירה של $k$ אינדקסים $1 \le i_1 < i_2 < \dots < i_k \le n$ וכל תת-קבוצה $T \subseteq \{H, T\}^k$ של מחרוזות באורך $k$ מעל האלף-בית $\{H, T\}$, מתקיים הדבר הבא: הסכום של $a_s$ על פני $2^{n-k}|T|$ המחרוזות $s$ שתת-הסדרה שלהן $s[i_1]s[i_2]\dots s[i_k]$ שייכת ל-$T$ סוטה מ-$\frac{|T|}{2^k}$ בלכל היותר $\varepsilon$. במונחים הסתברותיים, ניתן לבטא זאת כך:

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

באופן אינטואיטיבי, משמעות הדבר היא שכדי להבחין בין ההתפלגות לבין ההתפלגות האחידה, תצטרכו או להבחין בין הסתברויות שההפרש ביניהן אינו עולה על $\varepsilon$, או להסתכל על יותר מ-$k$ ביטים של המחרוזות הנוצרות על ידי ההתפלגות.

ההתפלגות $\{a_s\}_{s \in S}$ נקראת $t$-קרובה להתפלגות האחידה אם היא $(2^{-t}t, t)$-בלתי תלויה.

בהגדרה של $(\varepsilon, k)$-אי-תלות, השתמע שעליכם לבחור תחילה $k$ אינדקסים ורק אז לחקור את התפלגות ההסתברות על פני אותם $k$ אינדקסים. במודל גישת האורקל באורך $k$, הכל שונה. מחרוזת אקראית באורך $n$ נוצרת, ולאחר מכן מתנהלים $k$ סיבובים בפורמט הבא: אתם קוראים בשמו של מספר שלם $i \in \{1, 2, \dots, n\}$, ובתגובה נאמר לכם מהו $s[i]$. אתם יכולים להחליט לאיזה אינדקס לקרוא בפעם הבאה, תוך התחשבות בכל השאלות שנשאלו קודם לכן ובתשובותיהן.

כדי להוכיח שאתם יכולים להבחין בין ההתפלגויות של סם העצלן ושרה החרוצה, תצטרכו, בהינתן גישת אורקל באורך $t$ אל $m$ מחרוזות באורך $n$ שנדגמו מההתפלגויות שלהם (כל אחת נוצרה באופן בלתי תלוי ובאופן אחיד מההתפלגות של סם העצלן או מההתפלגות של שרה החרוצה), להסיק עבור כל אחת מהן מההתפלגות של מי היא נלקחה, ולנחש נכון לפחות $0.75m - 2\sqrt{m}$ פעמים.

פרוטוקול אינטראקציה

השורה הראשונה מכילה מספר שלם $t$, המציין את הקרבה הנדרשת להתפלגות אחידה ואת אורך גישת האורקל ($1 \le t \le 5$).

בתגובה, הדפיסו שורה עם מספר שלם יחיד $n$, המציין את אורך המחרוזות שעבורן אתם מוכנים לספק את ההתפלגות והוכחה אינטראקטיבית ליכולת ההבחנה ($t \le n \le 20$).

בשורה הבאה, הדפיסו שורה עם $2^n$ מספרים שלמים $b_s$, המגדירים את ההתפלגות שלכם ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). על סמך נתונים אלה, חבר השופטים יבחר את ההתפלגות $\{a_s\}_{s \in S}$ לפי הכלל $a_s = b_s / \sum_{s \in S} b_s$. הערכים של $b_s$ חייבים להיות רשומים בסדר לקסיקוגרפי של המחרוזות $s$: לדוגמה, עבור $n = 3$, יש להדפיס את המספרים בסדר הבא: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

לאחר מכן, קראו מספר שלם $m$, המציין את מספר הבדיקות האינטראקטיביות ($1 \le m \le 10^4$). בהמשך יוצגו $m$ הבדיקות, שאותן יש להשלים בזו אחר זו.

בתחילת כל בדיקה, חבר השופטים יבחר תחילה את ההתפלגות $\{a_s\}_{s \in S}$ של סם העצלן או של שרה החרוצה בהסתברות $\frac{1}{2}$. לאחר מכן, חבר השופטים דוגם מחרוזת אקראית $s \sim \{a_s\}_{s \in S}$: כל מחרוזת $s$ יכולה להתקבל בהסתברות $a_s$. לאחר מכן חבר השופטים נותן לכם הזדמנות לשאול לא יותר מ-$t$ שאלות על התווים של המחרוזת $s$. כדי לשאול שאלה, הדפיסו שורה עם מספר שלם $q \in \{1, 2, \dots, n\}$, המציין את האינדקס של התו המעניין אתכם. לאחר מכן, קראו את התו "H" או "T" שהוא התשובה לשאילתה. לאחר ששאלתם בין $0$ ל-$t$ שאלות, הדפיסו שורה עם השם "Sam" אם אתם מאמינים ש-$s$ נלקחה מההתפלגות של סם העצלן, או "Sarah" אם אתם מאמינים ש-$s$ נלקחה מההתפלגות של שרה החרוצה. מיד לאחר מכן, עברו לבדיקה הבאה עד שתשלימו את כל $m$ הבדיקות.

ניתן להדפיס מחרוזות באותיות גדולות או קטנות.

לאחר כל שורה מודפסת, אל תשכחו לרוקן את חוצץ הפלט (flush).

דוגמה

קלט 1

2
3
T
T
T
T
T

פלט 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.