ข้อมูลเบื้องต้นเกี่ยวกับคอมพิวเตอร์โอลิมปิกระหว่างประเทศ
การแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ (International Olympiad in Informatics) คือการแข่งขันเขียนโปรแกรมคอมพิวเตอร์ที่จัดขึ้นประจำปี ในการแข่งขันนักเรียนระดับชั้นมัธยมศึกษาตอนปลายเข้าร่วมแข่งขันทั่วโลก ผู้เข้าแข่งขันจำเป็นต้องใช้ความรู้ทางด้านวิทยาการคอมพิวเตอร์ (เช่น อัลกอริทึม โครงสร้างข้อมูล ฯลฯ) และเขียนโปรแกรมแก้ปัญหาที่กำหนดมาให้
การแข่งขันคอมพิวเตอร์โอลิมปิกที่จะจัดครั้งต่อไป
- ปี 2009 จะมีการแข่งขันที่เมื่อง Plovdiv ประเทศบัลแกเรีย
- ปี 2010 จะมีการแข่งขันที่เมือง Waterloo ประเทศแคนาดา
- ปี 2011 จะมีการแข่งขันที่เมืองพัทยา ประเทศไทย
- ปี 2012 จะมีการแข่งขันที่เมือง Milan ประเทศอิตาลี
รูปแบบการแข่งขัน
แข่งขันกันเขียนโปรแกรมเป็นเวลา 2 วัน แต่ละวันจะมีโจทย์ 3-4 ข้อ มีเวลาให้แก้ปัญหาทั้งหมด 5 ชั่วโมง ซึ่งรวมเวลาในการคิดหาขั้นตอนวิธีในการหาคำตอบ การเขียนโปรแกรม และการดีบัก (debug) โปรแกรม ทั้งหมดเข้าด้วยกัน
โจทย์ปัญหาในการแข่งขันคอมพิวเตอร์โอลิมปิกมีกันด้วยกัน 3 ประเภท คือ Batch, Library Interaction และ Output Only
โจทย์ Batch คือโจทย์ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมภาษา C, C++ หรือ Pascal เพื่อรับแฟ้มข้อมูลทดสอบ นำไปประมวลผล แล้วแสดงผลลัพธ์สอดคล้องตามที่โจทย์กำหนด
ตัวอย่างเช่น โจทย์ให้คำนวณ “ค่าเฉลี่ยเลขคณิตของลำดับจำนวนความยาว N” ผู้เข้าแข่งขันจะต้องรับจำนวน N จำนวนทาง Standard Input นำไปหาผลรวมทั้งหมด จากนั้นนำผลรวมไปหารด้วย N ก่อนแสดงผลลัพธ์ทาง Standard Output
หลังจากที่ผู้เข้าแข่งขันเขียนโปรแกรมเสร็จแล้ว จะต้องส่งโค้ดของโปรแกรมเพื่อตรวจ ซึ่งมักจะตรวจหลังการแข่งขันเสร็จสิ้นแล้ว การตรวจโปรแกรมจะนำแฟ้มข้อมูลลับมาทดสอบกับโปรแกรมของผู้เข้าแข่งขันว่าให้คำตอบถูกต้องหรือไม่ ผู้เข้าแข่งขันจะได้คะแนนจากชุดทดสอบที่ให้ผลลัพธ์ที่ถูกต้องและจะต้องรันโดยใช้เวลาและหน่วยความจำไม่เกินที่โจทย์กำหนดด้วย
โจทย์ Library Interaction คือโจทย์ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมภาษา C, C++ หรือ Pascal เพื่อติดต่อกับ Library ที่กรรมการกำหนดมาให้ ผู้เข้าแข่งขันจะต้องโต้ตอบกับ Library ดังกล่าวและบรรลุวัตถุประสงค์ตามที่โจทย์กำหนด
ตัวอย่างเช่น โจทย์กำหนดให้ผู้เข้าแข่งขันเขียนโปรแกรมเพื่อเล่นเกมให้ชนะ Library ที่กำหนดให้ โจทย์อาจจะกำหนดสถานะเริ่มต้นของเกมให้คุณเลือกที่เป็นฝ่ายแรกที่เริ่มเกมหรือเป็นฝ่ายที่เล่นเกมเป็นคนที่สองก็ได้ หากคุณสามารถชนะเกมโดยที่ไม่ทำผิดกติกา คุณจะได้คะแนนสำหรับเกมนั้น ๆ
โจทย์ลักษณะนี้จะกำหนดวิธีการติดต่อกับ Library มาให้อย่างละเอียด ผู้เข้าแข่งขันไม่จำเป็นต้องมีความรู้เกี่ยวกับ Library มาก่อน นอกจากนี้กรรมการมักมี Library ตัวอย่างเพื่อใช้ในการทดสอบโปรแกรมที่ผู้เข้าแข่งขันเขียน อย่างไรก็ตาม Library ที่ใช้ในการให้คะแนนผู้เข้าแข่งขันอาจแตกต่างออกไป
โจทย์ Output Only คือโจทย์ที่ผู้เข้าแข่งขันจะต้องเขียนโปรแกรมเพื่อหาคำตอบสำหรับโจทย์ปัญหาที่กำหนดมาให้ โดยผู้เข้าแข่งขันจะทราบแฟ้มข้อมูลนำเข้าทั้งหมด ผู้เข้าแข่งขันจะต้องหาคำตอบสำหรับชุดข้อมูลนำเข้าแล้วส่งเฉพาะคำตอบที่หาได้
โจทย์ Output Only อาจไม่ต้องการคำตอบที่ดีที่สุด ส่วนใหญ่คะแนนจะขึ้นกับว่าคำตอบของผู้เข้าแข่งขันนั้นดีแค่ไหน อาจมีการนำคำตอบผู้เข้าแข่งขันไปเปรียบเทียบกับผู้เข้าแข่งขันคนอื่น ๆ หรือแม้แต่เทียบกับคำตอบที่ดีที่สุดของกรรมการ โจทย์ Output Only ส่วนมากมักจะเป็นโจทย์ปัญหาในกลุ่ม NP-Complete หรือโจทย์ที่ต้องใช้เวลารันนาน
การเขียนโปรแกรมและการแก้โจทย์ปัญหา
ผู้เข้าแข่งขันจะมีเครื่องคอมพิวเตอร์หนึ่งเครื่องซึ่งลงระบบปฏิบัติการลีนุกซ์ พร้อมด้วย Compiler และ Editor มากมาย คอมพิวเตอร์ดังกล่าวจะเชื่อมต่อกับระบบเครือข่ายเพื่อใช้ในการส่งคำตอบสำหรับโจทย์ปัญหาเท่านั้น หากมีการใช้เครือข่ายทำอย่างอื่นจะถูกปรับให้แพ้และต้องออกจากการแข่งขันทันที
ในระหว่างการเขียนโปรแกรม จะมีโจทย์ทั้งฉบับภาษาไทยและภาษาอังกฤษ (สำหรับผู้แข่งขันจากประเทศไทย) หากผู้เข้าแข่งขันสงสัยเกี่ยวกับโจทย์ สามารถถามคำถามกรรมการได้ โดยที่คำตอบของกรรมการจะเป็น (1) ใช่ (2) ไม่ใช่ (3) ไม่แสดงความคิดเห็น (4) คำตอบปรากฏในโจทย์อย่างชัดเจน (5) คำถามถามไม่ถูกต้อง
เกณฑ์การตัดสิน
สำหรับโจทย์แต่ละข้อจะมีคะแนนเต็ม 100 คะแนน รวมทั้งหมด 600-800 คะแนน เมื่อนำคะแนนของผู้เข้าแข่งขันแต่ละคนมารวมกัน แล้วนำมาเรียงลำดับ จากนั้นทำการจัดอันดับเหรียญรางวัลโดยใช้เกณฑ์ดังนี้
- คะแนนที่จะได้เหรียญทอง คือคะแนนที่ต่ำที่สุดที่ทำให้ผู้เข้าแข่งขันไม่เกิน 1 ใน 12 มีคะแนนมากกว่าหรือเท่ากับคะแนนนี้
- คะแนนที่จะได้เหรียญเงิน คือคะแนนที่ต่ำที่สุดที่ทำให้ผู้เข้าแข่งขันไม่เกิน 1 ใน 4 มีคะแนนมากกว่าหรือเท่ากับคะแนนนี้
- คะแนนที่จะได้เหรียญทองแดง คือคะแนนที่สูงที่สุดที่ทำให้ผู้เข้าแข่งขันอย่างน้อย 1 ใน 2 มีคะแนนมากกว่าหรือเท่ากับคะแนนนี้
