Code Jam 2015 รอบคัดเลือก
ปีนี้ประมาทไปเยอะครับ คือตอนแรกตั้งใจว่าจะถ่างตามาเริ่มเล่นตั้งแต่ปล่อยโจทย์ตอน 6 โมงเช้าเลย แต่สุดท้ายก็เผลอหลับไปตอนตี 4 ตื่นมารู้ตัวอีกทีก็บ่ายแล้ว
เลยพักสมองออกเล่นบอร์ดเกมกะ @tamwb และ @aibig ตามนัดปาร์ตี้สงกรานต์ แถมกลับมาก็ยังไม่มีสมาธิแก้โจทย์มัวแต่ดู MV เกาหลีอีก กว่าได้เริ่มทำแข่งจริงจังก็เหลือเวลาไม่กี่ชั่วโมงแล้ว
ตอนอ่านโจทย์ผ่านๆ ทุกข้อนี่คิดว่าง่าย ปีนี้ได้แก้มือเก็บคะแนนเต็มแน่ๆ … ที่ไหนได้ bug ซ่อนเร้น 1 ข้อ แล้วก็ตีความโจทย์อีก 1 ข้อ สุดท้ายแก้ไม่ทัน ได้ส่งแค่ 2 ข้อ ดีแค่ไหนแล้วที่ยังไม่ตกรอบ 555
Standing Ovation
ข้อแรกง่ายฮะ code ก็ประมาณ
import Text.Printf (printf)
invites audience =
let aux [] _ _ inv = inv
aux (p:ps) shy acc inv = aux ps (shy+1) (acc+p+more) (inv+more)
where more = max 0 (shy-acc)
in aux audience 0 0 0
test t = do
it <- getLine
let [_, ps] = words it
printf "Case #%d: %d\n" t $ invites [read [p] :: Integer | p <- ps]
main = do
loop <- getLine
sequence_ [test t | t <- [1..read loop :: Integer]]
(อย่างไรก็ตาม เท่าที่เคยไปคอนเสิร์ตหลายครั้ง รู้สึกว่าคนไทยจะมีค่าความอายเป็น infinity นะ)
Dijkstra
ข้อสองข้ามไปนะฮะ ทำไม่ได้ (ข้อสี่ด้วย)
ส่วนข้อสามนี่สนุกดี ถ้ายังจำเนื้อหาม.ปลายได้ เราจะมีเลขมหัศจรรย์ตัวนึงเรียกว่า $i$ ซึ่งมีนิยามที่สวยงามเรียบง่าย คือ
\[i^2 = -1\]สังเกตเพิ่มอีกหน่อยก็จะเห็นว่า
\[i^4 = 1\]โจทย์เพิ่มความสนุกโดยให้ตัวเลขมหัศจรรย์ $j$ และ $k$ มาด้วย ทั้งสองตัวที่เพิ่มเข้ามานี้ มีนิยามแบบเดียวกันกะ $i$ เด๊ะๆ เลย เพียงแต่มันไม่ใช่ $i$ เพราะเรานิยามการคูณระหว่างตัวเลขเหล่านี้ว่า
\[\begin{align} ij &= k \\ jk &= i \\ ki &= j \end{align}\]ความซับซ้อนของตัวเลขชุดนี้ยังเพิ่มขึ้นไปอีก เมื่อเรานิยามให้มันไม่มีสมบัติสลับที่ด้วย ซึ่งในที่นี้คือ
\[\begin{align} ji &= -k \\ kj &= -i \\ ik &= -j \end{align}\]เพื่อความสะดวก สมมติชื่อให้เลขชุดนี้ว่า $\mathbb{H_u}$ ละกันครับ โชคดีที่อย่างน้อยในเซต $\mathbb{H_u} = \lbrace1,i,j,k\rbrace$ มันยังมี
- สมบัติปิดบนการคูณ คือ ถ้าใช้การคูณอย่างเดียวบนสมาชิกของเซต $\mathbb{H_u}$ ผลลัพธ์ที่ได้ก็จะเป็นสมาชิกของเซต $\mathbb{H_u}$ ด้วย
- สมบัติจัดกลุ่มการคูณ คือ $a(bc) = (ab)c$ สำหรับทุก $a,b,c \in \mathbb{H_u}$
สรุปง่ายๆ ถ้าใครถนัดเรื่องการคูณไขว้เวกเตอร์ ก็นึกถึงกฎมือขวาได้เลย
จาก $X,LS$ ที่โจทย์ให้ การแก้ปัญหาแบบตรงๆ ก็คือวิ่งผ่านชุดตัวเลข $LS$ เป็นจำนวน $X$ ครั้ง โดยเลขแต่ละตัวเลข $s \in LS$ ที่วิ่งผ่าน ก็จัดการคูณเก็บไว้ในใจไปเรื่อยๆ ถ้าเจอตัวเลขครบทั้ง $i,j,k$ และหางที่เหลือคูณกันออกมาเป็น $1$ ก็ตอบว่าถูกได้เลย
ถ้าอ่านมาจนถึงตรงนี้แล้วยังงงไม่หาย ลองดูการทำงานตามขั้นตอนวิธีด้วยตัวอย่างนี้
\[\overbrace{ \underbrace{ji\:\; j}_i \underbrace{i\:\; ji}_j \:\; \underbrace{ji\:\; ji\:\; ji}_k \:\; \underbrace{ji\:\; ji\:\; ji\:\; ji}_1 }^{X = 10,\; LS = ji}\]โจทย์ข้อนี้ฉลาดตรงที่เอาตัวเลข $X$ขนาดใหญ่มากๆ มาขู่ ทั้งที่เราสามารถ modulo มันทิ้งให้เหลือแค่หลักสิบได้ (ซึ่งก็คือ คำถามชุดใหญ่จะมีความยากแทบไม่ต่างกับคำถามชุดเล็กเลย)
การลดขนาด $X$ ทำได้โดยใช้ข้อสังเกตที่ว่า $i^4 = j^4 = k^4 = 1$ ซึ่งบอกเป็นนัยอยู่ 2 อย่างคือ
- ถ้าวิ่งคูณหา $i,j,k$ แต่ละตัวเกิน 4 รอบแล้วยังไม่เจอ ไม่ต้องวิ่งต่อ เพราะแต่ละรอบที่วิ่งเพิ่ม จะไม่ได้ผลลัพธ์ใหม่แล้ว
- หลังจากหา $i,j,k$ ได้ครบแล้ว หางที่เหลือสามารถ mod 4 ได้
ดังนั้น เราจะวิ่งผ่านชุดตัวเลขนี้ 3 ครั้ง (เพื่อหา $i,j,k$) โดยแต่ละครั้งวิ่งไม่เกิน 4 รอบ ซึ่งก็เท่ากับวิ่ง 12 รอบ แล้วรอบที่เหลือก็จับ mod 4 ได้เลย
หรือพูดจาภาษา code ก็คือ
def correct_misspelling(ijks, x):
x = min(x, 12+(x%4))
accumulate = Quaternion('+1')
searching = [Quaternion(it) for it in 'kji']
for _ in range(x):
for it in ijks:
accumulate *= Quaternion(it)
if searching and searching[-1] == accumulate:
accumulate = Quaternion('+1')
searching.pop()
return not searching and accumulate == Quaternion('+1')
for case in range(int(input())):
_, x = [int(n) for n in input().split()]
ijks = input().strip()
ans = 'YES' if correct_misspelling(ijks, x) else 'NO'
print('Case #{}: {}'.format(case+1, ans))
ข้อนี้ถ้าจะ optimize เพิ่มก็ยังทำได้อีก (code จริงที่เอาไปส่งก็เขียนสวยน้อยกว่านี้เพราะมัวแต่ optimize มากเกินไป) โดยเรามีข้อสังเกตดังนี้
- $aba = b$ สำหรับทุก $a,b \in \mathbb{H_u}$
- เราสามารถทดเก็บค่าสุดท้ายที่ได้จากการวิ่งผ่านเพื่อหาผลคูณของทุกตัวใน $LS$ ไว้ได้ แล้วพอจะวิ่งผ่าน $LS$ อีกรอบก็ใช้ค่าที่ทดไว้ได้เลย
- ในการทดลองจริง ค่า $X$ ที่จำเป็นต่อการคำนวณ ไม่เคยมีค่ามากถึง 8 เลย ซึ่งก็คือ $\forall x \in X, x \gt 4 \left[x \equiv x \pmod{4}, 4 \le x \lt 8\right]$
ถ้ายังอยากรู้ว่าข้อสังเกตเหล่านี้จริงหรือไม่ หากจริงแล้วจะช่วยการคำนวณอย่างไร proof เพิ่มเองโลด ~
author