สืบเนื่องจากบล็อก TECHJAM 2018 — Code Incubation #2 ที่กล่าวถึงโจทย์ปัญหา Optimization ข้อหนึ่งซึ่งเป็นปัญหาเปิดที่ไม่มีใครทราบวิธีที่ดีที่สุด และได้นำมาใช้ในการแข่งขัน TechJam 2017 Code Track รอบสุดท้ายที่ผ่านมา

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

Table of Contents

• What is “Output-Only”?
  • TechJam 2017’s Final Problem
• How to solve Output-Only problems?
  • Approach 1: Brute Force
  • Approach 2: Observation, Heuristics and Approximation
  • Approach 3: Meta-heuristics
    • Hill Climbing
    • Simulated Annealing
    • Genetic Algorithm
• Training Approaches
  • Simplifying the Problem
  • Solving similar problems
• Conclusion

What is “Output-Only”?

โดยทั่วไปแล้ว ในการทำโจทย์ต่าง ๆ ผู้เข้าแข่งขันจะมีหน้าที่ในการส่ง source code มาในระบบ และให้ระบบตรวจว่าโปรแกรมสามารถคำนวณคำตอบได้ถูกต้อง ภายในระยะเวลาและหน่วยความจำที่จำกัดได้หรือไม่

แต่นอกจากโจทย์ดังกล่าวแล้ว ยังมีโจทย์อีกสองประเภทหลัก ๆ ที่แปลกใหม่ก็คือ โจทย์ประเภท Interactive ซึ่งโปรแกรมของผู้เข้าแข่งขันจะต้องติดต่อ ถาม-ตอบ กับโปรแกรมที่โจทย์กำหนดให้ และโจทย์ประเภท Output-Only ที่ผู้เข้าแข่งขันจะได้ไฟล์ input ไปเลย แล้วสามารถนำไฟล์ input ดังกล่าวไปแก้อย่างไรก็ได้

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

TechJam 2017’s Final Problem

โจทย์ปัญหาข้อหนึ่งที่โผล่มาในการแข่งขัน Code Track รอบสุดท้ายของ TechJam 2017 เป็นดังนี้

กำหนดตารางขนาด $N \times M$ มาให้ โดยที่ตารางประกอบด้วยตัวเลข 0 และ 1 เพียงเท่านั้น แทนรูปแบบการระบายสีที่ต้องการ

หากเรามีตารางขนาดเท่ากันที่ประกอบไปด้วยเลข 0 เพียงเท่านั้น และในแต่ละครั้ง เราสามารถเลือกสี่เหลี่ยมจัตุรัสขนาด $k \times k$ ใดๆ ก็ได้ (เลือกค่า $k$ เท่าใดก็ได้) เพื่อทำการ toggle สี (จาก 0 เป็น 1, จาก 1 เป็น 0)

จงหาวิธีที่ใช้จำนวนครั้งในการ toggle น้อยที่สุดเพื่อที่จะได้รูปแบบการระบายสีที่ต้องการ

ตัวอย่างโจทย์ TechJam 2017

How to solve Output-Only problems?

ในที่นี้จะขอกล่าวถึงกระบวนการแก้ปัญหาที่น่าจะเป็นประโยชน์กับการแก้โจทย์ Output-Only โดยยกตัวอย่างการประยุกต์ใช้ตามโจทย์ TechJam ข้างบน

Approach 1: Brute Force

วิธีหนึ่งที่สามารถใช้แก้ปัญหาดังกล่าวได้คำตอบดีที่สุดแน่นอนก็คือการทดลองทุกกรณีที่เป็นไปได้

พิจารณากราฟที่ node แต่ละ node คือสถานะของตารางที่เป็นไปได้และ edge แทนกระบวนการ toggle สี่เหลี่ยม 1 ครั้ง เราสามารถหาเส้นทางสั้นที่สุดจาก node ตารางเลข 0 ทั้งหมด ไปยัง node ตารางที่เราต้องการได้

หากเราลองพิจารณาดู จะพบว่าจำนวนรูปแบบตารางทั้งหมดที่เป็นไปได้คือ $2^{NM}$ ซึ่งเมื่อ $N = M = 6$ จำนวนความเป็นไปได้ก็มีมากถึง $6.8 \times 10^{11}$ ซึ่งส่วนนี้ยังไม่ได้คิดถึงว่าสี่เหลี่ยมที่ toggle ได้มีจำนวนประมาณ $\mathcal{O}(N^3)$ (สมมติว่า $N \approx M$) ซึ่งจะยิ่งทำให้เราไม่สามารถแก้โจทย์ดังกล่าวได้ภายในเวลาที่กำหนด เนื่องจากโจทย์ไม่ได้บังคับให้เราหาคำตอบที่ดีที่สุดที่เป็นไปได้ในทางทฤษฎี ดังนั้น เราควรทดลองคิดวิธีที่น่าจะใช้เวลาไวขึ้นกว่านี้ แลกด้วยคุณภาพของคำตอบ

Approach 2: Observation, Heuristics and Approximation

การแก้โจทย์ประเภทนี้ เราสามารถใช้แนวคิดตามสัญชาตญาณมาช่วยแก้โจทย์ได้ เช่น

• “พยายามวางรูปสี่เหลี่ยมที่ใหญ่ที่สุดก่อน แล้วค่อยๆ ลดขนาดลงไปเรื่อยๆ จนได้รูปที่ต้องการ” ตามวิธีที่บล็อกของทาง TechJam แนะนำ

• ลองสังเกตสี่เหลี่ยมจัตุรัสย่อยทุกแบบที่เป็นไปได้เรียงจากขนาดใหญ่สุดมาขนาดเล็กสุด หากพบว่าภายในสี่เหลี่ยมมีช่องที่จำเป็นต้อง toggle มากเกินครึ่งหนึ่ง ควร toggle สี่เหลี่ยมนี้

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

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

Approach 3: Meta-heuristics

ในกรณีที่เราคิดไม่ออกว่าจะใช้เทคนิคใดในการแก้ปัญหาดี สิ่งสุดท้ายที่เราพึ่งได้ก็คือ Meta-heuristics ที่ใช้ในการแก้ปัญหา โดย Meta-heuristics ที่เป็นที่รู้จักกันก็เช่น

Hill Climbing

หลักการของ Hill Climbing ก็คือการทดลองสุ่มคำตอบมาสักคำตอบหนึ่ง แล้วพยายามปรับแบบสุ่ม ๆ เรื่อย ๆ หากเจอคำตอบใหม่ที่ดีกว่าก็เปลี่ยนมาใช้คำตอบใหม่

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

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

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

Simulated Annealing

มีความคล้ายคลึงกับ Hill Climbing แต่จะแก้ปัญหาเรื่อง local maxima โดยการปรับเปลี่ยนคำตอบแต่ละครั้ง เราอาจจะยอมรับคำตอบที่แย่กว่าเดิมได้ (ปกติเรายอมรับแค่คำตอบที่ดีกว่าเดิมเท่านั้น) โดยในช่วงแรก ๆ ของการทำงานของโปรแกรม เราจะเปิดโอกาสยอมรับคำตอบที่แย่กว่า มากกว่าการทำงานช่วงท้าย ๆ ของโปรแกรมที่เราจะรับเฉพาะคำตอบที่ดีกว่าเท่านั้น

Genetic Algorithm

Genetic Algorithm เป็นวิธีการแก้ไขปัญหาที่ได้รับแรงบันดาลใจมาจากกระบวนการพัฒนาตามธรรมชาติของ species ต่าง ๆ บนโลกใบนี้ที่มีการพัฒนาต่อเนื่องกันไปเป็นรุ่น ๆ และปล่อยให้ธรรมชาติคัดสรรสมาชิกของประชากรที่มีคุณภาพที่สุดเท่านั้น (natural selection, survival of the fittest)

ขั้นตอนในการเขียนโปรแกรม Genetic Algorithm จะเป็นดังนี้

1. สุ่มประชากร “คำตอบ” เริ่มต้นมาเป็นรุ่นแรก (จำนวนคำตอบขึ้นอยู่กับลักษณะปัญหาที่จะแก้ ดูตามความเหมาะสม)

2. วัดคุณภาพของคำตอบแต่ละตัว

3. สร้างรุ่นต่อไป: เลือกพ่อพันธุ์/แม่พันธุ์ โดยให้โอกาสตัวที่คำตอบดีที่สุดเยอะ ๆ (ตัวที่คำตอบแย่ ๆ จะมีโอกาสโดนเลือกน้อย) แล้วนำมาทำกระบวนการ crossover และ mutation เพื่อสร้างรุ่นต่อไป

4. กำจัดคำตอบที่แย่ที่สุดออกไป เหลือเพียงประชากรรุ่นใหม่ที่มีคุณภาพมากกว่าเดิมเท่านั้น วนซ้ำไปเรื่อย ๆ จนกว่าจะได้คำตอบที่เราพอใจ

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

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

นอกจากนี้ เพื่อความหลากหลายของประชากร เราจะต้องออกแบบ operation mutation เพื่อสุ่มดัดแปลงประชากรบางส่วน (ดัดแปลงเพียงเล็กน้อยเท่านั้น) เช่น การสุ่มเลือกตำแหน่งเพื่อเปลี่ยนอักขระ/ตัวเลขเพียง 1 ตำแหน่ง เป็นต้น

หากเราสามารถออกแบบวิธีการเก็บข้อมูล, operation รวมถึงตั้งค่า parameter ต่าง ๆ เช่น จำนวนประชากร, ความน่าจะเป็นที่จะเกิด mutation ได้ดี ก็จะทำให้โปรแกรมของเราสามารถหาคำตอบของปัญหาที่เราต้องการจะแก้ได้อย่างรวดเร็ว

Training Approaches

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

Simplifying the Problem

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

• ถ้าแทนที่จะกำหนดตารางให้ โจทย์กำหนดมาให้เป็นเส้นตรง (แทนที่จะเป็นการพลิกช่วงสี่เหลี่ยม ก็กลายเป็นการพลิกช่วงหนึ่งของ array แทน) จะแก้อย่างไร

• ถ้าโจทย์ล็อคขนาดของสี่เหลี่ยมจัตุรัสมาให้แบบเดียว จะแก้อย่างไร

• ถ้าเป็นอย่างนี้ทั้งคู่ล่ะ จะแก้อย่างไร

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

Solving similar problems

หากต้องการจะฝึกฝนการทำโจทย์ Output-Only เราก็ควรฝึกกับโจทย์ที่มีรูปแบบคล้าย ๆ กัน เช่นโจทย์ของการแข่งขัน IOI หรือโจทย์ Tiebreaker ของ CodeChef Long Challenge เป็นต้น

โจทย์ Output-Only ของ IOI ที่เป็นที่รู้จักกัน เช่น

• Road Service - IOI 2018 Practice Session

• Nowruz - IOI 2017 Day 1

• Pebbling Odometer - IOI 2012 Day 1

• Maze - IOI 2010 Day 2

นอกจากนี้ยังมีโจทย์อื่น ๆ ที่ไม่ใช่ Output-Only แต่ยังคงต้องใช้ความคิดสร้างสรรค์ในแบบคล้าย ๆ กัน เช่น

• Scales - IOI 2015 Day 1

• Art Class - IOI 2013 Day 1

• Languages - IOI 2010 Day 1

Conclusion

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