TOCPC 2021's Tasks

IOI's Curriculum (Division I)

สามารถเข้าถึงได้ที่ IOI 2019 Syllabus

TOI's Curriculum (Division II)

ขอบเขตเนื้อหาวิชาที่ครอบคลุมในการแข่งขัน แบ่งได้เป็น 3 หมวด คือ (1) คณิตศาสตร์ (2) พื้นฐานวิทยาการคอมพิวเตอร์ และ (3) อัลกอริทึม

1. คณิตศาสตร์

• เลขคณิตและเรขาคณิต

  • จำนวนเต็ม คุณสมบัติของเลขจำนวนเต็ม (ค่าบวก ค่าลบ เลขคู่ เลขคี่ การหารลงตัว จำนวนเฉพาะ)
  • เลขเศษส่วน และร้อยละ
  • จุด เวคเตอร์ พิกัดจุดแบบคาร์ทิเชียน (Cartesian coordinates) ในตารางสองมิติที่มีพิกัดเป็นจำนวนเต็ม
  • ระยะทางแบบยูคลิด ทฤษฏีพิธากอรัส
  • ส่วนของเส้นตรง จุดตัดของเส้นตรง และคุณสมบัติพื้นฐานที่เกี่ยวข้อง
  • มุม สามเหลี่ยม สี่เหลี่ยมผืนผ้า สี่เหลี่ยมจัตุรัส วงกลม

• โครงสร้างไม่ต่อเนื่อง (discrete structures)

  • ฟังก์ชัน ความสัมพันธ์ และเซ็ต
  • ตรรกศาสตร์พื้นฐาน
  • วิธีการพิสูจน์
  • วิธีการนับเบื้องต้น
  • กราฟและต้นไม้

• เนื้อหาที่ไม่รวมอยู่ในการแข่งขัน

  • แคลคูลัส
  • ความน่าจะเป็น
  • สถิติ
  • จำนวนจริงและจำนวนเชิงซ้อน
  • ภาคตัดกรวยทั่วไป (parabolas, hyperbolas, ellipses) แต่เรื่องวงกลมอยู่ภายใต้ขอบเขตเนื้อหาในการแข่งขันระดับชาติ
  • โพลิกอน (ในระดับนานาชาติจะครอบคลุมเนื้อหาเกี่ยวกับโพลิกอน)

2. พื้นฐานวิทยาการคอมพิวเตอร์

• พื้นฐานด้านการเขียนโปรแกรม
• ทักษะการแก้ปัญหา (problem-solving skill)
• พื้นฐานโครงสร้างข้อมูล
  • ชนิดข้อมูลดั้งเดิม (Primitive data type) ได้แก่ Boolean, signed/unsigned integer, character
  • แถวลำดับ (อาเรย์ อาเรย์หลายมิติ)
  • Record/Struct
  • สตริงและการดำเนินการกับสตริง
  • Static และ Stack allocation
  • Lined structures (ทั้งที่เป็นแบบเส้นตรง และแบบที่แบ่งเป็นสาขาได้)
  • การสร้าง โครงสร้างกองซ้อน (stack), คิว (queue), ต้นไม้ และกราฟ
  • การเลือกโครงสร้างข้อมูลที่เหมาะสม
  • คิวลำดับความสำคัญ (priority queue), ไดนามิกเซต (dynamic set), ไดนามิกแมพ (dynamic map)
• การเรียกตัวเองซ้ำ (Recursion)
  • แนวคิด
  • ฟังก์ชันทางคณิตศาสตร์ที่เรียกตัวเองซ้ำ
  • วิธีแบ่งแยกและเอาชนะ (divide and conquer)
  • อัลกอริทึมการย้อนรอยแบบเรียกตัวเองซ้ำ (recursive backtracking)

3. อัลกอริทึม

• พื้นฐานการวิเคราะห์ความซับซ้อนของอัลกอริทึม (algorithmic complexity)
• กลวิธีทางอัลกอริทึม
  • Brute-Force algorithm
  • Greedy algorithm
  • Divide And Conquer
  • Backtracking (ทั้งที่เป็นแบบเรียกตัวเองซ้ำ และไม่เรียกตัวเองซ้ำ)
  • Branch-and-Bound algorithm
  • Pattern matching and string/text algorithm
  • Dynamic programming
• อัลกอริทึมเชิงคำนวณพื้นฐาน
  • อัลกอริทึมเชิงตัวเลขพื้นฐานที่เกี่ยวข้องกับจำนวนเต็ม เช่น Radix Conversion, Euclid's algorithm, Primality test in O(√N), Sieve of Eratosthenes, Factorization, Efficient exponentiation
  • การจัดการอาร์เรย์ขั้นพื้นฐาน (รวมถึงการทำฮิสโทแกรม และ Bucket sort)
  • Sequential และ Binary search
  • Search by elimination
  • การแบ่งข้อมูล (partitioning) การจัดลำดับด้วยการแบ่งข้อมูลซ้ำๆ Quick sort
  • การเรียงข้อมูลที่มีเวลาที่แย่ที่สุดเป็น O(NlogN) เช่น Heap sort และ Merge sort
  • Binary heap พื้นฐาน และ Binary search tree
  • การบรรยายโครงสร้างกราฟ เช่น adjacency list และ adjacency matrix
  • Depth-first and breadth-first traversals of graphs และการหาองค์ประกอบที่เชื่อมต่อกันของกราฟแบบไม่มีทิศทาง
  • Shortest path algorithm เช่น Dijkstra, Bellman-Ford และ Floyd-Warshall
  • Transitive closure (Floyd's algorithm)
  • Minimum spanning tree
  • Topological sort

ข้อกำหนดของระบบปฏิบัติการและตัวแปลภาษาที่ใช้ในระบบตัวตรวจของการแข่งขัน

1. โปรแกรมที่ผู้เข้าแข่งขันจัดทำในระหว่างการแข่งขัน กำหนดให้เขียนตามมาตรฐานของภาษา C หรือภาษา C++ ไม่อนุญาตให้เขียนโปรแกรมที่ทำงานใน Graphic Mode
2. ฟังก์ชันทั้งหมดในการเขียนโปรแกรม กำหนดให้ใช้ฟังก์ชันจากคลังมาตรฐานของภาษา C (The Standard C Library), conio.h (เฉพาะการทำงานบนระบบปฏิบัติการวินโดวส์) และ Standard Template Library (STL) เท่านั้น

• ไม่อนุญาตให้ใช้ฟังก์ชันจัดการกับแฟ้มและอุปกรณ์โดยตรงที่กำหนดรูปแบบใช้งานในแฟ้ม (fentl.h), (io.h) และ (iomanip.h)
• ไม่อนุญาตให้โปรแกรมสร้างแฟ้มข้อมูลสำรองเพิ่มเติมระหว่างการทำงาน ห้ามอ่านหรือเขียนแฟ้มข้อมูลอื่นนอกเหนือจากที่โจทย์ระบุ
• ไม่อนุญาตให้เรียกใช้โปรแกรมอื่นๆ (เช่น ผ่านทางฟังก์ชัน system) หรือเรียกใช้ system call นอกเหนือจากที่ใช้งานปกติ
• ไม่อนุญาตให้ทำการคำนวณแบบมัลติโปรเซสซิง (multi-processing) เช่น ไม่อนุญาตให้โปรแกรมเรียกใช้ฟังก์ชันใน thread library ต่างๆ

3. โปรแกรมภาษา C ที่ผู้เข้าแข่งขันจัดทำในระหว่างการแข่งขัน กำหนดให้เขียนโปรแกรมที่ส่วนขยายเป็น .c สำหรับภาษา C++ ให้ใช้นามสกุล .cpp และต้องอยู่ในรูปแบบที่สามารถแปล (compile) ให้เป็นโปรแกรมที่สามารถทำงานได้โดยสมบูรณ์จากบรรทัดคำสั่ง (command line)
4. ใช้ GCC (GNU compiler collection) ในการตรวจโปรแกรมเพื่อให้คะแนน โดยใช้วิธีการแปลและให้ทำงานจากบรรทัดคำสั่งเท่านั้น โปรแกรมจะถูกสั่งให้ทำงานบนระบบปฏิบัติการและคอมไพเลอร์เดียวกันกับที่ผู้เข้าแข่งขันเลือกใช้ ทั้งนี้เครื่องที่ใช้ในการตรวจสอบคำตอบของผู้เข้าแข่งขันจะเลือกระบบปฏิบัติการและคอมไพเลอร์โดยพิจารณาข้อมูลจากที่กำหนดไว้ที่ต้นไฟล์คำตอบของผู้เข้าแข่งขัน (รายละเอียดเพิ่มเติมอยู่ในหัวข้อ 'ข้อมูลและรายละเอียดเพิ่มเติมเกี่ยวกับการแข่งขัน')
5. คอมไพเลอร์ออปชัน (compiler option) ที่ใช้ในการแข่งขันจะทำการออปทิไมซ์ (optimize) โปรแกรมโดยใช้ออปชัน -O2
6. อนุญาตให้เขียนโปรแกรมภาษา C ตามมาตรฐาน C++11 และ C++17 โดยคอมไพเลอร์ออปชันที่กำหนดเพิ่มใช้ออปชัน -std=c++11 หรือ -std=c++17

ข้อห้าม

1. จำนวน subtasks น้อยกว่า 3
2. โจทย์ไม่ทำให้ผู้เข้าแข่งขันพัฒนา (เช่น โจทย์ที่พบเห็นได้โดยง่าย ผู้ที่มีประสบการณ์สามารถคิดออกได้ภายในไม่เกิน 1 นาที ขาดความคิดริเริ่มสร้างสรรค์ในโจทย์)
3. ความยากของการเขียนโปรแกรมไม่สมเหตุสมผลต่อระยะเวลา (เช่น เขียนมากกว่า 150 บรรทัดต่อข้อ)
4. โจทย์ใช้เนื้อหานอกขอบเขตที่กำหนดไว้
5. testcase ไม่เหมาะสม เช่น ค่าไม่ตรงเงื่อนไขที่โจทย์บอก หรือวิธีการที่ไม่ควรผ่าน ตามเงื่อนไขของโจทย์ สามารถผ่านได้โดยไม่ได้ตั้งใจ
6. time limit ไม่เหมาะสม เช่นโจทย์ต้องการแยกระหว่าง O(n) กับ O(n log n) แต่ตั้ง time limit ให้ solution บางตัวที่เป็น O(n log n) ผ่านได้ หรือบางตัวที่เป็น O(n) กลับไม่ผ่าน
7. input/output format ไม่ชัดเจน