<commit_before>---
title: Code Jam 2015 รอบคัดเลือก
tags:
  - Programming
  - Google Code Jam
  - Python
  - Haskell
date: 2015-04-16 08:00:00 +0700
---

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

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

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

---

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

<iframe width="853" height="480" src="https://www.youtube.com/embed/danBaPWT09A" frameborder="0" allowfullscreen></iframe>

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

{% highlight haskell %}
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]]
{% endhighlight %}

(อย่างไรก็ตาม เท่าที่เคยไปคอนเสิร์ตหลายครั้ง
รู้สึกว่าคนไทยจะมีค่าความอายเป็น infinity นะ)

---

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

ส่วนข้อสามนี่สนุกดี ถ้ายังจำเนื้อหาม.ปลายได้ เราจะมีเลขมหัศจรรย์ตัวนึงเรียกว่า $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}$ ละกันครับ โชคดีที่อย่างน้อยในเซ็ต $\mathbb{H} = \\{1,i,j,k\\}$ มันยังมี

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

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

จาก $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 ก็คือ

{% highlight python %}
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))
{% endhighlight %}

ข้อนี้ถ้าจะ optimize เพิ่มก็ยังทำได้อีก (code จริงที่เอาไปส่งก็เขียนสวยน้อยกว่านี้เพราะมัวแต่ optimize มากเกินไป) โดยเรามีข้อสังเกตดังนี้

- $aba = b$ สำหรับทุก $a,b \in \mathbb{H}$
- เราสามารถทดเก็บค่าสุดท้ายที่ได้จากการวิ่งผ่านเพื่อหาผลคูณของทุกตัวใน $LS$ ไว้ได้ แล้วพอจะวิ่งผ่าน $LS$ อีกรอบก็ใช้ค่าที่ทดไว้ได้เลย
- ในการทดลองจริง ค่า $X$ ที่จำเป็นต่อการคำนวณ ไม่เคยมีค่ามากถึง 8 เลย ซึ่งก็คือ $\forall x \in X, x \gt 4 \left[x \equiv x \pmod{4}, 4 \le x \lt 8\right]$

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


[@tamwb]: //twitter.com/tamwb
[@aibig]: //twitter.com/aibig<commit_msg>blog more specify on math notation<commit_after>---
title: Code Jam 2015 รอบคัดเลือก
tags:
  - Programming
  - Google Code Jam
  - Python
  - Haskell
date: 2015-04-16 08:00:00 +0700
---

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

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

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

---

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

<iframe width="853" height="480" src="https://www.youtube.com/embed/danBaPWT09A" frameborder="0" allowfullscreen></iframe>

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

{% highlight haskell %}
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]]
{% endhighlight %}

(อย่างไรก็ตาม เท่าที่เคยไปคอนเสิร์ตหลายครั้ง
รู้สึกว่าคนไทยจะมีค่าความอายเป็น infinity นะ)

---

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

ส่วนข้อสามนี่สนุกดี ถ้ายังจำเนื้อหาม.ปลายได้ เราจะมีเลขมหัศจรรย์ตัวนึงเรียกว่า $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} = \\{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$ ก็ตอบว่าถูกได้เลย

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

$$
  \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 ก็คือ

{% highlight python %}
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))
{% endhighlight %}

ข้อนี้ถ้าจะ 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 เพิ่มเองโลด ~


[@tamwb]: //twitter.com/tamwb
[@aibig]: //twitter.com/aibig
{'fraction_non_alphanumeric': 0.22657697182412012, 'fraction_numerical': 0.016574046992297944, 'mean_word_length': 4.841685649202733, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 7, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4035504', 'n_tokens_mistral': 7604, 'n_tokens_neox': 7981, 'n_words': 832}