2017年4月19日 星期三

世界級的演算法比賽們

關鍵字:年度演算法競賽、大型演算法比賽、國際演算法比賽、演算法比賽有哪些、能獲得T-shirt 的演算法比賽、總之就是有機會獲得免費機票免費住宿去國外交朋友的比賽啦!

= = =

試用了一下 Google,似乎中文都搜不到類似主題的文章,英文的 wiki 雖然也有,但也很不齊全,畢竟這是非常小眾的東西吧 www

那就由身為演算法比賽狂熱者的小月來寫一篇吧!

1. Google Code Jam (Distributed Code Jam)


基本資訊
比賽相關的連結:https://code.google.com/codejam/
比賽季節:4 至 6 月
第一屆舉辦年份:2003
2016年參加人數:25288
獲得 T-shirt 人數:1000
現場賽錄取人數:26
私心評價難易度:★★★★☆

比賽模式
作答方式:一般而言,每題有會根據數據範圍的不同分為小測試資料和大測試資料,測資下載後要在規定時間內(小測資約 4 分鐘,大測資約 8 分鐘) 上傳答案以及答題所使用的程式碼。小測資在賽中就可以知道是否答對,大測資則要等到比賽結束後才能知道。每題的大小測資擁有不同的分數,若兩人總分相同,則比誰最後一個解題成功的 Submission 比較早。每次小測資失敗都會有 4 分鐘的罰時。

Qualification Round:超過 24 小時的資格賽,達到規定的分數即可晉級。

Round 1:共有A, B, C 三場,每場會在連續三個周末的不同時段,各 2.5 小時,其中一場達到前 1000 名即可晉級,通過一場後就不能參加其他場。

Round 2:只有一場,為期 2.5 小時,前 500 名晉級,前 1000 名有 T-shirt。

Round 3:為期 2.5 小時,前 25 名可與上屆冠軍一起參加決賽。

Final Round:所有參賽者會被邀請到 Google 的某個分部參加決賽,為期 4 小時。

台灣之光
2009 年: Jiunru (Rank 14)
2014 年: shik (Rank 14) 
2015 年: peter50216 (Rank 6), STEP 5 (Rank 19), betaveros (Rank 23)

小月講評
做為想接觸大型演算法比賽的新手,Google Code Jam 算是最適宜的吧,再怎樣,資格賽都可以讓你有一整天的時間慢慢寫 XD。為什麼難度會只給四星半呢?因為 google 的員工不能參加,所以就少掉不少很強的競爭對手了 XD

另外,有一個關於參賽者個個像統計資料料的網站:https://www.go-hero.net/jam,可以看到各個國家的晉級人數以及大家寫的程式語言分布,頗有趣的。


Distributed Code Jam

基本資訊
比賽相關的連結:https://code.google.com/codejam/
比賽季節:5 至 6 月第一屆舉辦年份:2015
2016年參加人數:898
獲得 T-shirt 人數:500
現場賽錄取人數:15
私心評價難易度:★★★★

比賽模式
作答方式:這裡就不敘述了,詳情請參考 2016 年台灣晉級決賽的 tmt514 所寫的介紹,這個比賽並不只是普通的演算法比賽,還考你分散式系統、平行計算的概念。

Round 1:只有 Google Code Jam 晉級 Round 2 的人可以參加 Distributed Code Jam 的 Round 1,會舉辦在 Google Code Jam 的隔天。共三小時,前 500 名可晉級到 Round 2。

Round 2:至 2017年(第三屆)為止,第 $x$ 屆有 $5 + 5 \times x$ 個人可與上屆冠軍一起參加決賽。(也就是今年有 20 個人可晉級。) 共三小時。前 500 名有 T-shirt。

Final Round:和 Google Code Jam 同地點舉辦,但不會在同一天,所以兩個比賽可能同時晉級。為期 4 小時。

台灣之光
2015 年:shik (Rank 3), Kirino (Rank 10)
2016 年:tmt514 (Rank 9)

小月講評
這個比賽小月剛好在第一屆還沒什麼人知道這個比賽在搞什麼的時候撿到車尾啦!不僅是吊車尾晉級的,決賽結果也是吊車尾 T_T

由於業界很需要平行處理問題?所以這個比賽大概會想要搞得像 Google Code Jam 一樣大?但礙於 Distributed Code Jam 的評測方式,想必他將會持續以 Google Code Jam 進 Round 2 當作門檻,且就小月個人觀感而言... 晉級的所需的技能和寫一般演算法競賽所需的技能沒差多少,大概差在寫 Distributed Code Jam 你需要更高的穩定度吧 XD 因為根據前兩屆的經驗,比賽結束時得到 Judge 結果前的 Score board 和最終結果的 Score board 差距頗大,畢竟解小測資和解大測資的難度差太多了。

2. Facebook Hacker Cup


基本資訊

比賽相關的連結:https://www.facebook.com/hackercup/

比賽季節:12 至 2 月第一屆舉辦年份:2011

2017年參加人數:12804

獲得 T-shirt 人數:500


現場賽錄取人數:25
私心評價難易度:★★★☆

比賽模式
作答方式:每題只有一筆測試資料,測資下載後要在 6 分鐘內上傳答案以及答題所使用的程式碼。全部題目都要等到比賽結束後才能知道是否答對。罰時的計算方式為所有答對題目的 (上傳時間 - 比賽開始時間) 的總和。


Qualification Round:為期三天,至少答對一題即可晉級。

Round 1:只有一場,為期 24  小時,前 1000 名可晉級。



Round 2:只有一場,為期 3 小時,前 200 名晉級,前 500 名有 T-shirt。


Round 3:為期 3 小時,前 25 名可晉級決賽。

Final Round:所有參賽者會被邀請到 Facebook 的某個分部參加決賽,決賽有四小時。

台灣之光
2012 年: kelvin (Rank 9) (偷偷爆料全場只有 8 個人不是 0 分 XD)
2014 年: shik (Rank 10) 
2016 年: shik (Rank 3), kelvin (Rank 21) 

小月講評
最初四屆的題目還蠻難的,但到最近,題目邏輯難度變得比較簡單,類型趨向是考你實做穩不穩定,細節能不能想清楚。小月可是 2016 年和 2017年都有進決賽才敢公開這麼說 XD。這個比賽 Judge 結果出來前的 score board 和出來後的差距頗大,根據小月經驗,題目給的 Sample 都是難以測出 Bug 的測資。

註:這個比賽向來對台灣人很不友善, Round 2 和 Round 3 選在 凌晨 2:00 ~ 凌晨 5:00 這種只適合大學生的時間,且近幾年 Round 3 都在農曆過年期間...

3. Topcoder Open Cup



基本資訊
比賽相關的連結:https://tco17.topcoder.com/ (每年會換)
比賽季節:3 至 9 月第一屆舉辦年份:2001
2016年參加人數:1500 ~ 2500
獲得 T-shirt 人數:???

現場賽錄取人數:25
私心評價難易度:★★★★★

比賽模式
作答方式:分成 Coding Phase 和 Challenge Phase。 Coding Phase 有 75 分鐘(總決賽為 85 分鐘)。共有三題,三題有不同的分數(約為 250, 500,1000)。但至從打開 (打開這個詞對沒參加過的比賽的人聽起來應該很玄吧XD 總之參加後就知道了) 一題後愈晚上傳答案,分數就會變得愈低。 Coding Phase 結束後休息 5 分鐘,進入 Challenge Phase,可以自己生測資挑戰同個 Room (每場比賽會把 20 至 30人分到一個 Room)的人的 Code,挑戰成功一次分數增加 50 分,挑戰失敗扣 25 分


Round 1:有三場,每場前 750 名且分數大於 0 即可晉級。(但近年來,參加人數過少,只要 分數大於 0 就能晉級)

Round 2:有三場,每場前 50 名晉級。最近似乎沒 T-shirt !?



Round 3:共有兩場,每場各取 $x$ 人晉級,$x$ 通常不超過 12,最近兩年 $x$ 變小了...今年 $x = 5$ 


Final Round:所有參賽者會被邀請到美國西岸某個地方參加決賽。決賽方式很複雜,每年都不太一樣。

台灣之光
2013 年: peter50216 (Rank 2), kelvin (前 16 強)

小月講評
這是小月所知最古老的面相全世界的演算法個人比賽了。但由於他的比賽介面對現代人(新手)來說非常難操作,所以近五年參賽人數愈來愈少,都是資深玩家在玩吧?實際上 Topcoder 並不只有演算法比賽,甚至連 UI 設計等等的比賽都有,大家可以找找看有沒有其他有興趣的比賽領域,說不定一不小心就能闖進決賽了 www。小月曾經因為幫忙 Topcoder 出過很多題目而有幸被邀請到決賽現場參觀,他們的場地設計是所有我看過的演算法比賽場地中最有競技感的 XD

4. Yandex Algorithm



基本資訊
比賽相關的連結:https://contest.yandex.com/
比賽季節:4 至 6 月第一屆舉辦年份:2013
2016年參加人數:1243
獲得 T-shirt 人數:512
現場賽錄取人數:25
私心評價難易度:★★★

比賽模式
作答方式:這個比賽的賽制和晉級制度複雜到足以寫常常一篇文章來探討... 這裡就先隨便講一下,想深入了解請參考 https://contest.yandex.com/algorithm2017/rules/,每年可能會有些許變更。大致上講起來就是,比賽長度為 100 分鐘,共有六題,題目都偏簡單(跟其他演算法比賽賽相較之下)。每題可以選擇 Open Submit 或 Blind Submit,Open Submit 可以立刻知道結果,Blind Submit 要等到賽後才會知道結果,但若選擇 Blind Submit,你的 penalty 就會根據該題 AC 人數減去某個值。而能否晉級前 25 名是根據 Round 1~3 的總積分決定,前 25 名會有不同的積分值。


Warm-Up Round :100 分鐘,答對一題即可參加 Round 1 至 3。

Qualification Round:可以選擇給定的 48 小時內的自選連續 100 分鐘參賽,也是答對一題即可參加 Round 1 至 3。



Round 1、2、3:每場會落在不同時段,但為了拚積分,最好每場都參加。


Final Round:所有參賽者會被邀請到俄羅斯某個地方參加決賽。決賽也是只有 100 分鐘。

台灣之光
2013 年: peter50216 (Rank 3), Kirino (Rank 19)
2014 年: peter50216 (Rank 5), tmt514 (Rank 21)

小月講評
這個比賽,小月也是在第一屆還沒什麼人知道的時候,靠著每場快速解出簡單題拿少少的積分晉級決賽,之後就無緣進決賽了 >__<。總之這個是自認寫扣速度很快但不太能解難題的人可以衝衝看的比賽。

5. Code Festival (Host by Atcoder)



基本資訊
比賽季節:9 至 10 月第一屆舉辦年份:2016
2016年參加人數:1500~3000
獲得 T-shirt 人數:0

現場賽錄取人數:20
私心評價難易度:★★☆

附註:限學生或畢業未滿四年的待業中的人才能參加決賽

小月講評
去年是第一次辦,之後到底會不會繼續辦舉辦方式會不會一樣呢~有待考證。大概是因為這是面相學生,讓非常多公司能接觸廣闊的人才的比賽,所以線上賽的題目很簡單,但決賽題目就很難了 www

台灣之光
2016 年:shik (Rank 10)

6. Snack Down (Host by Codechef)


基本資訊
比賽相關的連結:https://www.codechef.com/snackdown/2017 (每年會變)
比賽季節:5 至 7 月
第一屆舉辦年份:2015 (第二屆以後才邀請外國人到現場參賽)
2016年參加人數:1500~3000
獲得 T-shirt 人數:0
現場賽錄取隊數:25隊(每隊 1~2 人),但只有前 15 隊會補助機票
私心評價難易度:★★★★ (以兩個人而言的話)


台灣之光
2016 年:con217 - shik, STEP5 (Rank 4)

小月講評
今年是有現場賽的第二年,以後到底會怎樣呢我沒把握所以也懶得寫詳細比賽資訊啦~,反正決賽前的比賽重點只有一場,而那場的比賽模式和 ICPC 差不多,一種只有兩個人挑戰 ICPC 的 Regional 的感覺。順帶一提,外國人不能去現場賽的那年,決賽 peter50216 + kelvin 第五名, dreamoon + shik 第六名。是說今年的資格賽也快開始了,大家可以玩玩~


結語

實際上,若不考慮面向全世界的比賽,或是把機票要自付的比賽也考慮進去,就會有超多比賽可以列出來,也有些專搞招聘的公司也會辦乍看之下是面向全世界的演算法比賽,但這些比賽題目難度和以上所列的比賽有差距,參加的人也很偏重某些地區,我就不列上來了(其實第五項比賽也算是這種比賽,但由於是 rng_58 辦的全世界的強者還是都慕名而來了(?))。至今為止我覺得大型比賽的密度也快飽和了吧~但還是希望哪天 tmt514 能辦場面向全世界的演算法比賽 ~