โจทย์จากการแข่งขัน IOI 1992 เอาจริงโจทย์ข้อนี้ก็อาจเรียกได้ว่าไม่ใช่โจทย์ที่ยากหรือโดดเด่นเท่าไหร่ (เมื่อเทียบกับโจทย์อื่นๆ) แต่ส่วนตัวแล้วก็เรียกได้ว่ามีความทรงจำร่วมกับโจทย์นี้พอสมควร เพราะว่ามันเป็นโจทย์แรกๆ ที่เปิดโลกให้เรารู้จักการนำคอมพิวเตอร์มาช่วยแก้โจทย์ปัญหาเลยหล่ะ¹

เป็นที่ทราบกันดีว่า¹ เมทริกซ์สำหรับการหมุนวัตถุในสองมิติ (หมุนรอบจุดกำเนิดด้วยมุม $\theta$ ในทิศทางทวนเข็มนาฬิกา) นั้นคือ

โอเรอรี่เป็นเครื่องมือทางดาราศาสตร์อย่างหนึ่งที่ช่วยให้เรา “เห็นภาพ” และเรียนรู้เกี่ยวกับระบบสุริยะ โดยมันจะจำลองลักษณะต่างๆ ของดวงอาทิตย์ดาวเคราะห์และดาวบริวาร ไม่ว่าจะเป็น ขนาด ตำแหน่ง วงโคจร ไปจนถึงการหมุนรอบตัวเอง พูดง่ายๆ ว่ามันก็คือนาฬิกาดาราศาสตร์แบบหนึ่งนั่นแหล่ะ ซึ่งก็แน่นอนว่าเครื่องมือในลักษณะเช่นนี้ถูกคิดค้นพัฒนาขึ้นมาอย่างยาวนานตามประวัติศาสตร์มนุษยชาติ แต่ว่าหมุดหมายสำคัญของโอเรอรี่ยุคใหม่นี้เริ่มนับที่ปี 1713 เมื่อ George Graham ได้ประดิษฐ์โมเดลระบบสุริยะด้วยกลไกฟันเฟืองที่จำลองการโคจรของดาวเคราะห์ต่างๆ ได้อย่างแม่นยำเพื่อนำไปเสนอต่อเอิร์ลแห่งโอเรอรี่ (จึงเป็นที่มาของชื่อเครื่องมือชิ้นนี้นั่นเอง)

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

แบบฝึกหัดสุดคลาสสิกในวิยุตคณิต สนใจปริภูมิ $\mathbb{R}^2$ ถามว่าเส้นตรง $n$ เส้นสามารถตัดแบ่งปริภูมินี้ออกเป็นชิ้นส่วนได้เป็นจำนวนมากที่สุดกี่ชิ้น?

คอมพิวเตอร์นั้นแท้จริงแล้วก็คือระบบตรรกะที่ซับซ้อนมากๆ ระบบหนึ่ง นั่นก็คือเราสามารถคำนวณสิ่งต่างๆ ได้ผ่านการนำตัวดำเนินการ $\wedge,\vee,\neg$ (AND/OR/NOT — เพื่อความสะดวก ในที่นี้จะเขียนนิเสธด้วยเส้นขีดยาวข้างบนแทน) มาทำงานร่วมกัน เช่น ถ้าเรามีจำนวนนับสองตัว $n,m$ ที่เขียนผ่านเลขฐานสองขนาด 4 บิต เราสามารถคำนวณ $n+m$ ได้จาก

เพื่อนในแลปเล่าให้ฟังว่า เจอโจทย์ฝึกสัมภาษณ์งานที่ให้เขียนโปรแกรมเพื่อบวกจำนวนเต็มสองตัวโดยห้ามใช้เครื่องหมายบวก(และลบ) … คือแว๊บแรกก็เข้าใจแหล่ะว่า โจทย์นี้ต้องการทดสอบพื้นฐานการจัดการข้อมูลในระดับบิต ซึ่งก็โอเค คำตอบก็แค่จับ nand gate มาประกอบเป็น halfadder, fulladder เพื่อทำงานบน 2’s compliment ก็เสร็จแล้ว (ถ้ายังจำเทคนิคเหล่านั้นได้จากสถาปัตยกรรมคอมพิวเตอร์อะนะ)

เพลงเก่าแล้ว แต่ MV ปั่นโคตรๆ wwwwwwww

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

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