在线评测系统
在线评测系统(英语:Online Judge,缩写OJ)是一种在算法竞赛竞赛中用来测试参赛程序的在线系统,也可以用于平时练习。近年来(2016年或更早)亦出现一些针对求职面试的在线评测系统。许多OJ网站会自发组织一些竞赛。此外,OJ网站通常会设立用户排名,以用户的提交答案通过数多少或某个题目执行时间快慢为排名依据。[1]
原理
算法竞赛通常采取黑盒测试,事先准备好一些测试数据,然后用它们来测试选手的程序[2]。
在在线评测系统中,用户需要提交源代码至服务器,服务器会编译用户的源代码,然后执行源代码生成的可执行文件(或用解释方式执行,或直接执行脚本文件),得到其输出的结果,并与正确结果比较。[3]
为防止攻击和恶意提交,服务器必须采取一定的安全措施,例如对用户提交的源代码实施过滤、将进程放入沙盒以进行隔离、对代码进行哈希以防止抄袭和重复提交等。[3]
Virtual Judge
Virtual Judge是一种特殊的在线评测系统。与其他在线评测系统不同的是,Virtual Judge系统本身并没有任何测试数据,而是通过在其他在线评测系统中注册的机器人账号进行测试并抓取测试结果。因此可以在只有题目而没有测试数据的前提下建立竞赛。[4][5]
题目状态
在提交程序之后,在线评测系统会根据题目的测评情况,返回评测结果。只有返回“Accepted”状态,才表示题目通过,选手才会获得成绩。不同OJ评测结果略有出入,但常见的评测结果大致分为以下三类。
正在评测
- Pending:系统繁忙,用户程序正在排队等待。
- Pending Rejudge:因为数据更新或其他原因,系统将重新判你的答案.
- Compiling:正在编译。
- Running & Judging:正在运行并与标准数据进行比较。
程序未通过
- Wrong Answer(简称WA):答案错误。
- Runtime Error(简称RE):运行时错误,程序崩溃。
- Compile Error(简称CE):编译错误。
- Time Limit Exceeded(简称TLE):运行超出时间限制。
- Memory Limit Exceeded(简称MLE):超出内存限制。
- Output Limit Exceeded(简称OLE):输出的长度超过限制。
- Presentation Error(简称PE):答案正确,但是输出格式不符合题目要求。在一些要求比较严格的比赛中,格式错也会被视为答案错误[2]。
程序通过
在测试过程中,只有未发生以上几种错误的情况下才算做通过。
- Accepted(简称AC):程序通过。另外,在整场比赛中通过了所有题目又俗称“AK”或是“破台”。
一些比赛的测试点可以给出“部分分”,例如答案正确但不够优,或者选手没有完全完成题目所给的任务等。[2]
实例
最早的在线评测系统是由西班牙Valladolid大学的Ciriaco García de Celis于1995年开发的,当时用于该校参加ACM/ICPC西南欧区域赛选拔队员。[6]
现在较为著名的在线评测系统有洛谷(页面存档备份,存于互联网档案馆),西班牙的UVaOJ、俄罗斯的SGU、Timus、Codeforces、波兰的SPOJ、美国的TopCoder、中国的POJ(北京大学)、ZOJ(浙江大学)、HDOJ(页面存档备份,存于互联网档案馆)(杭州电子科技大学)。[2]
不同群体中不同OJ使用的频率也不同,学生中常会因为教师的要求使用公开/校内OJ,为此,许多公开OJ也提供了个性化服务,如Vijos(页面存档备份,存于互联网档案馆)中的“域”服务[7],OpenJudge(页面存档备份,存于互联网档案馆)、洛谷(页面存档备份,存于互联网档案馆)、Vjudge(页面存档备份,存于互联网档案馆)中的团队服务。
在特定群体中亦有一些流行的在线评测系统,例如中国初中选手中流行的Vijos(页面存档备份,存于互联网档案馆)、进阶选手使用的BZOJ(页面存档备份,存于互联网档案馆)(现称“耒阳大视野”,注:已无法访问)、hihocoder(页面存档备份,存于互联网档案馆)、美国求职者中流行的LeetCode(页面存档备份,存于互联网档案馆)等。
参见
参考文献
- ^ Programming Challenges (Skiena & Revilla) (页面存档备份,存于互联网档案馆) ISBN 0387001638, ISBN 978-0387001630
- ^ 2.0 2.1 2.2 2.3 刘汝佳. 算法競賽入門經典. 清华大学出版社. 2014-06. ISBN 978-7-302-35628-8.
- ^ 3.0 3.1 李定才,瞿绍军,胡争,段兵,成幸毅,唐强. 基于Windows的在线评测系统的安全性研究. 计算机技术与发展. 2011-09, (2011年第9期): 204–207.
- ^ Virtual Judge. [2016-09-19]. (原始内容存档于2016-09-20).(英文)
- ^ Welcome to NEUQ Virtual Judge. [2016-01-06]. (原始内容存档于2016-01-29).(英文)
- ^ Revilla M, Manzoor S, Liu RJ. Competitive learning in informatics: the UVa online judge experience (2008,2). Olympiads in Informatics: 131–148.
- ^ 帮助 - Vijos. vijos.org. [2017-06-06]. (原始内容存档于2017-07-13) (中文(中国大陆)).