ก่อนเริ่มแข่งเมื่อวานคิดว่ายังไงก็ผ่านฉลุยได้เข้ารอบถัดไปแน่ๆ แต่เหมือนยิ่งการแข่งปีหลังๆ ยิ่งมีขาโหดหน้าใหม่งอกขึ้นมาเรื่อยๆ พอเห็นผลคะแนนหลังแข่งจบนี่เข้าใจเลยว่ายังไงก็ต้องเก็บคะแนนเต็มเท่านั้นถึงจะการันตีผ่านเข้ารอบ

ไม่ได้เล่นโค้ดแจมรอบที่ผ่านมาเพราะเพิ่งกลับกรุงเทพเลยนัดกินอาหารอินเดียกับแกงค์สัมภาษณ์งาน กินเสร็จกลับมาบ้านแล้วเห็นว่าโจทย์ข้อนี้น่ารักดีเลยลองทำเล่นย้อนหลังดีกว่า

เทศกาลทดลองเขียนโปรแกรมด้วยภาษาใหม่ๆ วนกลับมาอีกปี ปีนี้ Google รู้ใจ(?) ทำ easter egg จำลองบัตรเจาะรูแบบคอมพิวเตอร์ยุค 1970 มาให้เล่นกันเลยทีเดียว 🤪

ส่วนตัวเคยได้ยินมุกเชิง “ให้คนขับรถเลคเชอร์แทน” มานานมากแล้ว มีหลายเวอร์ชันด้วย เวอร์ชันที่เคยฟังแล้วพิสดารที่สุดนี่ถึงขั้นบอกว่าศาตราจารย์เหนื่อยมากจนขอหลับรอในรถ ส่วนฝั่งคนขับที่ขึ้นเลคเชอร์แทนนั้น เมื่อเจอคนฟังยกมือถามคำถามที่ยากเกินกว่าจะตอบได้ เขาเลยหาทางแก้ตัวด้วยการบ่ายเบี่ยงว่า “คำถามง่ายนี้มาก เดี๋ยวไปปลุกคนขับรถมาตอบให้”

The problem of trisecting an angle is a geometric puzzle that can’t be done using only straightedge and compass. That’s because those tools are only good at simulating quadratic equations. To split an angle into three equal part, however, require the power to solve cubic equations instead. But if we’re not restricted ourselves to the classical tools, we’ll see that origami (the art of paper folding) offer more powerful way which can solve cubic equations, in other words, it can trisect an angle!

พอดีไปเจอโค้ดของ David Turner ที่นิยามการสร้างลิสต์จำนวนเฉพาะด้วยเทคนิคการร่อนตะแกรง ซึ่งโค้ดต้นฉบับนั้นเขียนในภาษา SASL (ภาษาโปรแกรมเชิงฟังก์ชันยุคเดียวกับ ML) แต่สามารถสรุปเทียบออกมาเป็น Haskell ได้ภายในสองบรรทัดเพียงเท่านี้

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

เนื่องจากเพื่อนเจอโจทย์เขียนโค้ดตอนสัมภาษณ์งานจากบริษัทฝั่งซิลิคอนวัลเลย์ โดยส่วนที่ให้คิดอัลกอริทึมมาแก้ปัญหาเอาจริงๆ แล้วก็น่าจะถือว่ายากเกินไปด้วยซ้ำเมื่อเทียบกับการเขียนโค้ดในโลกการทำงานจริง (และออกจะแปลกใจด้วยที่เลือกโจทย์เชิงแข่งเขียนโปรแกรมมาออก) ตรงนี้ก็เข้าใจว่าทางฝั่งคนสัมภาษณ์นั้นคงตั้งใจเลือกโจทย์ที่ยากมากๆ จนหลายคนไม่มีทางทำเสร็จทันเวลา ซึ่งเค้าคงไม่ได้ดูแค่ผลลัพธ์คำตอบสุดท้ายปลายทางเพียงอย่างเดียว แต่ดูกระบวนการคิดระหว่างทางไปด้วยว่าทำอย่างไรจึงเดินทางมาจนถึงจุดหมายนั้นๆ นอกจากนี้ก็อาจจะทดสอบเชิงจิตวิทยาไปในตัวด้วยหละมั้ง ว่าถ้าเจอโจทย์ที่ยากเกินกำลังแล้วเราจะรับมือมันยังไง (เหมือนกับแบบทดสอบโคบายาชิมารุไงหละ!)

สามเหลี่ยมปัสกาลนั้นเป็นเครื่องมือสุดเรียบง่ายที่ใครก็สามารถคำนวณมันได้ แต่มันกลับมีประโยชน์สารพัดจนเอาไปประยุกต์ใช้ได้ในหลายต่อหลายเรื่อง ซึ่งหนึ่งในเรื่องที่เห็นได้ชัดก็คือการกระจายทวินาม $(a+b)^n$ เมื่อ $n$ เป็นจำนวนเต็มไม่ติดลบ ที่ทำให้เราได้สัมประสิทธิ์ทวินามหลังการกระจายแต่ละพจน์ ว่าพวกมันเหล่านั้นมาจากแถวแนวนอนแถวที่ $n$ ในสามเหลี่ยมนั่นเอง (เริ่มนับแถวแรกว่าเป็นแถวที่ศูนย์)

When dealing with combinatorics computation, like $n!$ or $\binom{n}{r}$, we often interest in the numerical outcome. For example, $\binom{8}{3} = 56$, which means given a set of $8$ elements, there are $56$ distinct ways to choose $3$ elements from it.