นี่คือปัญหาแบบโต้ตอบ (interactive problem)
แซมผู้ขี้เกียจและซาราห์ผู้ขยันขันแข็งได้รับมอบหมายให้คิดค้นการแจกแจงความน่าจะเป็นที่น่าสนใจสองแบบบนเซตของสตริงความยาว $n$ บนเซตอักขระ $\{H, T\}$ แซมผู้ขี้เกียจจะเพียงแค่โยนเหรียญ $n$ ครั้ง (โดยแต่ละด้านจะออกด้วยความน่าจะเป็น $\frac{1}{2}$ และการโยนเหรียญทุกครั้งเป็นอิสระต่อกัน) แล้วเขียน "H" สำหรับแต่ละครั้งที่ออกหัว และเขียน "T" สำหรับแต่ละครั้งที่ออกก้อย คุณต้องการช่วยซาราห์ผู้ขยันขันแข็งสั่งสอนแซมผู้ขี้เกียจ คุณได้รับจำนวนเต็ม $t$ จงช่วยซาราห์คิดค้นการแจกแจงที่ $t$-ใกล้เคียง กับการแจกแจงเอกรูป (uniform distribution) พร้อมทั้งพิสูจน์แบบโต้ตอบว่าคุณสามารถแยกแยะระหว่างการแจกแจงของแซมผู้ขี้เกียจและซาราห์ผู้ขยันขันแข็งได้ด้วยการเข้าถึงออราเคิล (oracle access) ความยาว $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$ บนสตริง $s$ จำนวน $2^{n-k}|T|$ ตัวที่มีลำดับย่อย $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$ กับสตริงความยาว $n$ จำนวน $m$ ตัวที่สุ่มตัวอย่างมาจากการแจกแจงของพวกเขา (แต่ละตัวถูกสร้างขึ้นอย่างเป็นอิสระและด้วยความน่าจะเป็นเท่ากันจากการแจกแจงของแซมผู้ขี้เกียจหรือซาราห์ผู้ขยันขันแข็ง) เพื่อสรุปสำหรับสตริงแต่ละตัวว่ามันถูกนำมาจากการแจกแจงของใคร และทายให้ถูกต้องอย่างน้อย $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$ จากนั้นกรรมการจะให้โอกาสคุณถามคำถามเกี่ยวกับอักขระของสตริง $s$ ได้ไม่เกิน $t$ คำถาม ในการถามคำถาม ให้พิมพ์บรรทัดที่มีจำนวนเต็ม $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