IOI 1995: สายไฟและสวิตช์
โจทย์จากการแข่งขัน IOI 1995 ซึ่งนับว่าเป็นโจทย์ระดับตำนานเพราะเป็นโจทย์ที่นำแนวคิดการเขียนโปรแกรมเชิงโต้ตอบมาใช้เป็นครั้งแรก ซึ่งก็คือให้เราเขียนโปรแกรมในที่รับข้อมูลจากโปรแกรมของกรรมการ แล้วส่งคำถามกลับไปยังโปรแกรมของกรรมการเพื่อขอรับข้อมูลเพิ่มเติม จนกระทั่งเมื่อมีข้อมูลเพียงพอที่จะประกอบสร้างผลลัพธ์สุดท้ายแล้ว จึงค่อยส่งคำตอบไปให้โปรแกรมของกรรมการแล้วจบการทำงาน
โจทย์ให้สายไฟ
ตัวอย่างการส่งคำถาม 4 ครั้ง ซึ่งสามารถทำให้ระบุได้ว่าสายไฟเส้นตรงกลางต่อเชื่อมไปยังสวิตช์ตัวบน
โปรแกรมเชิงถามตอบ
ถึงโจทย์จะให้เราเขียนโปรแกรมฝั่งถามคำถามเพื่อแก้ปัญหาเพียงทางเดียว แต่เราคงทำงานได้ไม่ครบทั้งระบบถ้าเราไม่มีอีกโปรแกรมที่คอยตอบคำตอบกลับไปยังโปรแกรมต้นทางด้วย แน่หละว่าในการแข่งจริงๆ กรรมการจะเขียนโปรแกรมในส่วนนี้เตรียมไว้ให้เราแล้ว แต่การแข่งขันก็ล่วงเลยมาจนเกือบสามสิบปีไม่มีซอร์สโค้ดอะไรเหลือ งั้นเรามาเขียนส่วนนี้ไว้ใช้งานเองกันเถอะ
from random import randrange
def initialize(n):
wires = [randrange(n) for i in range(n)]
switches = [False for _ in range(n)]
return wires, switches
def judge(n=90, limit=900):
wires, switches = initialize(n)
print(n)
for _ in range(limit):
command, *rawindex = input().split()
indexes = [int(r) for r in rawindex]
if command == 'C':
index = indexes[0]
switches[index] = not switches[index]
print('NY'[switches[index]])
if command == 'T':
index = indexes[0]
print('NY'[switches[wires[index]]])
if command == 'D':
print('NY'[wires == indexes])
return
print('N')
โค้ดข้างต้นนี้เป็นโค้ดฝั่งกรรมการที่คอยตอบคำถามที่ส่งมาจากโปรแกรมผู้เข้าแข่งขัน ซึ่งมันจะสร้างเคสง่ายที่สุ่มสายไฟไปเชื่อมต่อกับสวิตช์ให้เสร็จก่อนแล้วค่อยตอบคำถาม ในการแข่งจริงโค้ดฝั่งกรรมการสามารถสร้างเคสที่ซับซ้อนยิ่งกว่านี้ได้ อย่างเช่นการไม่สร้างสายไฟทิ้งไว้ก่อน แต่เมื่อได้รับคำถามมาจากโปรแกรมผู้เข้าแข่งขันจึงค่อยๆ สร้างสายไฟแบบที่พยายามหลบการถามคำถามจากผู้เข้าแข่งขันและให้ข้อมูลกลับไปน้อยที่สุด เพื่อบังคับให้โปรแกรมผู้เข้าแข่งขันต้องถามคำถามเป็นจำนวนมากที่สุดจนอาจได้รับข้อมูลไม่เพียงพอเมื่อถามคำถามจนถึงข้อจำกัด
ในระบบปฏิบัติการตระกูล POSIX เราคงคุ้นเคยกันดีกับการ pipe ส่งข้อมูลขาออกจากโปรแกรมแรกไปเป็นข้อมูลขาเข้าให้โปรแกรมที่สอง อย่างไรก็ตามในโจทย์ที่เรากำลังแก้นี้เราต้องการการพูดคุยแบบสองทาง โปรแกรมที่สองยังต้องสามารถส่งข้อมูลกลับไปยังโปรแกรมแรกได้ด้วย เราสามารถต่อ pipeline ให้กับระบบได้ผ่าน named pipe ในที่นี้จะเป็นการสร้าง pipe ที่ชื่อ comm
ขึ้นมาก่อน แล้วจึงจับมันมาต่อเป็นลูปแบบนี้
mkfifo comm
<comm ./judge | ./contestant >comm
ถึงตอนนี้เราก็พร้อมที่จะโฟกัสกับการแก้โจทย์ปัญหาแล้ว
เทคนิคจากเลขฐานสอง
ลองโยนความคิดว่าเรามีสายไฟหลายเส้นทิ้งไปก่อน แล้วพิจารณาแค่ว่าเรามีสายไฟเพียงเส้นเดียวกับสวิตช์
แต่ระลึกไว้เสมอว่า เพื่อนแท้ที่ดีที่สุดของนักวิทยาการคอมพิวเตอร์ก็คือเลขฐานสอง เราอาจมองได้ว่าสวิตช์แต่ละตัวนั้นมีตัวเลขกำกับเป็นเลขฐานสองจาก
ตัวอย่างการสับสวิตช์สิบตัว ณ รอบต่างๆ ดังนั้นหากไฟติดในรอบที่
และดับในรอบ นั่นหมายถึงสายไฟเชื่อมไปยังสวิตช์หมายเลข
แต่เรายังทำกระบวนการเลขฐานสองนี้ให้มีประสิทธิภาพขึ้นไปได้อีก โดยแทนที่แต่ละรอบเราจะสับสวิตช์ให้ตรงกับระบบบิต ก็เปลี่ยนไปเป็นสับสวิตช์เลยเมื่อเห็นค่าในบิตในรอบนั้นๆ มีค่าเป็นหนึ่ง (นั่นคือไม่ต้องสนใจแล้วว่าสวิตช์นั้นมีสถาณะเป็นเปิดหรือปิดอยู่ก่อน แค่สับสวิตช์ให้กลายเป็นสถานะตรงกันข้ามก็พอ) แล้วค่อยมาปวดหัวเอากับตอนแปลงค่ากลับ ซึ่งก็ไม่ค่อยปวดหัวเท่าไหร่หรอกเพราะเราก็แค่ดูว่าการทดสอบไฟในรอบหนึ่งๆ ให้ค่าต่างจากรอบก่อนหน้าหรือไม่ หากให้ค่าต่างกันก็คือบิตตำแหน่งนั้นจะเป็นหนึ่งนั่นเอง
ตัวอย่างการสับสวิตช์สิบตัวในอีกทางหนึ่ง ซึ่งหากไฟติดในรอบที่
และดับในรอบที่ จะตีความได้ว่ามีการเปลี่ยนแปลงเกิดขึ้นในรอบแรก (ถือว่ารอบก่อนรอบแรกไฟไม่ติด) และรอบที่สาม จึงได้ว่าสายไฟเชื่อมไปยังสวิตช์หมายเลข
สังเกตว่าวิธีนี้ใช้การส่งคำสั่งประมาณ
ดังนั้นเราจึงได้โค้ดสำหรับแก้ปัญหานี้ว่า
def communicate(command, *values):
print(command, *values)
return {'N':0, 'Y':1}[input().strip()]
def bin_repr_search(n):
prevs = [0 for _ in range(n)]
wires = [0 for _ in range(n)]
switches = [0 for _ in range(n)]
for shift in range(ceil(log2(n))):
mask = 1 << shift
for i in range(n):
if bool(i & mask):
switches[i] = communicate('C', i)
for i in range(n):
curr = communicate('T', i)
if curr != prevs[i]:
wires[i] |= mask
prevs[i] = curr
return communicate('D', *wires)
ซึ่งสำหรับสายไฟและสวิตช์
เลี่ยงการทดสอบสวิตช์ที่ไม่จำเป็น
หากเรามีสายไฟและสวิตช์เป็นจำนวนในรูป
แต่การแก้ไขโปรแกรมจากหัวข้อที่แล้วให้ทำงานเช่นนี้ได้ อาจให้ผลลัพธ์เป็นโค้ดที่ซับซ้อนเกินความจำเป็น เราจะเริ่มเขียนโค้ดใหม่แต่ต้นโดยแบ่งสายไฟออกเป็นสองชุด คือชุดที่วัดค่าไฟได้เหมือนกับทิศสวิตช์ที่สับ กับอีกชุดที่ให้ค่าตรงกันข้าม แล้วจึงเรียกตัวเองลึกลงไปจนทดสอบสายไฟได้ครบทุกเส้น
def partition(candidates, lo, mid, hi, switch):
for i in range(lo, mid):
communicate('C', i)
left, right = [], []
for i in candidates:
light = communicate('T', i)
(right if light == switch else left).append(i)
return left, right
def aux(candidates, lo, hi, switch=0):
if hi - lo <= 1 or not candidates:
return [(i,lo) for i in candidates]
mid = (lo+hi) // 2
left, right = partition(candidates, lo, mid, hi, switch)
return aux(left, lo, mid, switch^1) + aux(right, mid, hi, switch)
def recursive_search(n):
result = sorted(aux(range(n), 0, n))
return communicate('D', *[str(v) for _, v in result])
ข้อดีของการเปลี่ยนไปเขียนโดยคิดจากบนลงล่างแบบนี้ คือนอกจากเราจะทดสอบสายไฟบางเส้นด้วยจำนวนบิตที่น้อยลงตามที่ได้อธิบายแล้ว เรายังจะเห็นชัดได้อีกว่าสวิตช์ช่วงใดบ้างที่ไม่มีสายไฟต่อเชื่อมแน่ๆ เลยไม่มีประโยชน์ที่จะต้องส่งคำสั่งไปเพื่อสับสวิตช์อีก จึงทำให้โยนช่วงเหล่านี้ทิ้งไปได้ และบีบให้จำนวนคำถามที่ส่งไปนั้นอยู่ภายในเกณฑ์ที่โจทย์กำหนดในที่สุด

author