Codejam 2013 Qualification Round

ก็ผ่านไปแล้วนะครับกับ Codejam 2013 รอบคัดเลือก ปีนี้กฎค่อนข้างโหดคือ 35 คะแนน ซึ่งปกติคะแนนผมก็น่าจะเกินแหละแต่โจทย์มันยากขึ้นด้วยก็เลยต้องระวังตัวหน่อยๆ

# Tic Tac Toe Tomek

เกม XO แบบสี่แถวครับ ให้กระดานมาถามว่าใครชนะ ยังเล่นไม่จบ หรือ เสมอ

โค้ดผมใช้ [cjlib](https://github.com/whs/cjlib) นะครับ เพิ่ง open source เมื่อวาน เขียนไว้ตั้งแต่โค้ดจมรอบซ้อมมือ เอาไว้รับ input และข้อไหนจะโหดก็ใช้ multiprocessing ขยายให้ใช้ CPU 8 core ให้คุ้มได้ (ผมเซต default mode เป็น thread ด้วย แต่เอาจริงๆ ก็ไม่ค่อยช่วยเท่าไรเพราะติด global interpreter lock อยู่ดี)

ข้อนี้โปรแกรมมันหา​ “XXX” “OOO” + “T” ในแถวนึง ถ้าเจอก็คือชนะ ถ้าไม่เจอก็พลิกกระดานหาอีกที แล้วก็ลองเช็คทะแยง นี่ถ้ามันเอา XXX สามตัวนี่ทะแยงเขียนกันสนุกเลยครับ

Algorithm หมุนกระดาน ผมตั้งใจจะหมุนตามเข็มนะครับ แต่มันดันหมุนแบบ flip horizontal + flip vertical ซึ่งก็โอเคไม่มีปัญหาใช้ได้เหมือนกัน

ปรากฏว่า ผมพลาดข้อ Large ไปได้ยังไงไม่รู้ พอเช็คกับโปรแกรมคนอื่นมาเจอ OOTO *speechless*

ปกติในรอบคัดเลือก Codejam ตัวเทสเคสจะช่วยเราดักบัีกพวกนี้นะ แต่ปีนี้ไม่ช่วยกันเลย

# Lawnmover

[ถ้าชีวิตกูต้องเจอเรื่องแบบนี้ กูไปตัดหญ้าดีกว่า](https://www.facebook.com/pages/%E0%B8%96%E0%B9%89%E0%B8%B2%E0%B8%8A%E0%B8%B5%E0%B8%A7%E0%B8%B4%E0%B8%95%E0%B8%95%E0%B8%A3%E0%B8%B9%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7%E0%B8%A7-%E0%B8%95%E0%B9%89%E0%B8%AD%E0%B8%87%E0%B9%80%E0%B8%88%E0%B8%AD%E0%B9%80%E0%B8%A3%E0%B8%B7%E0%B9%88%E0%B8%AD%E0%B8%87%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%99%E0%B8%B5%E0%B9%89%E0%B8%99%E0%B8%B0-%E0%B8%95%E0%B8%A3%E0%B8%B9%E0%B9%84%E0%B8%9B%E0%B8%95%E0%B8%B1%E0%B8%94%E0%B8%AD%E0%B9%89%E0%B8%AD%E0%B8%A2%E0%B8%94%E0%B8%B5%E0%B8%81%E0%B8%A7%E0%B9%88%E0%B8%B2/288729314481614) แต่เนื่องจากโปรแกรมเมอร์ดันมีเครื่องตัดหญ้าขั้นเทพครับกดทีเดียวเกรียนทั้งแถบ ส่วนคนตัดดันอยากตัดเป็นรูปพิสดารอีกต่างหาก เลยต้องมาดูกันว่าเครื่องตัดหญ้าที่ตัดเกรียนทั้งแถบจะทำรูปนั้นได้มั้ย

บางคนเค้ามี algorithm ที่ solve ได้เลยว่ามันตัดได้มั้ย แต่อย่างผมแล้วต้องบอกวิธีตัดได้ด้วยครับ ก็เลยใช้วิธีหาหญ้าสูงที่สุดที่ยังไม่ได้ตัด (`notFinishedList` จะทำให้แถวที่ตัดแล้วเป็น 0 เพื่อไม่ให้ `max` ไปเจอแถวนั้น จริงๆ ผมใช้ `max` มาตรฐานก็ได้ แต่เขียน myMax ไว้ตอนใช้ algorithm อีกอันที่ลบไปเลยแล้วเลยลืมเปลี่ยน) พอเจอแถวที่ไม่ได้ตัดแล้วก็ไถแถวนั้นให้สูงเท่่าที่ต้องการ แล้วก็ไถไปเรื่อยๆ ทั้งสองแนว

สังเกตฟังก์ชั่น `cutX`,`cutY` นะครับ `cutY` จะตัดไปในแนวแกน x ส่วน `cutX` ตัดไปในแนวแกน y เพราะชื่อฟังก์ชั่นบอกว่า input เป็น x หรือ y ครับ

จริงๆ ถ้าเขียนตัวหมุนกระดานได้แล้วผมใช้วิธีหมุนน่าจะไวกว่าเขียนแยก `cutX`/`cutY` แต่ข้อนี้เพิ่งตื่น

ข้อนี้ตอนแรกดูเผินๆ เหมือนจะยากที่สุด แต่เอาจริงๆ แล้วง่ายกว่าข้อถัดไปอีกครับ ตอนแรกเกือบไม่ทำแล้ว ถ้าไม่ทำนี่ตกรอบไปแล้ว :/

# palindrome

ข้อนี้ผมเขียนใหม่นะครับ ของเดิมไปโหลดจาก codejam ได้ ผมไม่ได้เซฟไว้

โจทย์ข้อนี้คือให้หาปริมาณของจำนวนที่เป็นพาลินโดรม และถอดรูทได้พาลินโดรมเช่นกัน (พาลินโดรมคือเลขที่อ่านจากหน้าหลังได้เหมือนกัน รวมถึงเลข 0-9 ทุกจำนวนด้วย เช่น 121 1441 400080004)

ข้อนี้เสียดาย Large-1 มากครับ ผมเพิ่งรู้ว่า Large ลองได้รอบเดียวแล้วจะล็อค ไม่งั้นคงได้คะแนนไปแล้ว

ตัวโปรแกรมที่ผมใช้ทำ small นั้นก็ไม่ยากครับ วิ่งจาก start – end ทีละตัวแล้วเช็คเงื่อนไข แต่พอข้อ large เลยมาใช้วิธีเขียน palindrome generator แทน (เขียนบนมอเตอร์เวย์ด้วย ^^)

ต่อมาผมเห็น @icez ลอง large-2 ก็เลยทำมั่ง​ โดยใช้วิธีที๋โคตรโกงที่สุดคือ เนื่องจากว่า palindrome มันสามารถรู้ล่วงหน้าได้ก็เลยเขียน offline generator ตั้งแต่ 1-1E100 รันไปตั้งแต่เที่ยงยันบ่ายสาม แต่โปรแกรมดันค้างซะอีก (เหมือนจะ overflow มั้ง ผมไม่ได้ debug ดู)

ก็คือ save-palins.py จะรัน fas.py (จากด้านบนที่ผมใช้แก้โจทย์) เสร็จแล้วผมเซฟลง file ชื่อ palins แล้วก็ fas-cache.py จะรันดูว่าใน range ที่กำหนดมีจำนวนในไฟล์ palins กี่จำนวน

แน่นอนว่าผิดครับ เพราะ 4000000008000000004 ไม่อยู่ในช่วงน้อยของจำนวนใดๆ ใน large input 2 เลย TT มันต้อง gen เยอะกว่านี้

(อันนี้ผมเขียนรีบไปหน่อย จริงๆผมควรตัดช่วง 1E100 เป็นช่วงย่อยๆ แล้วใช้ TaskRunner แยกกันไป gen palins ออกมา จะได้กระจาย 8 core ได้เต็มที่)

# Treasure

ข้อนี้คือเราจะมีกุญแจชนิดต่างๆ อยู่ตามที่กำหนด และเรารู้ว่าในหีบแต่ละใบใช้กุญแจชนิดไหนเปิด และมีกุญแจชนิดใดอยู่ข้างใน ถามว่าต้องเปิดหีบอย่างไรถึงจะเปิดได้ครบ​ (ถ้ามีวิธี)

ข้อนี้ดูน่าจะเป็นทฤษฎีกราฟครับ ผมงงกับเรื่องนี้คือโรงเรียนผมไม่มีสอน แต่โรงเรียนกวดวิชามีให้ลง ผมก็เคยลงแต่ลืมไปหมดแล้ว (ก็โรงเรียนไม่ได้สอบเลยอะ) และมันไม่มีเรื่องกราฟที่มีน้ำหนักขอบ

โปรแกรมแนวๆ นี้เคยลองกับโจทย์อีกข้อนึงที่มันชื่อหอฝึกยุทธครับ จำไม่ได้แต่เป็นโจทย์ภาษาไทย วิธีคิดก็คือ left-first search ลองมันทั้งหมดโดยไต่จากด้านซ้ายไปก่อน (โจทย์บังคับด้วยการบอกว่าต้องเอาเลขน้อยขึ้นก่อน)

ปรากฏว่ารัน small ไม่ทันครับ (เพิ่งเคยเจอครั้งแรกที่แก้ได้แล้วรัน small ไม่ทัน) และใน scoreboard ผมก็ไม่มีใครทันเลย

——-

สรุปคือไม่ได้ใช้ algorithm อะไรทั้งนั้นล่ะครับ คิดมือยังไงผมก็ทำแบบนั้นนี่แหละ แต่ optimize for multicore เต็มเหนี่ยว อิอิ

รอบนี้เข้ารอบด้วย 60 คะแนน, 14:37:06 (ถ้าไม่ทำ C-large + B ผมคงได้เวลาสองสามชั่วโมง แต่ตกรอบ น่าจะเอา B ไปทำก่อน C), Rank 11121