ซ้อม CodeJam

Thursday, February 16, 2012, 02:46 AM

ช่วงนี้ซ้อม CodeJam อยู่ หวังว่าจะได้เสื้อ Google มาใส่เล่น (โดน @lewcpe ยั่วให้อยากแข่ง) เลยว่าจะจดรายระเอียดเอาไว้หน่อย เผื่อว่าใครอยากจะลงเล่นแย่งชิงเสื้อไปด้วย อิอิ

การเขียนโปรแกรมแก้โจทย์:

ใช้ภาษาอะไรก็ได้ ขอแค่มี compiler เวอร์ชันฟรีให้กรรมการเอาไว้ทดสอบก็พอ (Mathematica อด)
ส่วน editor/ide จะใช้อะไรก็ได้ อันนี้ฟรีสไตล์เลย
แต่ระบบคิดคะแนนคือโหลด test case มารันในเครื่องตัวเอง แล้วส่งคำตอบกลับไป ไม่ใช่รันที่ฝั่ง server ปิดบัง test case
ดังนั้น test case ที่ให้มาก็จะมี time out เพื่อป้องกันการที่เราโหลด test case มาศึกษานั่นเอง
และเวลาส่งคำตอบ ต้องแนบไฟล์โปรแกรมของเราไปด้วย

คำถามแต่ละข้อ:

ในหนึ่งคำถาม จะมี test case ให้ 2 ชุด (ง่ายกับโหด)
อ่านโจทย์ + เขียนโปรแกรมให้เสร็จก่อน แล้วค่อยโหลด test case
test case ข้อง่ายเมื่อโหลดมาแล้ว มีเวลา 4 นาทีในการหาคำตอบ และส่งข้อมูลกลับไปให้ตรวจ
ส่งคำตอบผิดไป ทางโน้นจะบอกว่าผิด แต่ยังให้ส่งใหม่ได้เรื่อยๆ จนกว่าเวลา 4 นาทีจะหมด
ถ้าเวลาหมดก็ต้องโหลด test case ชุดใหม่มาคิด
เมื่อส่งคำตอบที่ถูกต้องไปแล้ว ถึงจะโหลด test case แบบโหดมาทำได้
test case โหดให้เวลา 8 นาที แต่จะไม่บอกตอนแข่งว่าถูกหรือผิด แถมคราวนี้เวลาหมดแล้วหมดเลย (ระวังให้ดี)

ในหนึ่งรอบต้องเจอ:

แต่ละรอบจะมีคำถามให้ 3 ข้อ เรียงจากคะแนนน้อยไปมาก (อาจจะถือว่าเรียงง่ายไปยากด้วย)
ถ้าคิดว่าทำไม่ทันทั้ง 3 ข้อ ควรเก็บข้อแรก (ง่ายสุด) แล้วข้ามไปเก็บข้อสุดท้ายเลย จะได้คะแนนเยอะกว่าเก็บข้อแรกกับข้อที่สอง
แต่ถ้าคิดจะทำข้อสุดท้ายด้วยการ recursive - brute force ไม่พึ่ง dynamic programming ทำใจได้เลยว่าผ่านแค่ test case แบบง่ายเท่านั้น
เพราะฉะนั้น จะเขียน algorithm ธรรมดาเก็บ test case แบบง่ายทั้งหมดก่อน (อย่างรวดเร็ว) แล้วค่อย optimize เพื่อลุย test case โหดก็ได้

รอบที่แข่งขัน:

รอบ qualification ให้เวลา 24 ชั่วโมง แต่ถ้าจะจริงจังกับเสื้อ ควรทำรอบนี้ให้เสร็จใน 2 ชั่วโมง เพราะคำถามง่ายมาก
เมื่อผ่าน qualification แล้ว ก็จะพบกับรอบที่ 1 ซึ่งมีให้เลือกเล่น 3 รอบย่อย
จะแข่งรอบย่อยกี่รอบก็ได้ ขอแค่ผ่านรอบย่อยอันใดอันหนึ่งก็พอแล้ว (เข้ารอบประมาณรอบย่อยละ 1000 คน)
รอบย่อยของรอบที่ 1 จะเริ่มโหดขึ้นมาบ้างแล้ว ควรเก็บให้ได้อย่างน้อย 2 ข้อเต็มๆ (เวลาแข่งประมาณ 2.5 ชั่วโมง)
ถ้าไม่มีปัญหาอะไร ก็จะได้ผ่านเข้าไปแข่งรอบที่ 2
รอบนี้จะยากขึ้นมาอีกระดับเลย เก็บได้ข้อนึงเต็มๆ กับอีกข้อที่ผ่านแค่ test case ง่ายก็มีสิทธิ์ได้เสื้อแล้ว
จะผ่านเข้ารอบที่ 3 ได้ต้องติด 500 อันดับแรก ส่วนถ้าจะหวังเสื้อก็ติด 1000 อันดับแรก

เอาให้ได้ถึงแค่นี้ก่อน ถ้าติดถึงรอบ 3 มหาโหดจริงจะมาเขียนต่อ (ตอนนี้หวังแค่เสื้ออย่างเดียว)