在線評測系統

在線評測系統(英語: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) (中文(中國大陸)).