ข้อมูลเบื้องต้นเกี่ยวกับคอมพิวเตอร์โอลิมปิกระหว่างประเทศ

การแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ (International Olympiad in Informatics) คือการแข่งขันเขียนโปรแกรมคอมพิวเตอร์ที่จัดขึ้นประจำปี ในการแข่งขันนักเรียนระดับชั้นมัธยมศึกษาตอนปลายเข้าร่วมแข่งขันทั่วโลก ผู้เข้าแข่งขันจำเป็นต้องใช้ความรู้ทางด้านวิทยาการคอมพิวเตอร์ (เช่นอัลกอริทึมโครงสร้างข้อมูลฯลฯ) และเขียนโปรแกรมแก้ปัญหาที่กำหนดมาให้

การแข่งขันคอมพิวเตอร์โอลิมปิกที่จะจัดครั้งต่อไป
ปี 2009 จะมีการแข่งขันที่เมื่อง Plovdiv ประเทศบัลแกเรีย
ปี 2010 จะมีการแข่งขันที่เมือง Waterloo ประเทศแคนาดา
ปี 2011 จะมีการแข่งขันที่เมืองพัทยา ประเทศไทย
ปี 2012 จะมีการแข่งขันที่เมือง Milan ประเทศอิตาลี

รูปแบบการแข่งขัน
แข่งขันกันเขียนโปรแกรมเป็นเวลา 2 วัน แต่ละวันจะมีโจทย์3-4 ข้อ มีเวลาให้แก้ปัญหาทั้งหมด 5 ชั่วโมง ซึ่งรวมเวลาในการคิดหาขั้นตอนวิธีในการหาคำตอบ การเขียนโปรแกรมและการดีบัก(debug) โปรแกรมทั้งหมดเข้าด้วยกัน

โจทย์ ปัญหาในการแข่งขันคอมพิวเตอร์โอลิมปิกมีกันด้วยกัน 3 ประเภท คือ Batch, Library Interaction และ Output Only

1.โจทย์ Batch คือโจทย์ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมภาษา C, C++ หรือ Pascal เพื่อรับแฟ้มข้อมูลทดสอบ นำไปประมวลผล แล้วแสดงผลลัพธ์สอดคล้องตามที่โจทย์กำหนด
ตัวอย่างเช่น โจทย์ให้คำนวณ “ค่าเฉลี่ยเลขคณิตของลำดับจำนวนความยาว N” ผู้เข้าแข่งขันจะต้องรับจำนวน N จำนวนทาง Standard Input นำไปหาผลรวมทั้งหมด จากนั้นนำผลรวมไปหารด้วย N ก่อนแสดงผลลัพธ์ทาง Standard Output

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

2.โจทย์ Library Interaction คือโจทย์ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมภาษา C, C++ หรือ Pascal เพื่อติดต่อกับ Library ที่กรรมการกำหนดมาให้ ผู้เข้าแข่งขันจะต้องโต้ตอบกับ Library ดังกล่าวและบรรลุวัตถุประสงค์ตามที่โจทย์กำหนด
ตัวอย่างเช่น โจทย์กำหนดให้ผู้เข้าแข่งขันเขียนโปรแกรมเพื่อเล่นเกมให้ชนะ Library ที่กำหนดให้ โจทย์อาจจะกำหนดสถานะเริ่มต้นของเกมให้คุณเลือกที่เป็นฝ่ายแรกที่เริ่มเกม หรือเป็นฝ่ายที่เล่นเกมเป็นคนที่สองก็ได้ หากคุณสามารถชนะเกมโดยที่ไม่ทำผิดกติกา คุณจะได้คะแนนสำหรับเกมนั้นๆ

โจทย์ลักษณะนี้จะกำหนดวิธีการติดต่อกับ Library มาให้อย่างละเอียด ผู้เข้าแข่งขันไม่จำเป็นต้องมีความรู้เกี่ยวกับ Library มาก่อน นอกจากนี้กรรมการมักมี Library ตัวอย่างเพื่อใช้ในการทดสอบโปรแกรมที่ผู้เข้าแข่งขันเขียน อย่างไรก็ตาม Library ที่ใช้ในการให้คะแนนผู้เข้าแข่งขันอาจแตกต่างออกไป

3.โจทย์ Output Only คือโจทย์ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมเพื่อหาคำตอบสำหรับโจทย์ปัญหา ที่กำหนดมาให้ โดยผู้เข้าแข่งขันจะทราบแฟ้มข้อมูลนำเข้าทั้งหมด ผู้เข้าแข่งขันจะต้องหาคำตอบสำหรับชุดข้อมูลนำเข้าแล้วส่งเฉพาะคำตอบที่หา ได้

โจทย์ Output Only อาจไม่ต้องการคำตอบที่ดีที่สุด ส่วนใหญ่คะแนนจะขึ้นกับว่าคำตอบของผู้เข้าแข่งขันนั้นดีแค่ไหน อาจมีการนำคำตอบผู้เข้าแข่งขันไปเปรียบเทียบกับผู้เข้าแข่งขันคนอื่นๆ หรือแม้แต่เทียบกับคำตอบที่ดีที่สุดของกรรมการ โจทย์ Output Only ส่วนมากมักจะเป็นโจทย์ปัญหาในกลุ่ม NP-Complete หรือโจทย์ที่ต้องใช้เวลารันนาน

การเขียนโปรแกรมและการแก้โจทย์ปัญหา
ผู้เข้าแข่งขันจะมีเครื่องคอมพิวเตอร์หนึ่งเครื่องซึ่งลงระบบปฏิบัติการลี นุกซ์ พร้อมด้วย Compiler และ Editor มากมาย คอมพิวเตอร์ดังกล่าวจะเชื่อมต่อกับระบบเครือข่ายเพื่อใช้ในการส่งคำตอบ สำหรับโจทย์ปัญหาเท่านั้น หากมีการใช้เครือข่ายทำอย่างอื่นจะถูกปรับให้แพ้และต้องออกจากการแข่งขันทันที

ในระหว่างการเขียนโปรแกรม จะมีโจทย์ทั้งฉบับภาษาไทยและภาษาอังกฤษ (สำหรับผู้แข่งขันจากประเทศไทย) หากผู้เข้าแข่งขันสงสัยเกี่ยวกับโจทย์สามารถถามคำถามกรรมการได้ โดยที่คำตอบของกรรมการจะเป็น (1) ใช่ (2) ไม่ใช่ (3) ไม่แสดงความคิดเห็น (4) คำตอบปรากฏในโจทย์อย่างชัดเจน (5) คำถามถามไม่ถูกต้อง

เกณฑ์การตัดสิน
สำหรับโจทย์แต่ละข้อจะมีคะแนนเต็ม 100 คะแนน รวมทั้งหมด 600-800 คะแนน เมื่อนำคะแนนของผู้เข้าแข่งขันแต่ละคนมารวมกันแล้วนำมาเรียงลำดับ จากนั้นทำการจัดอันดับเหรียญรางวัลโดยใช้เกณฑ์ดังนี้

•คะแนนที่จะได้เหรียญทอง คือคะแนนที่ต่ำที่สุดที่ทำให้ผู้เข้าแข่งขันไม่เกิน 1 ใน 12 มีคะแนนมากกว่าหรือเท่ากับคะแนนนี้
•คะแนนที่จะได้เหรียญเงิน คือคะแนนที่ต่ำที่สุดที่ทำให้ผู้เข้าแข่งขันไม่เกิน 1 ใน 4 มีคะแนนมากกว่าหรือเท่ากับคะแนนนี้
•คะแนนที่จะได้เหรียญทองแดง คือคะแนนที่สูงที่สุดที่ทำให้ผู้เข้าแข่งขันอย่างน้อย 1 ใน 2 มีคะแนนมากกว่าหรือเท่ากับคะแนนนี้

แต่ละประเทศสามารถส่งนักเรียนเข้าแข่งขันโอลิมปิกวิชาการได้ไม่เกิน 4 คน สำหรับประเทศไทย นักเรียนชั้นมัธยมศึกษาตอนปลายที่ประสงค์ที่เข้าแข่งขันคอมพิวเตอร์โอลิมปิกจะต้องดำเนินการดังนี้

1.สมัครเข้าค่ายคอมพิวเตอร์ สอวน. ณศูนย์สอวน. ใกล้โรงเรียนท่านประมาณเดือน สิงหาคม- กันยายนของทุกปี (สามารถดูรายละเอียดเพิ่มเติมได้ที่เว็บมูลธินิสอวน.)
2.สอบคัดเลือกเพื่อเข้าค่ายสอวน. (ถ้ามี)
3.ผ่านการอบรมค่ายสอวน. ค่ายที่ 1 และ 2 เพื่อเป็นตัวแทนศูนย์ สอวน.
4.แข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติในเดือนพฤษภาคม เพื่อได้สิทธิเข้าค่ายอบรมเข้มคอมพิวเตอร์โอลิมปิก สสวท. (สามารถดูรายละเอียดเพิ่มเติมได้ที่เว็บสสวท.)
5.ผ่านการอบรมค่ายสสวท. ค่ายที่ 1 (เดือนตุลาคม) ค่ายที่ 2 ระยะที่ 1 (เดือนมีนาคม) ค่ายที่ 2 ระยะที่ 2 (เดือนเมษายน)
6.ได้รับคัดเลือกเป็นผู้แทนประเทศไทยไปแข่งคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ฉะนั้นจะต้องเข้าค่ายเป็นเวลาประมาณ 2 ปีก่อนที่จะได้เป็นผู้แทนประเทศฯ

ในกรณีที่นักเรียนผ่านค่ายอบรมเข้มสสวท. ค่ายที่ 1 จะมีสิทธิสอบ สอวน. ระดับชาติคอมพิวเตอร์โอลิมปิกครั้งถัดไปได้และในกรณีที่นักเรียนผ่านค่ายอบรมเข้ม สสวท. ค่ายที่ 2 ระยะที่ 1 จะมีสิทธิเข้าค่ายที่ 1 ของปีถัดไปได้ ส่วนในกรณีที่นักเรียนผ่านค่ายอบรมเข้ม สสวท. ค่ายที่ 2 ระยะที่ 2 จะมีสิทธิเข้าค่ายที่ 2 ระยะที่ 1 ของปีถัดไปได้

ข้อมูลสำหรับฝึกเขียนโปรแกรมและแก้ปัญหาโจทย์ ขั้นตอนการฝึกเขียนโปรแกรม ณ ที่นี้จะแบ่งขั้นตอนการเตรียมความพร้อมออกเป็น 3 ระดับดังนี้

1.ขั้นพื้นฐาน
นักเรียนควรจะเริ่มจากศึกษาคณิตศาสตร์ เรื่อง การให้เหตุผล คอมบินาทอริกส์ ทฤษฎีจำนวน และพีชคณิต เพราะเป็นส่วนสำคัญในการพัฒนาทางด้านการเขียนโปรแกรมต่อไป หลังจากนั้นนักเรียนจะต้องเริ่มฝึกใช้งานภาษาระดับต่ำถึงปานกลาง โดยภาษาที่มีให้เลือกได้แก่ C, C++ และ Pascal เราขอแนะนำให้ท่านเริ่มที่ภาษา C ก่อนแล้วจึงเปลี่ยนมาใช้ C++ เมื่อท่านใช้งานภาษา C จนคล่องแล้ว ส่วนภาษา Pascal มักไม่นิยมใช้ในการแข่งขันคอมพิวเตอร์โอลิมปิกของประเทศไทย

นักเรียนสามารถเริ่มต้นฝึกเขียนโปรแกรมจาก หนทางดังต่อไปนี้
1.การเข้าค่าย สอวน. จะมีการสอนเขียนโปรแกรมตั้งแต่เริ่มต้น รวมทั้งโครงสร้างข้อมูลและขั้นตอนวิธีเบื้องต้น
2.วิชาบังคับหรือวิชาเพิ่มเติมของแต่ละโรงเรียน (บางโรงเรียนอาจไม่มีวิชาเขียนโปรแกรม)
3.เริ่มต้นฝึกด้วยตนเอง เช่น ผ่านเว็บไซต์ Programming.in.th หรือเว็บไซต์อื่นๆ หรือแม้แต่ซื้อหนังสือมาฝึกด้วยตนเอง

การฝึกฝนเขียนโปรแกรมควรจะค่อยเป็นค่อยไปควบคู่กับการศึกษาคณิตศาสตร์ ไม่ควรรีบเร่งหรือเริ่มต้นด้วยการเขียนโปรแกรมที่มีลักษณะเป็นอ็อบเจกท์ เพราะจะทำให้ยุ่งยากในการเรียนรู้เขียนโปรแกรมต่อไป

2.ขั้นกลาง
นักเรียนควรหาโจทย์ปัญหาระดับง่ายถึงปานกลางมาฝึกเขียนโปรแกรมจนมีความชำนาญ ก่อนจะหาหนังสือเพื่อศึกษาโครงสร้างข้อมูลและขั้นตอนวิธีเบื้องต้นต่อไป ส่วนมากในค่ายสอวน.และสสวท. มักจะมีสอนอยู่แล้ว

3.ขั้นสูง
สำหรับนักเรียนที่ได้เข้าค่ายสสวท. ค่ายที่ 2 (เดือนมีนาคม) แล้ว ควรจะศึกษาโครงสร้างข้อมูลและขั้นตอนวิธีที่มีความซับซ้อนมากขึ้น นักเรียนจำเป็นต้องมีพื้นฐานคณิตศาสตร์อยู่ในระดับดี ข้อมูลเกี่ยวกับเนื้อหาที่เกี่ยวข้องกับคอมพิวเตอร์โอลิมปิกที่นี่

สำหรับเทคนิคการเขียนโปรแกรมเพิ่มเติมเล็กๆ น้อยๆ สามารถหาอ่านได้จาก Blog ของนักเขียนต่างๆ ในเว็บนี้

เว็บไซต์ ฝึกเขียนโปรแกรม
เว็บไซต์ที่มีโจทย์ปัญหาการเขียนโปรแกรมมากมาย มีดังต่อไปนี้ (หากผู้ใดมีเพิ่มเติมสามารถส่งอีเมลมาบอกเพิ่มเติมได้)

เว็บไซต์ ภายในประเทศ
การแข่งขัน YTOPC และ YTOPC Challenge ภายในเว็บไซต์นี้
Programming.in.th
azzeptGrader
Theory wiki
เว็บไซต์ต่างประเทศ
โจทย์ IOI ปีเก่า
USACO Training Program Gateway
Croatian Open Competition in Informatics
เว็บจำพวก timus หรือ z-trening.com (ไม่ใช่แกน)
โจทย์ของประเทศบัลแกเรีย โปแลนด์ โครเอเชีย อเมริกา รัสเซีย แคนาดา อังกฤษ ฝรั่งเศส ฯลฯ (โปรดใช้ Google ในการค้นหา)

รายการเนื้อหาทั้งหมดที่เกี่ยวข้องกับคอมพิวเตอร์โอลิมปิกทั้งหมดนี้มาจาก ioi2009.org