on Google Code Jam Qualification Round 2012

ผ่านไปแล้วนะครับ กับรอบคัดเลือก Code Jam 2012 ไหนๆ ดองมานานจนลืมแล้วเล่าสักหน่อยดีกว่า

ก็ วันนั้นผมก็ตั้งปลุกตัวเองไว้ว่าตีห้าครึ่ง พอหกโมงเช้าที่เริ่มแข่งแบบว่าง่วงมาก แต่ก็อ่านโจทย์สักหน่อย

เจอข้อแรกไป… Speaking in Tongues โจทย์มีอยู่ว่าให้ข้อความที่ทำการเข้ารหัสแบบ 1:1 แล้ว คือสมมุติว่า a แปลงเป็น z ก็จะเป็น z เสมอ คราวนี้ล่ะผมนอนต่อไม่ได้ละ เลยลงมือเผาๆ ให้เสร็จจะได้นอน

คือ โจทย์จะใช้วิธีประมาณว่าให้ลองเดาจากโจทย์ตัวอย่างดู ซึ่งผมก็ขี้เกียจทำ map table เลยเขียนโปรแกรมให้มันวิเคราะห์โจทย์อัตโนมัติไปเลยโดยเอาข้อตัวอย่างและคำตอบใส่ไป มันก็จะสร้าง map table มา แล้วก็ตอบ ทีนี้ปรากฎว่า**โดนดักควาย** ว่ามันไม่มีตัว q ในโจทย์ แต่กว่าจะรู้ก็ตอนขอ test case แล้ว

ทีนี้ผมก็เดาละ z มันได้ q (ถ้าผมจำไม่ผิดนะ) งั้นผมมั่ว q->z เลยแล้วกัน แล้วก็ใส่ใน map table ไว้ ปรากฎว่าผิด ผมลองดูจาก input มันมีข้อนึงไล่ a-z อยู่แล้ว ก็แค่ดูว่าตัว q มันเป็นตัวลำดับไหน เลยให้มันแทน q ด้วย ! แต่ผมไม่เจอ ! อีกแล้ว… ก็เลยช่างมัน ผ่านแล้วมั้ง ส่ง!

ที่ไหนได้ล่ะครับ ก็ผมเซตไปแล้วไง q->z ผมก็เลยส่งคำตอบไปผิดๆ พอมาไล่อีกที อ้าว map table มันเซตไว้แล้ว ก็เสียค่าโง่ไป

หลังจากนั้นแล้ว… นอนดีกว่า

———–

บ่ายสองผมตื่นมาทำต่อ เริ่มที่ข้อ recycle ที่ดูจะง่ายกว่า dance โจทย์มีอยู่ว่าจำนวน n เนี่ย สามารถตัดตัวเลขจากด้านหลังไปใส่ด้านหน้าได้ จะตัดกี่ตัวก็ได้ เช่นตัวเลข 12345 มันจะได้ 51234, 45123, 34512, 23451 คำถามคือ ในช่วงที่กำหนด มีตัวเลขแบบนี้กี่ชุด ถ้าตัวเลขแรกเป็นตัวเดียวกัน ตัวเลขที่เกิดจากการสลับแล้วซ้ำกันจะไม่นับ

โอเค วิธีคิดผมก็ตามโจทย์เป๊ะ ตัด string จากด้านหลังไป ตั้งแต่ หนึ่งตัว สองตัว ไปเรื่อยๆ จนถึง n-1 แล้วก็วนลูปในช่วงที่กำหนดมา โชคดีว่ากรณีซ้ำไม่นับอยู่ใน example case ผมก็เลยเจอบั๊ก แล้วก็นั่งไล่ดูไปทีละตัวเลขของข้อนั้นเลยว่ามีตรงไหนทำไมนับเกิน ดูไปสักพักค่อยแบบว่า อ้อ ลืมกรณีซ้ำ ฉะนั้นผมก็เลยให้มันเซฟทุก combination ที่เป็นไปได้ทั้งหมดลง array!

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

ใครว่าการมีความหวังน่ะเป็นสิ่งที่ผิด ฉันจะตอบกลับไปว่าไม่ใช่เลย

— Kaname Madoka

————-

มาถึงข้อสุดท้ายครับคือ Dance โจทย์ประมาณว่ามีกรรมการสามคนให้คะแนน ซึ่งแต่ละคนจะให้คะแนนที่ min,max ห่างกันไม่เกิน 1 แต่จะมีกรณีพิเศษที่ห่างกันไม่เกิน 2 โจทย์ถามว่า มีการแสดงจำนวนครั้งเท่านี้ มีคะแนนรวมของแต่ละคนเท่านี้ และมีจำนวนครั้งที่ได้คะแนนพิเศษเท่านี้ ถามว่า มีกี่ครั้งที่ได้คะแนนเกินที่กำหนด

วิธีคิดข้อนี้ผมใช้ generator คิด โดยไล่กรณีคะแนนที่เป็นไปได้ทั้งหมดจาก 1-10 ซึ่งพบว่าคะแนนของกรรมการคนอื่นจะเป็นดังนี้ (สมมุติว่าได้ 1 คะแนน): [1, 1, 1], [1, 0, 0], [1, 1, 0] และกรณีพิเศษคือ [1, 1, -1], [1, -1, -1], [1, 0, -1]

ผมพบว่าการให้โปรแกรมลองเดา โดยพยายามหลีกเลี่ยงกรณีที่ได้คะแนนกรณีพิเศษเท่าที่เป็นไปได้โปรแกรมก็จะสามารถทำโจทย์ได้อย่างถูกต้องแล้ว แต่พอรันเทสเคสเจอปัญหาคือ กรณี 1 และ 0 มันคิดออกมาเป็นคะแนนติดลบ ก็ต้องแก้โดย hardcode ไปว่าคะแนนรวมได้ 0 ให้ตอบ [0,0,0] 1 ตอบ [1,0,0] เท่านั้น

สำหรับข้อยากอันนี้ใช้เวลารันพอๆ กับข้อง่ายครับ

——————-

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

One thought on “on Google Code Jam Qualification Round 2012”

  1. ข้อ dance ใช้ reduce lambda ทำไมอะ? ไม่ใช่ว่า sum เป็น built-in อยู่แล้วเร๊อะ

    ปล. ข้อ recycle ปรากฏว่าใช้ pypy แล้ว แทบไม่เห็นความต่างระหว่างการ shift เลขแบบ math กับแบบ str เลยแฮะ

Comments are closed.