[รีวิว] TechJam 2018 Regional Competition — Code Squad ภาคเหนือ

เอาตรง ๆ คืองานนี้มาแข่งเพื่อล่ารางวัลครับ :3 แต่ก็ไม่ได้คาดหวังอะไรมาก เพราะนี่ไม่ใช่แค่การแข่งขันในระดับ ม.ปลาย เท่านั้น นักศึกษามหาวิทยาลัย หรือแม้กระทั่งอาจารย์และ software developer คนอื่น ๆ ก็สามารถลงแข่งได้ด้วย

แต่ได้ยินมาว่างานนี้เน้น Algorithms และ Data Structures ผมก็เลยคิดว่า สกิลที่สะสมมาตั้งแต่งานแข่ง OI ต่าง ๆ (TOI, APIO, IOI) กับ Google Code Jam หรือพวกเว็บ Codeforces, CSAcademy อะไรงี้น่าจะช่วยได้บ้างแหละ ผนวกกับช่วงเวลาที่แข่ง ผมไม่ได้ติดงานอย่างอื่นพอดี ก็เลยลองลงแข่งรอบ audition เล่น ๆ แล้วก็พบว่า

โจทย์ง่ายมาก ทำ 1 ชม. เสร็จ ติดรอบระดับภาคชิลๆ :D

คลิป Teaser ของ Techjam 2018 — Regional Competition ภาคเหนือ

First Impression

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

หลังลงทะเบียนเสร็จแล้วทีมงานก็จะแจกไอเทมสุดพื้นฐาน 3 อย่าง นั่นก็คือ

• สติ๊กเกอร์ Squad กับหมายเลขทีมที่เอามาแปะตรงหน้า T-Shirt สวย ๆ ที่อุตส่าห์ใส่ไป กลัวคนอื่นจะไม่รู้ว่าอยู่ Squad ไหน
• สายรัดข้อมือ Code Squad ที่ติดกาวเหนียวเวอร์ ๆ
• กล่องขนมที่ประกอบไปด้วยขนมปังและน้ำผลไม้ในตำนาน

ภาพกระติกน้ำ Tomorrow Squad ในเพจครับ (ภาคกลางด้วย) ถ่ายเองไม่สวย ;-;

ส่วนอย่างสุดท้ายที่เรียกได้ว่าเป็นแรร์ไอเทมในงานนี้ก็คงไม่พ้นกระติกน้ำขนาดใหญ่ที่เขียนคำว่า Tomorrow Squad ติดไว้อย่างเท่ ซึ่งเอาออกไปใช้อวดคนอื่นนอกงานได้ด้วย อันนี้ของดีมากครับ ขอขอบคุณทาง KBTG ที่อุตส่าห์ลงทุนขนาดนี้ _/\_

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

หลังจากแนะนำสถานที่เสร็จสรรพแล้ว สิ่งที่ต้องทำต่อไปนั่นก็คือ… รอ! พอดีมาเช้าเกินไปเลยต้องนั่งรอไป 2 ชม. ยาว ๆ ไป D:

New Challengers Appeared!

จะให้รออยู่เฉย ๆ มันก็น่าเบื่อ ผมจึงถือโอกาสไปเดินทัวร์ในงานเล่น ๆ แล้วก็พบกับคนที่ไม่คิดว่าจะมาโผล่ในภาคเหนือ นั่นก็คือเพื่อนที่เพิ่งไปแข่ง IOI 2018 มาด้วยกันแล้วได้เหรียญเงิน O_O”

ยังไม่พอ เขามาพร้อมกับผู้แทน IOI 2016 ที่ได้เหรียญทองแดงอีกคนนึง รวมกันเป็น Team ↓↓↓ Second Place ↓↓↓ ตอนนี้คิดอะไรไม่ออกนอกจากอุทาน เยดเข้ ในใจละครับ ลาก่อนเงิน 30,000 บาท ลาก่อนรูปชนะเลิศแบบ solo ขึ้นเพจเท่ ๆ T_T

แต่นอกเหนือจากทีมผู้แทนแล้ว ก็ยังได้พบกับอีกทีมนึงที่ผมรู้จักดี นั่นก็คือ Team PlugFire ของท่านพี่ ChimengSoso กับเพื่อนพี่เขาอีกคนหนึ่ง ซึ่งทั้งคู่ก็เป็นเทพจาก CompSci มช. นั่นเอง

เห็นว่าช่วงนี้พี่แกกำลังทำแชนแนลสอนเขียนโปรแกรมใน YouTube อยู่ ว่าง ๆ ก็เข้าไปส่องและก็ subscribe กันหน่อยละกันนะครับ #ยังไม่ได้ค่าsponsor

CodeMeng

Setting the Rules of the Game

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

กรรมการอธิบายว่า การแข่งขันจะแบ่งออกเป็นสามรอบ คือ

1. Quickfire — รอบคิดเร็ว มีโจทย์มาให้ต้องตอบได้ภายในเวลาที่กำหนด (ประมาณ 20 นาที) โจทย์ทั้งหมด 5 ข้อ ข้อละ 4 คะแนน รวมเป็น 20 คะแนน
2. Ponder — รอบคิดวิเคราะห์ซึ่งจะคล้าย ๆ กับ Quickfire แต่จะมีเวลาให้มากถึง 5 นาที และก็สามารถใช้คอมพิวเตอร์ช่วยแก้โจทย์ได้ ทีมที่เสร็จเป็นทีมแรกจะได้ 7 คะแนน ทีมต่อ ๆ ไปก็ลดลงมาเหลือ 6, 5, 4, … มีโจทย์ 5 ข้อเช่นกัน ดังนั้นคะแนนมากที่สุดที่เป็นไปได้คือ 35 คะแนน
3. Coding — รอบเขียนโปรแกรมที่แท้จริง มีโจทย์มาให้สามข้อ ให้เขียนโปรแกรมที่รันผ่าน Test Case ต่าง ๆ ที่กำหนดไว้แต่ละข้อมีคะแนนให้ 15 คะแนน ดังนั้นคะแนนรวมมากสุดคือ 45 คะแนน

หลังจากแข่งเสร็จทั้งสามรอบแล้ว จะเอาคะแนนแต่ละรอบมารวมกันแล้วจัดอันดับ ถ้าคะแนนเท่ากันจะจัดอันดับตามเวลาที่ใช้ในรอบ Coding ซึ่งกรรมการยังไม่อธิบาย ณ ตอนนี้

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

ผลออกมาพบว่า Team ↓↓↓ Second Place ↓↓↓ ได้แข่งก่อนใน group แรก ส่วนทีมของผม (Team AquaBlitz11) กับ Team PlugFire แข่งใน group ที่สอง เพราะฉะนั้นก็ต้องนั่งรอกันไปอีกยาว ๆ

Let the Game Begin!

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

นับเป็นเรื่องน่าบังเอิญที่ทีมผมกับทีมพี่ชิเหม่งดันได้อยู่โพเดียมใกล้กันอีก O_O”

และแล้วการแข่งขันรอบแรกก็เริ่มต้นขึ้น…

Round 1 — Quickfire

ในการแข่งขันรอบ Quickfire กรรมการจะนำโจทย์ขึ้นบนจอขนาดใหญ่ที่อยู่ตรงกลางห้อง แล้วอ่านโจทย์ให้ฟัง หลังจากอ่านโจทย์เสร็จแล้ว จะให้เวลาทำโจทย์โดยโจทย์แต่ละข้อตั้งแต่ 5 วินาทีถึง 60 วินาที ขึ้นอยู่กับความยาก (แต่ในงานแข่งจริง ๆ เหมือนจะ 20–30 วินาทีทุกข้อ)

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

สองข้อแรกถือว่าอยู่ในระดับค่อนข้างง่าย เลยไม่มีปัญหาอะไร แต่ข้อที่ 3 กับข้อที่ 4 ผมพลาดหนักมากก็เลยทำให้เสียคะแนนสองข้อนี้ไป ส่วนข้อที่ 5 ที่ดูแทบจะเป็นไปไม่ได้ที่จะคิดในเวลา 20 วินาที ผมเดาคำตอบเอา แล้วก็ดันถูกพอดี O_O”

สรุป ตอนนี้มีคะแนนเก็บไว้แล้ว 12 คะแนนจากทั้งหมด 20 คะแนน

Round 2 — Ponder

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

ทีมที่ทำโจทย์เสร็จก่อน จะต้องรีบวิ่งมาหยิบธงตามลำดับตรงกลางห้อง แล้วกรรมการจะตรวจให้คะแนน โดยทีมแรกที่ถูกต้องจะได้ 7 คะแนน ทีมถัดมาได้ 6, 5, 4, 3, … ลงมาเรื่อย ๆ

สำหรับรอบนี้ เนื่องจากมีเวลาให้ 5 นาทีผมเลยรู้สึกอุ่นใจอยู่พอสมควร ผมเลือกเขียนโปรแกรมภาษา C++ ทั้ง 5 ข้อเพราะเป็นภาษาที่ผมคุ้นเคยที่สุด แต่เพื่อไม่ให้เสียเปรียบคนที่ใช้ภาษา Python ผมจึงได้เตรียม template code เอาไว้ประมาณร้อยกว่าบรรทัด เพื่อจะได้พิมพ์อะไรหลาย ๆ อย่างได้สั้นพอ ๆ กับภาษา Python จะได้ไม่เสียเวลา

ถึงอย่างไรก็ตาม เนื่องจากว่าผมแข่งแบบ solo จึงเสียเวลากับการตรวจโค้ดนานอยู่พอสมควร (กลัวบัค) เลยทำบางข้อได้ช้ากว่าคนอื่น สำหรับรอบนี้ ผมทำได้ไวสุด 3 ข้อ ส่วนอีก 2 ข้อได้อันดับ 2 เลยได้คะแนนแค่ 33 คะแนนจาก 35 คะแนน

หลังจากการแข่งขันสองรอบแรกเสร็จแล้ว กรรมการจึงปล่อยให้ผู้เข้าแข่งขันออกมาทานข้าวเที่ยงก่อน ส่วนช่วงบ่ายก็จะเป็นการแข่งขันในรอบ Coding ที่หลาย ๆ คนรอคอยนั่นเอง

แน่นอนว่าทันทีที่ผมออกมาจากห้อง ผมก็รีบตรงเข้าไปหา Team ↓↓↓ Second Place ↓↓↓ เพื่อถามคะแนน พบว่าทีมนั้นทำโจทย์รอบ Quickfire ได้ 4 ข้อ (ผมได้ 3 ข้อ) ส่วนรอบ Ponder ได้ 7 คะแนนทุกข้อ

วิธีเดียวที่ผมจะชนะทีมนี้คือต้องเอาชนะรอบ Coding ให้ได้ แต่จากที่สันนิษฐานไว้ว่าโจทย์รอบ Coding จะมีระดับความยากไม่เกินโจทย์ TOI คิดว่าคงเป็นไปไม่ได้ เพราะน่าจะได้คะแนน (เต็ม) เท่ากัน มันจบแล้วล่ะ ฮือออ T_T

กินข้าวแก้เครียดแป๊บ T_T

The Final Battle — Coding

The Rules

ในรอบนี้ แต่ละทีมจะต้องใช้โน้ตบุ๊คต่อเข้าระบบที่กรรมการเตรียมไว้ให้ เพื่อเข้าไปทำโจทย์ทั้งหมด 3 ข้อ โดยโจทย์แต่ละข้อจะถูกแบ่งออกเป็นสองส่วนคือ Small (6 คะแนน) กับ Large (9 คะแนน) ให้เวลาทำทั้งหมด 2 ชั่วโมง 30 นาที

ระหว่างการแข่งขันจะมี Scoreboard ให้ดูด้วย ยกเว้นตอนชั่วโมงสุดท้ายเท่านั้น (จะได้ลุ้น) และในกรณีที่คะแนนรวมเท่ากัน จะตัดสินจากเวลาที่ submit ข้อสุดท้ายผ่าน แต่เพื่อป้องกันการ submit มั่ว ๆ จะต้องบวกเพิ่มไป 10 นาทีทุกครั้งที่คำตอบผิด

กฎการแข่งขันคล้ายกับ Code Jam มาก แต่ไม่ต้องไปลุ้นว่า Large จะถูกหรือผิดตอนจบ contest เฉย ๆ ซึ่งก็ทำให้ผมดีใจมาก เพราะตอนแรกนึกว่าจะให้ submit ได้แค่ครั้งเดียวเหมือนตอน audition QwQ

นอกจากนี้ ระบบตรวจที่เอามาใช้คือระบบ DOMjudge ที่เอามาปรับแต่ง interface ใหม่ให้เป็นสีดำ-เขียวตาม theme ของ TechJam ซึ่งอันนี้ทำออกมาได้ดูดีมาก ๆ ครับ //ปรบมือ ๆ

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

Problem 1 — Max Perimeter

เมื่อเริ่มการแข่งขัน ผมจึงเปิดอ่านโจทย์ข้อแรกก่อนเป็นอย่างแรก โดยโจทย์มีใจความสรุปสั้น ๆ ว่า

มีแท่งไม้อยู่ N แท่ง แต่ละแท่งมีความยาวตามที่กำหนดให้ใน input ให้เลือกแท่งไม้มา 3 แท่ง ประกอบเป็นรูปสามเหลี่ยมที่มีพื้นที่มากกว่า 0 จงหาความยาวรอบรูปสามเหลี่ยมที่มากที่สุดที่เป็นไปได้ (Small: N ≤ 100, Large: N ≤ 200,000)

เมื่ออ่านโจทย์เสร็จก็รู้สึกดีใจนิด ๆ เพราะว่าโจทย์ข้อนี้คล้ายกับโจทย์ใน programming.in.th เป็นอย่างมาก สามารถแก้ได้ง่าย ๆ โดยการ sort ความยาวแท่งไม้จากน้อยไปมาก แล้วทดลองเลือกแท่งไม้ 3 อันที่อยู่ติด ๆ กันเพื่อเช็คว่าสามารถสร้างเป็นสามเหลี่ยมได้หรือไม่ (x+y >z)

ผ่านไปแค่ 2 นาที Team AquaBlitz11 ก็มีคะแนนขึ้นมาแล้ว นับว่าเป็นการเริ่มต้นที่ดี :D

Problem 2 — Shipping Dolls

หลังทำโจทย์ข้อแรกเสร็จ ผมจึงรีบมาอ่านโจทย์ข้อที่สองต่อทันที

มีตุ๊กตาอยู่ N ตัว แต่ละตัวมีน้ำหนักตามที่กำหนดให้ใน input ต้องการแพ็คตุ๊กตาทุกตัวใส่กล่องหรือไม่ก็ถุงกระสอบ โดยมีกฎดังนี้

- สามารถใช้กล่องกี่กล่องก็ได้ แต่ละกล่องจะรับน้ำหนักได้ไม่เกิน L หน่วย
- ใช้ถุงกระสอบได้แค่ถุงเดียวเท่านั้น ถุงนี้จะรับตุ๊กตาได้ไม่เกิน M ตัว
- หากตุ๊กตาตัวที่ s กับ t อยู่ในกล่องเดียวกัน ตุ๊กตาตัวที่ i ทุกตัวที่ s < i < t (ตุ๊กตาที่อยู่ระหว่างกลาง) จะต้องถูกบรรจุในกล่องใบเดียวกันด้วย หรือจะต้องถูกบรรจุลงในถุงกระสอบ

จงหาว่าจะต้องใช้กล่องทั้งหมดกี่ใบ (Small: N ≤ 250, Large: N ≤ 2,500)

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

solution ที่เขียนไปเป็น brute force solution โดยเลือกว่าจะเอาตุ๊กตาช่วงไหนออก (ช่วงความยาว M) แล้วลูปนำตุ๊กตาที่เหลือใส่กล่องแบบ greedy จากซ้ายไปขวา รวม Time Complexity เป็น O(N²) พอเขียนเสร็จ ส่งไปก็พบว่า… Wrong Answer

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

โชคดีที่ไม่ได้มีทีมผมคนเดียวที่พลาด เพราะใน scoreboard จะเห็นว่า Team ↓↓↓ Second Place ↓↓↓ ก็ได้ Wrong Answer ข้อนี้ไปครั้งหนึ่งเช่นกัน

แต่ในเมื่อเข้าใจโจทย์อย่างนี้แล้ว ก็ชัดเจนว่าโจทย์ข้อนี้เป็น Dynamic Programming แน่นอน ผมจึงคิดสูตรขึ้นมาได้ ดังนี้

นิยามให้ DP[i][j] = จำนวนกล่องที่น้อยที่สุดที่เป็นไปได้ เมื่อต้องแพ็คตุ๊กตาตัวที่ 1, 2, 3, …, i โดยอนุญาตให้นำตุ๊กตาใส่ถุงกระสอบได้แค่ j ตัวเท่านั้น

ส่วน recurrence เราจะสนใจการเลือกตุ๊กตาตัวท้าย ๆ (ใกล้ ๆ ตัวที่ i) ใส่กล่องใบเดียว โดยสังเกตว่า

• ในกรณีปกติ เราควรจะเลือกจำนวนตุ๊กตาให้มากที่สุดเท่าที่เป็นไปได้ที่น้ำหนักยังไม่เกิน L
• เราอาจจะเลือกนำตุ๊กตาบางตัวออกไปใส่ถุงกระสอบได้ (ลูปเลือกจำนวนตรงนี้ ต้องไม่เกิน j)โดยให้นำตัวที่น้ำหนักมาก ๆ ออกไปก่อน จะทำให้สามารถเพิ่มจำนวนตุ๊กตาที่พิจารณานำใส่กล่องได้
• แล้วบวกด้วยคำตอบ DP[x][y] เมื่อ x = ตำแหน่งตุ๊กตาที่ไม่ได้อยู่ในกล่องนี้, y = จำนวนตัวที่มีสิทธิ์นำใส่ถุงกระสอบที่เหลืออยู่

เนื่องจากว่าสูตรนี้มี O(N²) state แล้วเราจำเป็นต้องลูป O(N) ใน transition โดยจะต้องนำตุ๊กตาตัวมากสุดออกเสมอ (อาจใช้ priority queue ได้ใน O(log N)) รวมแล้วโปรแกรมจะรันใน O(N³ log N) ซึ่งผ่านแค่ Small เท่านั้น

ตอนแรกผมคิดว่าน่าจะหาวิธีที่ทำให้คำตอบของ DP[i][j+1] อ้างอิงจาก DP[i][j] ได้ แต่พอเขียนสูตรออกมาเป็นสัญลักษณ์ทางคณิตศาสตร์จริง ๆ ก็รู้สึกว่าน่าจะทำได้ยาก ผมจึงตัดสินใจย้ายไปทำโจทย์ข้อ 3 ก่อน

Problem 3 — Island Counting

กำหนดตารางขนาด N*M ให้ แต่ละช่องจะเป็นน้ำ (.) หรือดิน (#)

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

จงนับจำนวนเกาะในตารางที่กำหนดให้
(Small: N, M ≤ 300, Large: N, M ≤ 3,000)

เมื่ออ่านโจทย์ข้อนี้เสร็จ ก็รู้สึกอุ่นใจขึ้นมาหน่อยเพราะคิดว่าน่าจะเป็นโจทย์ Flood Fill บน grid graph ง่าย ๆ ทั่วไป ผมจึงรีบโค้ด solution ของผมดังนี้

Flood Fill (ภาพจาก Wikipedia)

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

คิดว่าน่าจะถูกแล้ว พอลองส่งไปดูก็ได้ Wrong Answer มาอีกตัวนึง

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

ใช้เวลาอยู่สักพักจึงตั้งสติได้แล้วลองคิด test case มั่ว ๆ ขึ้นมา ตั้งแต่เคสแรกที่คิดขึ้นมาเองได้ ก็พบจุดผิดแล้ว

test case นี้ควรตอบว่ามี 8 เกาะ แต่โปรแกรมผมดันตอบ 4 เพราะหลัง flood fill พื้นที่น้ำด้านนอก จะได้ตารางแบบนี้

แล้วพอลูปเพื่อหาตำแหน่งที่เป็นเกาะโดย flood fill พื้นดินและน้ำทุกครั้งที่เจอเกาะใหม่ โปรแกรมจะคิดว่าพื้นที่ดินกับน้ำตรงกลางทั้งหมดเป็นเกาะเดียวกัน (เกาะ A ตามตารางด้านล่างนี้)

นั่นแปลว่าแนวคิดการ fill น้ำและดินด้านในเพื่อป้องกันการนับเกาะด้านในซ้ำ ผิด! ผมจึงคิดไอเดียใหม่ได้ นั่นก็คือ

• ตอน fill จากขอบตารางเข้าไป ถ้าเจอตรงไหนที่เป็นดิน ให้จดตำแหน่งไว้ด้วยว่าเป็นตำแหน่งที่น่าสนใจ (เพราะฉะนั้น ดินตรงกลางด้านในจะไม่ถูกนับ)
• พอ fill เสร็จ ให้ fill พื้นที่ดินที่อยู่ติดกับตำแหน่งที่น่าสนใจแต่ละตำแหน่งแล้วนับจำนวน component (ไม่ต้อง fill ผ่านพื้นที่น้ำอีกแล้ว เพราะเรารู้ว่าเกาะตรงกลางด้านในจะไม่ถูกนับแน่ ๆ)

แต่เมื่อส่งไปก็ Wrong Answer อีก T_T

มาถึงตอนนี้ Team ↓↓↓ Second Place ↓↓↓ ทำข้อนี้ ได้คะแนนนำผมไปแล้ว ผมจึงกลับไปอ่านโจทย์อีกครั้ง เผื่อว่าเข้าใจโจทย์ผิดเหมือนข้อที่ผ่านมา

แล้วมันก็เป็นอย่างนั้นจริง ๆ ด้วย ผมเพิ่งเห็น Sample Test Case 2 ตามนี้

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

พอรู้ตัวอย่างนี้แล้วก็เครียดเลย เพราะโจทย์ข้อนี้ดูยากกว่าที่คิดมาก หลังจากนั่งคิดวิธีแก้ไปประมาณ 2–3 นาทีก็เพิ่งนึกได้ว่า เฮ้ย เอาจริง ๆ วิธีล่าสุดก็ถูกแล้ว แค่ตอน fill พื้นที่ด้านนอก ให้มัน fill เฉียงได้ด้วยเท่านั้นเอง (เพราะฉะนั้นพื้นที่น้ำด้านในก็จะถือว่าเป็นพื้นที่เดียวกับขอบตารางด้านนอก)

แก้เพียงแค่นั้นก็ได้ผลลัพธ์ออกมาเป็น Correct สีเขียวที่อุตส่าห์รอมานานแสนนาน ข้อนี้ไม่ได้ยากอะไรเลย สะเพร่าเอง T_T

Revisiting Problem 2 — Shipping Dolls

ในตอนแรก สูตร Dynamic Programming ที่ผมคิดไว้ จำเป็นต้องหาวิธีลดเวลาจาก O(N³ log N) ให้เหลือ O(N²) หรือ O(N² log N) แต่เมื่อดูดี ๆ แล้ว คิดว่าน่าจะไม่มีวิธีง่าย ๆ ดังนั้นผมจึงต้องเปลี่ยนนิยาม DP ใหม่

แผนในหัวผมก็คือ น่าจะหาวิธีนิยาม DP ยังไงก็ได้ให้มันมีคุณสมบัติ monotonicity ของชอยส์ใน recurrence แล้วใช้ divide & conquer optimization แก้เอา แต่ความรู้สึกอีกอย่างนึงคือ

“โจทย์มันไม่น่าต้องใช้เทคนิคยากขนาดนี้”

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

นิยามให้ DP[i][j] = จำนวนตัวที่จะต้องนำใส่กระสอบที่น้อยสุดที่เป็นไปได้ เมื่อต้องการแพ็คตุ๊กตาตัวที่ 1 ถึง j ใส่กล่องไม่เกิน i กล่อง

เมื่อนิยามอย่างนี้แล้ว คำตอบสุดท้ายคือค่า x น้อยสุดที่เป็นไปได้ที่ DP[x][N] ≤ M (นำใส่ x กล่องได้โดยต้องนำตุ๊กตาใส่กระสอบไม่เกิน M ตัว)

ส่วน recurrence ก็สามารถคิดได้ง่ายขึ้น เพราะรูปแบบสูตรจะคล้ายกับพวก partitioning problem (แบ่ง array ความยาว N ออกเป็น K ช่วง) นั่นคือ เราต้องลูปตำแหน่ง 1 ≤ k ≤ j เพื่อหาว่าควรให้ช่วงสุดท้าย (ช่วง [k..j]) เป็นช่วงใดจึงจะได้คำตอบดีสุด นั่นคือ

DP[i][j] = min(DP[i-1][k-1] + F(k, j); 1 ≤ k ≤ j)

โดย F(k, j) = จำนวนตุ๊กตาน้อยสุดที่ต้องนำใส่กระสอบ (สนใจเฉพาะตัวที่ k ถึง j เท่านั้น) เพื่อให้ผลรวม ≤ L ซึ่งส่วนนี้เราสามารถ precompute ไว้ได้ใน O(N² log N) (fix จุดเริ่มต้นแล้วไล่เพิ่มผลรวมไปทางขวา หากผลรวมเกินก็ให้นำตัวมากสุดออกจาก priority queue)

ส่วนสูตร DP นี้ ถึงแม้ว่าจะเป็นสูตร O(N³) แต่จากข้อสันนิษฐานว่า

• ถ้าให้ตำแหน่ง k ที่ดีที่สุดของ DP[i][j] เป็น K[i][j] จะพบว่า K[i][j] ≤ K[i][j+1] สำหรับทุก j ที่ 1 ≤ j < N (monotonicity)

จากคุณสมบัตินี้ เราสามารถใช้ divide & conquer optimization ลดเวลาให้เหลือ O(N² log N) ได้ ซึ่งก็จะทำให้ได้คะแนนในโจทย์ข้อนี้พอดี

แน่นอนว่าชีวิตมันไม่ได้ง่ายขนาดนั้น

เพราะเมื่อผมส่งโค้ดไปแล้ว พบว่ากลับได้คำตอบมาเป็น Wrong Answer ซะงั้น O_O ผมจึงลองปรับโค้ดกลับเป็นโค้ดเวอร์ชัน O(N³) ที่ไม่ได้ใช้คุณสมบัตินี้ดูแล้ว แล้วให้โปรแกรมมันเช็คคุณสมบัตินี้ด้วยตัวเองดู พบว่า

เอาจริง ๆ แล้วคุณสมบัตินี้มันผิดตั้งแต่ Sample Test Case แล้วล่ะ T_T

แต่ไม่เป็นไร อย่างน้อยไหน ๆ ก็ปรับโค้ดแล้ว ผมจึงส่งโค้ด O(N³) ไปตรวจในระบบ เลยได้ Correct ใน Small Test Set มาให้อุ่นใจนิดนึง หลังจากนั้นไม่นาน Team ↓↓↓ Second Place ↓↓↓ ก็ submit solution คล้าย ๆ กัน ทำให้คะแนนผมตกลงมาเป็นอันดับ 2 อีกครั้ง (เอาจริง ๆ คะแนนเท่ากัน แต่ข้อ 3 ผม submit ผิดหลายครั้งเลยโดนบวก penalty เยอะกว่า)

หลังจากนั่งงมไปสักพัก พยายามคิดสูตร DP ต่าง ๆ มากมายที่น่าจะหาวิธี optimize ได้ ผมก็นึกขึ้นได้ว่า เฮ้ย เอาจริง ๆ เราไม่จำเป็นต้องใช้คุณสมบัตินี้เต็มที่ก็ได้ อาจจะอนุญาตให้มันเขยิบ ๆ ได้นิดนึง เช่น ถ้าสมมุติเรารู้ว่า K[i][j] ควรมีค่าอยู่ระหว่าง x กับ y ก็ลองขยายช่วงให้มันเป็น x-10 ถึง y+10 ดู

เอาจริง ๆ ก็ไม่คิดว่ามันจะถูกแหละ แต่พอส่งไป…

Correct

ผ่านแบบงง ๆ ตอนเหลือเวลาประมาณ 30–40 นาทีก่อนจบการแข่งขัน (Scoreboard โดน freeze ไปแล้ว ทีมอื่นเลยไม่เห็นว่าผ่าน)

แต่นี่ไม่ใช่ Correct ที่รู้สึกดีเท่าไหร่นัก เพราะยังรู้สึกไม่ค่อย convinced ว่าวิธีนี้ใช้ได้ทุกกรณีจริง (ถึงแม้จะผ่าน test case ในงานแข่งแล้วก็เถอะ) ผมเลยใช้เวลาที่เหลือพยายามนั่งคิดวิธีไปเรื่อย ๆ แต่ก็คิดไม่ออก

(เอาจริง ๆ แล้วข้อนี้มี solution O(N²) ง่าย ๆ อยู่ กำหนดให้ DP[i][j] = จำนวนกล่อง และน้ำหนักในกล่องสุดท้ายที่น้อยที่สุดที่เป็นไปได้ เมื่อแพ็คตุ๊กตาที่ 1 ถึง i โดยนำใส่ถุงกระสอบไม่เกิน j ตัว — ส่วน recurrence ก็แค่เลือกว่าจะนำตัวที่ i ใส่กระสอบ หรือว่าจะเอาไปรวมกับตัวก่อน ๆ หน้า ถ้าน้ำหนักเกินให้เพิ่มจำนวนกล่อง)

ในขณะเดียวกัน ช่วงครึ่ง ชม. สุดท้ายเป็นช่วงที่ทรมาณที่สุด เพราะผมต้องคอยลุ้นว่า Team ↓↓↓ Second Place ↓↓↓ จะผ่านหรือไม่ผ่าน ถ้าเขาผ่านผมจะได้ที่ 2 แต่ถ้าเขาไม่ผ่านผมจะได้ที่ 1

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

ทำผ่านกันแล้วสินะ… T_T

The End

หลังจบ contest แล้ว ผมจึงลุกขึ้นไปคุยกับ Team ↓↓↓ Second Place ↓↓↓ ว่าทีมนั้นใช้วิธีไหนจึงผ่านโจทย์ข้อนี้ได้ พบว่า…

เยดเข้ ใช้วิธีเกรียนเหมือนกันเลยนี่หว่า O_O”

แต่อย่างน้อยการแข่งขันในครั้งนี้ก็ไม่ใช่การแข่งขันง่าย ๆ อย่างที่คิดไว้ตอนแรก การมาเยือนของทีมมหาเทพช่วยให้การแข่งขันครั้งนี้สนุกขึ้นเยอะ คิดว่าคำที่เหมาะสมที่สุดตอนนี้ก็คงจะเป็น Good game :D แหละนะ

ส่วน Team PlugFire รุ่นพี่ผมจาก มช. บอกว่าข้อที่ 2 “ขี้เกียจทำ เพราะไม่ชอบอยู่ที่ 1 เดี๋ยวได้หน้าลงเพจ” แต่ดูเหมือนโชคจะไม่เข้าข้าง เพราะทีมอื่นทำคะแนนข้อนี้ไม่ได้เช่นกัน ถ้าคะแนนรอบ Quickfire และ Ponder ดีก็คงจะได้ขึ้นหน้าเพจอยู่ดีแหละนะ :D

Closing Ceremony

ในส่วนของพิธีปิด จะเป็นการมอบเกียรติบัตรให้กับผู้เข้าแข่งขันแต่ละคน ทั้งใน Code Squad และ Data Squad แล้วจึงมอบรางวัลให้กับ Top 3 ของแต่ละ Squad โดยมีรางวัลดังนี้

• โล่รางวัลที่มีสัญลักษณ์ Squad กับหมายเลขอันดับประดับอยู่อย่างเวอร์วังอลังการสวยงาม
• (ป้าย) เงินรางวัล โดยอันดับ 1, 2, 3 จะได้เงินรางวัล 30K, 20K, 10K ตามลำดับ
• Badge ประจำ Squad ที่เอาไว้เย็บติดเสื้อหรือกระเป๋า

ซึ่งตามที่คาดไว้ ในสาย Code Squad พบว่าทีมที่ผมรู้จักและพูดถึงมาตลอดบล็อกนี้ ได้รางวัลทั้งสามทีมเลย นั่นก็คือ…

• อันดับ 3 — Team PlugFire ทีมของพี่ ๆ จาก มช. นั่นเอง
• อันดับ 2 — Team AquaBlitz11 ทีม solo ของผมเอง
• อันดับ 1 — Team ↓↓↓ Second Place ↓↓↓ ทีมมหาเทพผู้แทน IOI ที่รู้อยู่แล้วว่าได้ที่ 1 แน่นอน _/\_ #กราบ

รับรางวัลเสร็จแล้ว สุดท้ายก็ถ่ายรูปรวมเก็บเป็นที่ระลึก ทั้งรูปผู้ชนะแต่ละ Squad และรูปผู้ชนะทุก Squad เลย ถือว่าเป็นบทสรุปของการแข่งขัน TechJam 2018 Regional Competition ในภาคเหนือแล้วนั่นเองครับ ที่เหลือก็แค่รอประกาศผลเข้าแข่งระดับประเทศเพียงเท่านั้น~

Final Words

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

ได้ยินมาว่าเดิม TechJam 2017 จัดแค่เพียงภาคกลางเท่านั้น ส่วน TechJam 2018 เป็นครั้งแรกที่ขยายมาจัดในภาคอื่น ๆ รวมถึงภาคเหนือด้วย ผมจึงได้มีโอกาสเข้าร่วมการแข่งขันเขียนโปรแกรมที่ลงทุนจัดจริงจังขนาดนี้ ไม่ว่าจะเป็นเรื่องเหล่า staff ที่เผลอ ๆ อาจจะมีจำนวนเยอะกว่าผู้เข้าแข่งขัน O_O” เรื่องอาหาร ของที่ระลึก หรือแม้กระทั่งบรรยากาศที่หาไม่ได้ในงานอื่นอีกแล้ว

ผมขอขอบคุณทาง KBTG และทางทีมงานที่จัดการแข่งขันดี ๆ อย่าง TechJam 2018 ไว้ ณ ที่นี้ด้วยนะครับ หวังว่าจะมีการแข่งขันนี้ที่พัฒนาต่อไปเรื่อย ๆ ในอนาคต เป็นเวทีแสดงศักยภาพ และเป็นแหล่งจุดประกายสร้างความรู้ความสามารถให้กับเหล่า developer ในประเทศไทยต่อไปครับ

ผู้เข้าแข่งขัน TechJam 2018 Regional Competition ภาคเหนือทั้งหมด