在线评测系统

在线评测系统(英語: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页面存档备份,存于互联网档案馆)等。

参见

参考文獻

  1. ^ Programming Challenges (Skiena & Revilla)页面存档备份,存于互联网档案馆ISBN 0387001638, ISBN 978-0387001630
  2. ^ 2.0 2.1 2.2 2.3 劉汝佳. 算法競賽入門經典. 清華大學出版社. 2014-06. ISBN 978-7-302-35628-8. 
  3. ^ 3.0 3.1 李定才,瞿绍军,胡争,段兵,成幸毅,唐强. 基于Windows的在线评测系统的安全性研究. 计算机技术与发展. 2011-09, (2011年第9期): 204–207. 
  4. ^ Virtual Judge. [2016-09-19]. (原始内容存档于2016-09-20). (英文)
  5. ^ Welcome to NEUQ Virtual Judge. [2016-01-06]. (原始内容存档于2016-01-29). (英文)
  6. ^ Revilla M, Manzoor S, Liu RJ. Competitive learning in informatics: the UVa online judge experience (2008,2). Olympiads in Informatics: 131–148. 
  7. ^ 帮助 - Vijos. vijos.org. [2017-06-06]. (原始内容存档于2017-07-13) (中文(中国大陆)).