neizod's speculation

insufficient data for meaningful answer

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

Thursday, April 16, 2015, 08:00 AM

ปีนี้ประมาทไปเยอะครับ คือตอนแรกตั้งใจว่าจะถ่างตามาเริ่มเล่นตั้งแต่ปล่อยโจทย์ตอน 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$ ซึ่งมีนิยามที่สวยงามเรียบง่าย คือ

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

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

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

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

  • สมบัติปิดบนการคูณ คือ ถ้าใช้การคูณอย่างเดียวบนสมาชิกของเซ็ต $\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$ ก็ตอบว่าถูกได้เลย

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

โจทย์ข้อนี้ฉลาดตรงที่เอาตัวเลข $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 เพิ่มเองโลด ~