Code Jam 2015 รอบคัดเลือก

ปีนี้ประมาทไปเยอะครับ คือตอนแรกตั้งใจว่าจะถ่างตามาเริ่มเล่นตั้งแต่ปล่อยโจทย์ตอน 6 โมงเช้าเลย แต่สุดท้ายก็เผลอหลับไปตอนตี 4 ตื่นมารู้ตัวอีกทีก็บ่ายแล้ว เลยพักสมองออกเล่นบอร์ดเกมกะ @tamwb และ @aibig ตามนัดปาร์ตี้สงกรานต์ แถมกลับมาก็ยังไม่มีสมาธิแก้โจทย์มัวแต่ดู MV เกาหลีอีก กว่าได้เริ่มทำแข่งจริงจังก็เหลือเวลาไม่กี่ชั่วโมงแล้ว

ตอนอ่านโจทย์ผ่านๆ ทุกข้อนี่คิดว่าง่าย ปีนี้ได้แก้มือเก็บคะแนนเต็มแน่ๆ ... ที่ไหนได้ bug ซ่อนเร้น 1 ข้อ แล้วก็ตีความโจทย์อีก 1 ข้อ สุดท้ายแก้ไม่ทัน ได้ส่งแค่ 2 ข้อ ดีแค่ไหนแล้วที่ยังไม่ตกรอบ 555

---

ข้อแรกง่ายฮะ แต่ถ้ายังอ่านโจทย์แล้วไม่อินขอให้ดูคลิปนี้ตอนนาทีที่ 7:05 และ 7:23 (เรียบร้อยแล้วก็กลับไปดูตั้งแต่ต้นด้วยจะดีมาก) :P



ส่วน code ก็ประมาณ

import Text.Printf (printf)
import Data.List.Split (splitOn)

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] = splitOn " " 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 นะ)

---

ข้อสองข้ามไปนะฮะ ทำไม่ได้ (ข้อสี่ด้วย)

ส่วนข้อสามนี่สนุกดี ถ้ายังจำเนื้อหาม.ปลายได้ เราจะมีเลขมหัศจรรย์ตัวนึงเรียกว่า i ซึ่งมีนิยามที่สวยงามเรียบง่าย คือ

i^2 = -1

สังเกตเพิ่มอีกหน่อยก็จะเห็นว่า

i^4 = 1    (multiplicative identity)

โจทย์เพิ่มความสนุกโดยให้ตัวเลขมหัศจรรย์ j และ k มาด้วย ทั้งสองตัวที่เพิ่มเข้ามานี้ มีนิยามแบบเดียวกันกะ i เด๊ะๆ เลย เพียงแต่มันไม่ใช่ i เพราะเรานิยามการคูณระหว่างตัวเลขเหล่านี้ว่า

ij = k
jk = i
ki = j

ความซับซ้อนของตัวเลขชุดนี้ยังเพิ่มขึ้นไปอีก เมื่อเรานิยามให้มันไม่มีสมบัติสลับที่ด้วย ซึ่งในที่นี้คือ

ji = -k
kj = -i
ik = -j

เพื่อความสะดวก สมมติชื่อให้เลขชุดนี้ว่า ℍu ละกันครับ โชคดีที่อย่างน้อยในเซ็ต ℍu = {1, i, j, k} มันยังมี

• สมบัติปิดบนการคูณ คือ ถ้าใช้การคูณอย่างเดียวบนสมาชิกของเซ็ต ℍu ผลลัพธ์ที่ได้ก็จะเป็นสมาชิกของเซ็ต ℍu ด้วย
• สมบัติจัดกลุ่มการคูณ คือ a(bc) = (ab)c สำหรับทุก a, b, c ∈ ℍu

สรุปง่ายๆ ถ้าใครถนัดเรื่องการคูณไขว้เวกเตอร์ ก็นึกถึงกฎมือขวาได้เลย

จาก X, LS ที่โจทย์ให้ การแก้ปัญหาแบบตรงๆ ก็คือวิ่งผ่านชุดตัวเลข LS เป็นจำนวน X ครั้ง โดยเลขแต่ละตัวเลข s ∈ LS ที่วิ่งผ่าน ก็จัดการคูณเก็บไว้ในใจไปเรื่อยๆ ถ้าเจอตัวเลขครบทั้ง i, j, k และหางที่เหลือคูณกันออกมาเป็น 1 ก็ตอบว่าถูกได้เลย

ถ้าอ่านมาจนถึงตรงนี้แล้วยังงงไม่หาย ลองดูการทำงานตามขั้นตอนวิธีด้วยตัวอย่างนี้

X  = 10
LS = ji

sequence: ji ji ji ji ji ji ji ji ji ji
running:  --->--->-------->----------->
found:       i   j        k           1

โจทย์ข้อนี้ฉลาดตรงที่เอาตัวเลข 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 ∈ ℍu
• เราสามารถทดเก็บค่าสุดท้ายที่ได้จากการวิ่งผ่านเพื่อหาผลคูณของทุกตัวใน LS ไว้ได้ แล้วพอจะวิ่งผ่าน LS อีกรอบก็ใช้ค่าที่ทดไว้ได้เลย
• ในการทดลองจริง จำนวน X ที่จำเป็นต่อการคำนวณไม่เคยมีค่าเกิน 8 เลย ซึ่งก็คือ x = min(x, 4+(x%4))

ถ้ายังอยากรู้ว่าข้อสังเกตเหล่านี้จริงหรือไม่ ถ้าจริงแล้วจะช่วยการคำนวณอย่างไร proof เพิ่มดูเองได้เลยครับ