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 เดียวกัน

Codejam Qualification Round 2014

โค้ดแจมปีนี้โจทย์ชักจะยากขึ้นเรื่อยๆ ครับ (ผมยังติดใจความง่ายของ 2011 อยู่เลยเนี่ย)

ปีนี้ผมดันทำ A เสร็จแล้วไปลุย C เลย ปรากฏว่าไม่ผ่านแล้วหมดแรงอยู่ตรงนั้น กว่าจะกลับมาทำ B ก็ห้าทุ่ม -_-‘ (ผมเองรู้สึกว่าผม burnout มาสักพักแล้ว ไม่ได้โค้ดแบบจริงจังมาสักสามสี่วันได้ หลังจากจัดเกมงูไปยาวๆ)

โค้ดปีนี้ครับ (Gist มันแยกไฟล์ไม่ได้ ผมลืมไปว่าต้องโพสต์แยกกัน)

## A

ข้อ A ใช้วิธีง่ายๆ ครับคือหา intersect มา แล้วดูว่ามีกี่ตัว ถ้ามีตัวเดียวก็ตอบตัวนั้นเลย

## B

ข้อ B ผมเสียเวลาบั๊กไปหลายพักเพราะคำนวณ `timeToTargetIfFarm` ผิด ลืมคิดเวลาเก็บเงินซื้อฟาร์มไป (และมีคิดติดลบด้วย) พอแก้เติม `max(0, cookie-farm)` ไปให้ถูก และ `timeToTargetIfFarm += timeToNextFarm` ก็เรียบร้อย ผ่านไปถึง B-large เลย

## C

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

## D

ข้อ D โจทย์ยาวมากครับ และมันไม่ได้ให้วิธีคิดมาด้วย ผมเองไม่ถนัดโจทย์แนวๆ optimization/game theory เลยเลยข้ามไปเลยแล้วกัน

จริงๆ ข้อ B ถ้าเป็นปีก่อนๆ ผมคงจะข้ามไปด้วย แต่ปีนีั้เห็นหลายคนทำแล้วเลยว่าจะทำมั่ง และ grader ผมเองเคยออกโจทย์แนวๆ นี้เหมือนกัน (แต่เป็น int หมด) เลยเอาวิธีคิดเดียวกับข้อที่ตัวเองออกมาใช้