Google Codejam 2016 Qualification Round

ปีนี้ใช้คอมใหม่ (ยังไม่ได้บล็อคเรื่องคอมใหม่สักที) ไม่ได้จัดอุปกรณ์ต่างๆ ที่สะสมไว้ให้เรียบร้อย ก็เลยต้องเริ่มจาก 0 และด้วยคิดว่า cjlib runner มันไม่จำเป็น มันเป็น overhead ก็เลยมีความคิดว่า เออ ลองเขียนเป็น C++ ดูดีกว่า น่าจะสนุก

Counting sheep

โจทย์ข้อนี้คือให้ N มา แล้วให้นับตั้งแต่ N, 2N, 3N, 4N, … โดยแต่ละครั้งให้จดตัวเลขในแต่ละหลักไว้ด้วย ถ้าเลขที่จดมีครบ 0-9 เมื่อไรให้คืนค่า xN ออกมา

ข้อนี้พบว่าพอเป็น C++ แล้วมันก็บังคับวิธีคิดเราอีกแบบ คือในลูปบรรทัดที่ 19 ถ้าเป็น Python เราจะ cast เป็น string แล้ววน ซึ่งมันเข้าใจง่ายกว่าการใช้ int (ที่ต้องมีบรรทัด 20 + 23 ให้อ่านแล้วต้องตีความ)

พบว่า cin ก็อ่าน input ง่ายดีนะ

Revenge of the Pancakes

โจทย์ข้อนี้ให้ string --+- มา แล้วให้ทำให้เป็น ++++ ทั้งหมด โดยใช้วิธีกลับเครื่องหมายทุกตัวตั้งแต่ตัวที่ 0 – n ได้ เช่น n = 2 ก็จะกลายเป็น ++-+

ที่สงสัยคือวิธีคิดเราง่ายมาก แต่ content analysis กลับคิดอะไรยากมากจนเรางงว่าวิธีเรามันผิดในทางคณิตศาสตร์หรือยังไง runtime ที่ใช้รันข้อ large เราก็แค่ 0.003s ด้วย

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

ครั้งที่ n (0-index) Output
เริ่ม --+-
1 3 ++-+
2 2 --++
3 1 ++++

ข้อนี้พบปัญหากับ cin นิดหน่อย คือมันไม่อ่าน \n เข้ามา ทำให้ต้องมาอ่านทิ้งอีกในบรรทัดที่ 49

Coin Jam

ข้อนี้จะใช้ C++ แล้วก็พบว่าใช้ itertools น่าจะไวกว่า ก็เลยจัด itertools + mathapi ตามสไตล์เดิมมา

ข้อนี้ผมก็ใช้วิธีตรงๆ โง่ๆ นี่แหละครับ

  1. Generate ตัวเลขมาก่อน โดยใช้ itertools.product('01', repeat=n-2) สร้างตรงกลางมา แล้วเอา 1 ประกบหน้าหลังตามที่โจทย์กำหนดว่าต้องขึ้นต้นและลงท้ายด้วย 1 ตรงนี้ดีที่ itertools สร้างเป็น tuple ออกมาทำให้มัน generate กรณีที่มี 0 นำได้ไม่มีปัญหา
  2. Cast และ cache เป็นเลขฐานต่างๆ ตั้งแต่ 2-10
  3. เช็คว่าเลขแต่ละตัวเป็น prime number ไหม ตรงนี้ใช้ mathapi เลย ง่ายและไวดี
  4. ถ้าใช่ก็ให้ mathapi หา factor แล้วตอบ

โค้ดที่เห็นนี่ optimize ไปนิดหน่อยละครับ แต่ก็ไม่ต่างกับเดิมมากนัก

ปัญหาของข้อยากคือ ผมก็ไม่เอะใจว่ามันให้ข้อยากมากแล้ว คือโจทย์ก็เขียนนะว่าไฟล์รับเข้าให้มาหมดแล้ว แต่ผมก็เห็นแค่ของ small ไม่เห็น large เลยนึกว่าไม่มี ปรากฏว่ามันให้เป็นตัวเลขมาแล้วไปเขียนไฟล์เอง ก็เลยไม่ได้ลองรันดู พอรันดูจริงๆ ก็พบว่าตัวเลขมันใหญ่มาก prime รันไม่ทัน ก็เลยเปลี่ยนแผนกลางอากาศขณะที่ timer วิ่งอยู่ (ตอนนั้นไม่รู้ว่า large หมดเวลาแล้วขอใหม่ไม่ได้)

แผนแรกก็คือไปใช้ C++ เผื่อจะรันไวขึ้น แต่ก็พบว่าเลขรับเข้าใหญ่กว่า 64 bit int เก็บไม่พอ library หา prime ที่ได้มาก็หา prime ได้สูงสุดแค่ uint64_t

อีกแผนคือ generate prime database ไว้ก่อนเลย ก็นั่ง generate ไปจนปาเข้าไป 40GB แล้ว ตอนนั้นเวลา countdown ใกล้หมดแล้วเลยกดหยุด และผมเชื่อว่าโปรแกรมที่ generate นั่นเหมือนจะออกมาแค่ uint64_t อีกแน่ๆ เพราะเป็น frontend ของ library เดียวกัน