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 แต่พอยกเลิกการใช้เทมเพลทรู้สึกว่าจะเขียนได้ไวขึ้นอีก

Content is King

*([first published on Facebook and Google+](https://plus.google.com/u/1/108003073552145737788/posts/BounCteizkv))*

ผมไม่เชื่อคำว่า content is king ดูอย่าง Facebook Twitter บริษัทเค้ามี content อะไรของตัวเองบ้างล่ะ?

สิ่งที่ผมเชื่อคือ system is king

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

ถามว่าเว็บที่ Content is King มีมั้ย มีจริง อย่าง Blognone นี่ไง ผมก็อ่าน
แต่มันอ่านแล้วก็ปิดแท็บไป มันก็เหมือนเวลาเขียนสเตตัสแล้วผ่านตาเพื่อนในเฟสเป็นร้อย แต่ไม่มีใครกด like คิดว่าประสบความสำเร็จมั้ยล่ะแบบนี้?

แต่ก็ไม่ได้หมายความว่า content 0 เลยจะรอด Mark Zuckerberg ก็อัพสเตตัสของเขา อัพรูปของเขา นั่นคือมันทำให้เกิด Network effect แต่พอถึงจุดนึง เค้าจะเริ่มหายไปจากหน้าจอของคนส่วนมาก ตอนนี้หลายๆ คน ไม่มี Larry Page, Mark Zuckerberg อยู่ใน wall อีกแล้ว เพราะเค้าก็เป็นผู้ใช้คนหนึ่งในระบบ ไม่ใช่ผู้สร้าง content ให้กับ Facebook หรือ Google+ อีกต่อไป

คำว่า content is king คงจะมาจากยุค Web 1.0