算法竞赛出题指南

本文介绍了算法竞赛中出题的相关知识与注意事项。

写在前面

0xfaner寒假里主办了一场面向全校的算法竞赛线上冬令营。冬令营要求每个同学都要参与出题工作。但是很多人作为算法竞赛萌新,并不了解出题流程。同时0xfaner也注意到很多致力于ACM的选手其实对出题工作并不熟悉。所以他决定写一篇文章来介绍下算法竞赛中出题的相关知识与注意事项。

简介

一个完整的题目包括三个部分:

  • 题面Problem:用于描述题目的全部细节。
  • 数据data:用于检验选手提交的代码的正确性。
  • 题解solution:用于说明该题目的标准解法。

比赛过程中,选手只能看到题面,而不能接触到数据和题解。

赛制大体分为两种

  • ACM赛制:可以对任意题目多次提交,直到正确为止,有实时榜,无部分分,按照过题数量与罚时进行排名。
  • OI赛制:比赛结束后将统一收取代码并进行评测,只有一次评测机会,无实时榜,有部分分,按分值进行排名。

其他赛制多由这两种赛制衍生而来,一般有三个维度:评测规则、实时榜、排名规则。

如较为著名的Codeforces赛制:可以对任意题目多次提交,直到正确为止,有实时榜,无部分分,按照分值进行排名。

不同的赛制对应不同的题面与数据,如在OI赛制中,需要按照部分分来分段出数据,并在题解中加以说明,但ACM赛制中则不需要。

题面 Problem

题面用于描述题目的全部细节。

题面一般包括四个部分:

  • 题目描述Description:描述了题目要求。
  • 数据范围与时空限制Limits:限定了输入输出数据的范围与程序运行所需时间空间的限制,常包含在题目描述Description或输入输出格式Format中,也可单独开一栏。
  • 输入输出格式Format:限定了输入输出数据的格式。
  • 输入输出样例Example:给定了一组或多组合法输入对应的正确输出,有时还会包含对样例的解释Note

0xfaner常用的格式如下(Markdown语法):

1
2
3
4
5
6
7
8
9
#Description
#Format
##Input
##Output
##Format
#Example
##Input
##Output
##Note

本次线上冬令营平台是vijos,出题人应当熟练运用Markdown,其中公式及符号应当使用latex来表示。

题目描述 Description

题目描述的作用是让选手理解题意。

当然,许多出题人会在题目描述中添加背景或者夹带私货使得题目变得不那么枯燥无味或者满足出题人的恶趣味。这当然是无伤大雅的,但是无论题面如何写,中文也好英文也好,都要以让选手理解题意为基础。表意不清、描述含糊、自相矛盾的题面无论在哪里都不会受欢迎。

题面一般会描述一个任务,要求选手编程解决。有给定输入的普通题,也有根据选手程序的输出而调整的交互题,也有无输入的提交答案题……总之题目形式多样,题目描述就要描述清楚这个任务。

数据范围与时空限制 Limits

数据范围及时空限制的作用是限制算法的时间复杂度。

因为题目中的给定任务往往建立在一个高度抽象的模型中,所以必须对输入输出数据及时空限制限定范围。

例如计算a+b,我们在现实生活中往往只需要十进制一百位以内的运算,但是在某些特殊情境中我们甚至需要用到上万位乃至上百万位的运算。对于不同的情景,写出正确算法的难度也各不相同。因此给定数据范围和时空限制也起到了明确题意的作用。

在出题人方面需要调节好数据范围与时空限制,来限定好标算的时间复杂度。既不能让时间复杂度不够优秀的算法通过,也不能让已经达到要求的算法被卡常数。

一般来说,出题人需要具备如何计算时间复杂度的前置知识并在评测机上加以验证。时间限制应当开到标算的1.5倍左右,以防止大常数选手悲剧(毒瘤出题人一般会开到1.1倍乃至1.0倍左右

输入输出格式 Format

输入输出格式的作用是限制选手代码的输入输出格式。

一般来说输入输出格式不应当成为妨碍选手Accept的原因,因为往往一道题目的考察点并不在此。

一般来说应当忽略行末空格与文尾换行,PEPresentation Error是每一个选手都不愿意看到的。

如果你想做一个良心出题人,那么你不应当在输入输出格式上挖坑。

输入输出样例 Example

输入输出样例的作用是帮助选手检验算法正确性。

输入输出样例可以帮助选手检验算法正确性。但样例无需像测试数据一样强,只需要给定小范围内的正确解即可。

同时输入输出样例还可以选手理解题意,不过不建议输入输出样例出太强,选手应当主要从题目描述中获取题意。

对于部分样例,可以再写一个对样例的解释Note

数据 Data

数据用于检验选手提交的代码的正确性。

数据包括输入文件与输出文件,对于交互题以及特殊评测题目Special Judge,还要额外加上一些用于评测的程序。

一般认为,如果选手通过了全部的测试数据,就认为该选手的算法正确性得到了验证。

所以数据应当足够强,并被限定在题面Problem给定的数据范围Limits以内。同时应当包含所有种类的极限情况,防止不合格的代码通过。

为避免数据单一,应当造出足够多的数据点来避免选手猜数据,一般来说十个数据就足够。

在OI赛制中,还要根据数据范围分段分强度造出数据。

因此,出题人应当对自己的题目有着清楚的认识,了解该题目的极限情况,以及各类wa点。

如果输入数据中包含图、树等较难以构造的数据,可以使用洛谷的基于Python的CYaRon或Codeforces的Polygon平台来构造。

题解 Solution

题解用于说明该题目的标准解法。

题解应该包含三部分:

  • 题意:用于明确题意,让误解题意的选手知道自己的wa点。
  • 解法:用于说明解题思路和方法,最好应当包含标算的时间复杂度。
  • 标算:方便选手检验自己的wa点。