Online Judge System

Online Judge System

源起

「 Association for Computing Machinery (ACM) 」是一個致力於電腦科學教育的協會，出版大量專業期刊、文獻，舉辦重大的計算機科學會議，在資訊界舉足輕重、名聞遐邇。

ACM 每年度都會舉辦一次「 The ACM-ICPC International Collegiate Programming Contest (ACM-ICPC) 」，是一個給全世界大專院校學生參加的演算法程式設計比賽，比賽目的在於考驗選手臨場時的演算法設計能力、程式編寫能力。 ACM 首先在世界各地舉辦初賽，然後從各個賽區選拔出表現優秀的隊伍，角逐世界總決賽。台灣主要大專院校近十幾年來不遺餘力，積極爭取到台灣賽區的舉辦權和承辦權，並鼓勵學生參與比賽。另外台灣教育部也創辦了類似的「全國大專電腦軟體設計競賽」，藉此發掘優秀的選手，賦予為國爭光的使命。

ACM-ICPC 帶動了演算法程式設計的風氣。世界上許多大專院校的資訊系所，仿照 ACM-ICPC 的比賽模式，紛紛自行開發出即時線上比賽系統，能夠自動批改、評分、計時、統計。學生不必齊聚一堂，藉由網際網路，就可以相互切磋程式設計技巧。比賽結束之後，便將比賽題目編列題庫，並開放線上批改程式的功能，供學生賽後練習檢討。這套系統大家一般稱之為「 Online Judge System 」，或直接稱為「 Online Judge 」、「 OJ 」。

最古老、也是最有知名度的 OJ ，是由西班牙知名的瓦雅多利大學「 Universidad de Valladolid (UVa) 」開發的「 UVa Online Judge 」。 UVa Online Judge 是台灣人最熟悉的一個 OJ ：資訊相關科系的學生，常利用它來磨鍊程式設計技巧；教師將它當作課程教材使用；有許多個人網站從事題目翻譯，提供測試資料集等等。

UVa Online Judge 亦和 ACM 合作，成為 ACM 推廣的一個 OJ ，藉此向大眾提倡程式設計。因此， UVa Online Judge 除了收集自行舉辦的比賽的題目，也嘗試收錄世界各地重大程式設計比賽的題目，以臻豐富完整。有趣的是，歷年來大家口耳相傳、以訛傳訛，便將 UVa Online Judge 誤植為 ACM 了，把 UVa Online Judge 的題庫稱作「 ACM 題目」，利用 UVa Online Judge 訓練程式設計技巧時稱作「寫 ACM 」，約定成俗。

知名的 Online Judge

UVa Online Judge，UVa Online Judge: Electronic Board
西班牙Valladolid大學的Online Judge。
是最古老也是全世界最知名的Online Judge，題庫目前約有2800+題。
題目類型非常廣泛。絕大部分的題目難度偏易，適合初學者磨練程式設計功力。
有專業的審題團隊。另外也有許多工具網站。

PKU JudgeOnline
中國北京大學的Online Judge，是中國規模最大的一個Online Judge，
題目類型偏向演算法競賽，可以找到比賽常見題型。
好處是可以在網路上輕鬆找到中文的解題資訊。

Timus Online Judge
俄國Ural大學的Online Judge，是俄國最大的Online Judge。
有比較進階的演算法題目，難度偏高。
有專業的審題團隊。

Sphere Online Judge
波蘭Sphere實驗室建立的Online Judge，是波蘭最大的Online Judge。
會員可自創題目，題目很有特色，但是品質良莠不齊。
支援多種程式語言。

Polish Olympiad in Informatics
波蘭用來訓練國際資訊奧林匹亞競賽選手的網頁。
收錄近年來IOI的題目、以及培訓營隊的題目。
題型幾乎都是演算法設計，而非演算法應用。
程度很高，不是平常人能夠接觸的領域。

The 2000's ACM-ICPC Live Archive Around the World
此站專門收集ACM-ICPC在2001年之後的比賽題目，
依照賽區地點來做編錄。可惜的是題庫尚未收集完整。
起先，Live Archive的題庫是跟UVa Online Judge的題庫捆在一起的，並且共用一套OJ。
後來，在2003年的聖誕節，站方決定將Live Archive獨立出來成為一個網站，原因不明。
雖然現在兩個網站各自運作，但實際上兩者都是UVa Online Judge的小組在維護的。

台灣的 Online Judge

高中生程式解題系統 ZeroJudge
由高師大附中所開發的Online Judge，
是第一個使用繁體中文介面的系統，實乃台灣人之福。
請大家記得懷著感恩的心，謝謝系統設計者。

Temporary Infor Online Judge
建國中學資研社的Online Judge。
有很多學生自行設計的創意題目。

NTU Online Judge
台灣大學的Online Judge。
目前只用於培訓校內的ACM-ICPC參賽選手，並未對校外人士開放。

NCTU Online Judge
交通大學的Online Judge。
比較特別的是，這是玩資訊安全攻防演練的Online Judge。

USACO

USACO Training Program Gateway

http://train.usaco.org

USACO = USA Computing Olympiad 美國資訊奧林匹克。這個網頁是美國用來訓練國際資訊奧林匹亞競賽選手的網頁，同時亦開放給大眾使用。

這個網站非常有趣！首先註冊一個帳號，進入網站後，會看到一個任務表，完成前面的任務，才會開啟後面的任務──循序漸進，學習更精深的課題。有些任務是只是一些文字資料，講述方法或概念，只要讀完，就算是解決了任務。讀完資料後，接下來的任務，通常都是一連串程式設計的題目，正好學以致用。

有些困難的題目，都會貼心的附帶提示，讓使用者不至於無所適從。每當解決了一個問題之後，便可以觀看該題的解析、解法、解答，讓自己有檢討和進步的空間。這個網站可說是一個非常完整的教學網站！

USACO Contest Gateway

http://ace.delos.com/contestgate

USACO 的活動時間是每年十月到隔年三月。十月好像是新生入學，而四月就是資訊奧林匹克競賽的時間（一個全世界天才高中生參與的資訊競賽）。 USACO 過了三月之後就會沉寂，一直到十月才又有新一季的活動。

每一季開始時， USACO 會舉辦資格賽，以鑑定新人的實力。接下來每個月都會舉辦月賽，參訓選手依照實力，獲邀參加對應等級的賽事。月賽的用意，一方面當作是成效驗收，一方面也是在激勵選手邁向更高的等級。 USACO 也不藏私，所有月賽都對外界開放，也因此 USACO 也就成了全世界天才高中生相互較勁與成長的場所，而一般民眾也有了動動腦的時間。

比賽說明

USACO 的比賽區分為金銀銅三種等級。每個人預設都是銅等級，隨時都可以參加銅等級的比賽。通過金、銀等級的資格賽，鑑定為金、銀等級的人，每個月才能獲邀參加金、銀等級的比賽。

如果沒有參加資格賽，又想要晉升等級，就必須在賽事中有傑出表現。每次月賽結束後， USACO 會主動寄送升級的邀請函，給表現優異的選手。

金等級滿困難的，水準相當於 ACM-ICPC 區賽的中上題目。銀等級是基礎演算法的應用。銅等級是只要懂得寫程式就行了。

每次月賽會提供 48 小時的緩衝期，期間內隨時都可以參加比賽，開啟題目後，才開始計時。比賽時間是兩小時三題，作題時間相當充裕。每一題都有約十組的測試資料，途中可以不斷上傳解答程式碼進行測試，以最後一次上傳的程式碼為正式解答。評分方式採部分給分，每答對一組測試資料都會得到分數。

賽後兩天左右，會公佈成績，提供題目講評與解答。講評與解答都是開放給所有的人，是一個非常好的學習資源。想要提升自我實力的人，一定要多看金、銀等級的講評。

最後是小叮嚀。 USACO 的題目是有版權的，請不要隨便在公眾網路上張貼題目、張貼解答程式碼，這會讓管理員很頭痛。 USACO 也嚴禁比賽作弊，被抓到作弊者，將會永久停權，並且成為國際之恥。曾有國家因為不遵守規矩而被禁賽，請各位三思。

TopCoder

TopCoder

http://www.topcoder.com/

這個網站是現下最流行的程式相關網站。網站功能眾多，其中有一個部分是競賽，競賽的其中一個部分是演算法競賽。在這裡舉行的演算法競賽十分多，平均每個禮拜就有一次比賽， Google Code Jam 剛開始也是在這裡舉行的。在這裡舉行的演算法競賽也有很多類型，最常舉辦的比賽類型就是 Single Round Match ，簡稱 SRM ，至今已舉辦過 450+ 場，是最簡易的競賽類型，其他還有馬拉松競賽、多回合競賽等等。某些大型比賽是有獎金的，例行賽的出題者也有獎金，因而吸引很多網民在 TopCoder 出沒。

比賽說明

http://www.topcoder.com/wiki/display/tc/Algorithm

大致上分為三個階段：第一個階段是程式解題，自己寫好解答程式碼，自己測試後沒問題就可以上傳，等候批改；第二個階段是找別人程式碼的漏洞，自己擬好測試資料去測別人寫的程式碼，測出漏洞後自己可得到分數、別人會降低分數，但是實施測試卻測不出漏洞，自己就會被扣分；第三個階段是由系統幫大家批改程式碼，並且統計分數。

通常比賽題目會有兩套，分別叫做 DIV1 和 DIV2 ，積分比較高的使用者會以 DIV1 進行比賽，積分比較低的使用者則以 DIV2 進行比賽，想當然 DIV1 的題目比 DIV2 的題目難得多了。兩套題目分別都是三題，但是三題的難度是不同的，有不同的給分，解出難題則會得到比較高的分數。比賽結束後會依該場比賽的答題情況以及排名名次，重新計算個人的積分。大家平時在練習時，可以直接做 DIV1 分數最高的題目，沒必要做分數低的題目，如此學習效果較好。

演算法競賽的部分，可以從 TopCoder 網站左邊的選單中找到，路徑是 Competition 下面的 Algorithm 。第一個選項 Launch Arena 是打開 TopCoder 用於演算法線上競賽的一套軟體，這套軟體叫做 Arena ，是一支 Java 程式。 Arena 跑起來之後，以個人的帳號密碼登入，就會出現一個介面，在上面可以直接參加比賽，也可以瀏覽過去的比賽題庫，也可以進行解題練習，就跟一般的 Online Judge 提供的功能差不多。另外 Arena 還有聊天系統，還有一些個人環境設定等等的功能。

Arena 還有一套寫程式的介面，使用者也可以直接在 Arena 上面編寫程式、執行程式、設計測試資料並測試程式。比較麻煩的一點是，解答程式碼必須包裝成 class 的形式，程式進入點的 member function 需按照題目規定來撰寫，系統才有辦法幫你批改和測試。也因此有很多人幫 Arena 寫了外掛，自動幫你處理這些繁瑣的問題，讓這個寫程式的介面更好用。

第二個選項 Statistics ，有很多關於比賽的資訊，第一個選項 Match Archive 會列出亙古迄今舉行過的演算法競賽，另外有一個 Promblem Arcive 則是列出亙古迄今的所有比賽題目。另外還有一個重要的選項是 Match Editorial ，可以觀看賽後講評，大部分的比賽都會提供詳細的解法以及解答程式碼，是個很好的學習教材。

這裡僅做些拋磚引玉，詳細情形大家可以自行去了解一下。

Project Euler

Project Euler

http://projecteuler.net/

這個網站專門提供能用程式計算出答案的數學問題。每個問題都有固定一個答案，自己撰寫程式計算出解答後，只要在題目下方的表單中將答案輸入進去、上傳答案，就可以看到解題結果了。
回到首頁
Online Judge System
USACO
TopCoder
Project Euler