2017年5月7日 星期日

MTF0000 題解

原本的文章吃光光,標題也換了,內文全部完成後移到 HackMD 上去了

---> https://hackmd.io/s/Skhbuv21W


不得不說...我好廢完全不知道怎麼用 Blogger,使用 HackMD 後整個美感差好多 QQ

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 能辦場面向全世界的演算法比賽 ~

2017年3月19日 星期日

農場例行賽 #27 超不負責任快速講評

Problem A --- Longly Dreamoon 3

若沒有把非遞增或非遞減的序列排除,這題就超簡單的,所以就加上了把非遞增和非遞減序列排除的條件,但似乎這樣改後難度就高了很多...

首先,若 $N = 2$ 或全部的數都一樣,則輸出 -1。


接著,不妨假設題目給你的序列是非遞減數列,也就是 $a_1 \le a_2 \le \ldots \le a_N$,並令 $d_i$ = $a_{i+1} - a_i$。而我們想要輸出的序列必須滿足存在某相鄰兩數 $= \displaystyle\min_{i=1 \sim N-1} d_i$。


於是呢...我們就稍微修改一些原本的非遞減序列,把第一個數移到最後面或把最後一個數移到最前面。第一個序列相鄰兩數的差會保留 $d_2, d_3, \ldots, d_N$,第二個序列會保留 $d_1, d_2, \ldots, d_{N-1}$,所以這兩個序列一定有一個是我們要的答案。

P.S. 此篇故事純屬虛構, Dreamoon 沒有心儀的對象。


Problem B --- Dreamoon and MRT

有些人可能有發現,開賽沒多久時限突然從 1 秒調為 2 秒,這是因為快開始的時候,測題者寫了一個 1 秒執行不完的解答,我突然覺得這題時限設一秒可能對大家來說有點難...才改為兩秒。

但這題再怎麼說也只是個 $O(2^m)$ 的模擬題而已,寫個遞迴,對於第 $i$ 次搭捷運,模擬往左或往右兩個可能。由於 $d_i \le 10^5$,所以模擬過程離起點最遠的距離不會超過 $2.5 \times 10^6$ 我們只要開個陣列就可以記錄某個點有沒有走過。有些人會先寫個 for 迴圈讓 $i$ 從 $0$ 跑到 $2^N$,再用 $i$ 的每個 bit 的值代表要往左或右。這也是常見的寫法,但他的複雜度是 O(m * 2^m),若時限只有一秒就很有機會 TLE。


Problem C --- Everyone look forward to high rating user 2

這題的重點是了解題目,並用 STL 的 set 模擬就行了,每次分數的改變都會對應到 set 的移除和插入的操作各一次。並且每場比賽結束後,就把 rating 低於 dreamoon 的人從 set 裡移除即可。


Problem D --- Lonely Dreamoon 4

這題是 DP 題。

先假設 Input 給的數是從小到大,也就是 $a_1 \le a_2 \le \ldots \le a_N$,並令 $d_i = a_{i+1} - a_i, s = \displaystyle\min_{i=1 \sim N-1} d_i$。

想像一下我們有個空序列,現在要依序把 $a_1, a_2, \ldots$ 插入序列裡,過程中,我們關心兩件事:有多少組相鄰兩數的差的絕對值為 $s$ (記做 $x$),以及最新插入的數是否和他相鄰的某個數的差為 $s$ (記做 $t$,可能值為 true/false)。於是 dp 的狀態為 dp[插入了幾個數][$x$][$t$],轉移就自己想像吧~


Problem E --- Guess the generator parameter

這題是怪題。

如果只從因數和公因數的角度去思考這題,大概很難想出什麼好作法(我是想不到啦)。有件重要的事情是:每個數的範圍介於 $a$ 和 $b \times 10^9$ 之間。

首先,先把 $1000$ 個數排序,重新編號為 $a_1, a_2, \ldots, a_{1000}$,我們拿比較大的一些數來兩兩曲最大公因數,可以相信, $b$ 會出現在這些最大公因數之間 (這是可以用很數學的方式出算出機率啦...但這裡略過),於是我們就先把這些 $b$ 的候補列出來。接著,我們要把幾乎不可能是 $b$ 的數移除。

首先,若取最大公因數的兩數都是 $b$ 產生的,那他們的最大公因數 $g$ 若不是 $b$,就會是 $b$ 的倍數,但若他是 $b$ 的倍數,$a_{1000} / g$ 會不超過 $5 \times 10^8$,若 $g = b$,則 $a_{1000} / g$ 應該會很接近 $10^9$ 才是,故我們可以把這樣的數淘汰掉。

接著,若取最大公因數的兩數分別是由 $a$ 和 $b$ 產生的,且 $a \ne b$,則他們的最大公因數 $g$ 會和 $a_{1000} / 10^9$ 差距很大,要不然就是其實也是 $b$。

最後。若取最大公因數的兩數都是由 $a$ 產生的,若他們的最大公因數 $g$ 和 $a_{1000} / 10^9$ 差不多大,則這個數幾乎可以確定就是 $a$,且幾乎只發生在 $a, b$ 很接近且都很大的時候。

於是,我們得到了 $a$ 或 $b$ 的候補,若我們已經確定了一個數,就可以把 $a_1$ 至 $a_{1000}$ 中不可能由該數產生的數去取最大公因數,就能得到另一數了。

這題相信還有很多做法可解,大家可以分享看看自己的做法~