2017年7月2日 星期日

2017 Facebook Hacker Cup(FHC) 世界總決賽參賽紀錄

今年難得晉級了好多個總決賽,花點時間來把決賽的比賽過程紀錄一下,讓自己對過去所犯下的罪孽深重的錯誤有更深的印象 >__<



FHC 的決賽總共是四小時,今年總共有六題

開場先看了一下這次題目的分數分布:12-16-16-18-19-19

是標準的 AC 題數多名次一定比較前面的分數分布哪...(關於這件事我曾經出成系列題目XD Score Distribution 系列)

可以相信第一題一定是相較起來簡單很多的一定要拿到分數的題目

所以我豪不猶豫的從第一題開始讀起。

第一題題目意思是:

請問在所有每個數的值都介於 $1 \sim H$且大小為 $R \times C$ 的整數矩陣,把每行及每列的最大值按照順序寫成一個數組,請問有多少不同的數組?($1 \le R,C,H \le 10^5$)

題目意思雖然那麼簡短,可是題面包裝得很複雜,我至少看了五分鐘才看懂題目吧...

就第一眼的直覺,這題要不是 dp 就是純粹的組合數題,要點就是先掌握一下可能的數組有什麼關鍵性質吧,所以我就先畫了簡單的一些例子,並觀察到:所有行的最大值的最大值和所有列的最大值的最大值一定一樣,說這件事適用觀察到的應該還蠻蠢的啦XD總之這是個很理所當然也不須要怎麼證明的事情。

我注意到這點的時候...已經有人 submit 這題了...所以可以相信這題的 code 應該很簡短很好寫?

但注意到這點到底有什麼用呀?於是接下來就想要大膽猜測:所有只要滿足這個條件的任一組數組,都能構造出對應的矩陣。

於是我有事圖畫了很多例子想證明這件事,其實我也有想過不要真的去證明直接把它當作是對的,但由於就算這件事是對的也沒有馬上知道要怎麼做,所以還是先給個證明增加信心。

花了些許時間後終於證出來了,接下來下一步就是想個排列組合公式解這題,這邊我也花了些許時間才想到作法。

這題的做法很乾淨很簡短,可是我寫完的初版 code 並沒有過 Sample...

我又花了些許時間才 de 出 bug...

比賽過了約 30 分鐘我才 submit 了第一題

沒記錯的話,我大概是第 14 個 submit 這題的人吧,而且已經有人連第二題都 submit 了 0.0

開場就感到些許絕望...


接著看了第二題

這題題目敘述更是複雜了...

我看了 20 分鐘左右都還沒有足夠的理解題目,以至於一剛開始以為這題只是超蠢的二分圖判斷類的題目。

但寫完後 Sample 卻錯了好幾筆測資,接著 debug de了不少時間後,最後一個測資怎樣也過不了樣例,於是我下狠心用手畫圖親自用人腦解該筆測資。

為什麼我會說下狠心呢?因為該筆測資是有超過 20 個點的 graph...

後來我發現我對題目有些微的認知錯誤,或者是說,我作法想歪了,這題並不只是超蠢的二分圖判斷,而是先做完二分圖判斷後,若是二分圖,還得找個二分圖最小點覆蓋...

說起來,這道題很裸啊!!!只是他題目敘述包得很複雜而已,我很不喜歡這類的題目唉...

得到正確的作法後,我對原本的 code 在稍作修改,又 debug 了一陣終於過了 Sample,並 submit。


這時比賽已過了一個半小時左右,看了下 scoreboard,我的名次仍舊落在 15 附近的中後地段 (決賽只有 21 個人參加)

但比賽仍有兩個半小時,前面兩題事都算是我寫的很不順利,若後面的題目寫的順利些,應該還是有機會翻盤。

於是我按照順序先看了第三題

這題讀題也是花了不少時間吧...

理解題意後,想了一下覺得細節好複雜喔,沒有很好的思緒能理清該從哪裡下手解這題,這時再看看 scoreboard 

發現有一兩個先傳了第五題,於是決定再繼續看第五題

第五題倒是一下就理解了題目,且稍想了一下我馬上就知道怎麼做了!

就只是個矩行面積覆蓋類的線段樹問題嘛!

這時覺得說不定有機會名次衝上去了!


但剩下的兩個半小時已經沒什麼話好說了

一直以來我寫線段數的問題似乎都很容易卡住,這次也不例外

而且我找最久的 bug 竟然是線段數初始化的位置擺錯...超蠢的T_T

submit pE 時間只剩下一個小時, scoreboard上有許多人都已經傳了 5 題,已經傳四題的人更是多,

到這時已經拉開題數差距,再加上我讀題總是很慢,看來再怎樣我都頂多只能四題了

這時我稍微想了下,我要直接繼續想第三題呢?還是在開新題目來讀?

看了下 scoreboard,覺得寫A、B、C、E 四題似乎分數還是有點慘烈,但 F 也有可能因為比較難而到賽末都寫不完,並且此時傳 D 的人比 C 還多,於是我決定看 D 的題目。

這算是做了錯誤的決定吧...

不知道怎麼搞的,我讀題讀了 20 分鐘左右,卻對題目在搞什麼連皮毛都還沒摸到... 超慘烈的啊!!!是因為我太緊張了嗎?還是我英文就是真的這麼差= =

在比賽剩 40 分左右時我放棄理解 E 的題目意思了,回去思考 C 怎麼做。

這時大概心很慌吧,就開始想到什麼就寫什麼,Sample 錯了就想想到底還要補些什麼,直到比賽結束都一直在做這樣的事情。

比賽結束時只寫了三題,這時在 scoreboard 上的名次是第 16 名(先當作大家有傳就有 AC 來做排名),超慘的啊。


開獎後,我 pB fail 了...故實際上只有 AC 兩題,最終排名為第 15 名。

這次前四名都是 AC 5 題,明顯感受到和大家的穩定性差距呀...(我說穩定性是因為,我沒答對的題目並不是我不會,只是我沒時間去理解或思考,因為花太多時間在寫其他題目上了...,剩下的題目我一定都能想到!)

P.S. 1 比賽結束過後,開獎過程中,我都一直在思考 pC 正確做法到底是什麼,大概想了 20 分鐘才想到,並發覺我賽中最初填上去的 code 離正解實在是太偏了,由那種 code 當起點東補西補怎麼可能改成正確答案呀...

P.S. 2 之後我看了再認真檢查我 pB 的程式碼,發現我最後傳的 code Bug超多,其實連 Sample 都沒有過... 只是不小心矇對了原本唯一錯掉的最後一筆測資,就被我當成所有測資都過了 Orz。

P.S. 3 最後六題 AC 人數分布為: 21、11、10、14、9、4。大概可以看出 B~E的難度根本沒什麼差...甚至 pD 可能還比較簡單,我 pD 讀不懂題目真吃虧...

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)
2017 年: dreamoon (Rank 15) 

小月講評
最初四屆的題目還蠻難的,但到最近,題目邏輯難度變得比較簡單,類型趨向是考你實做穩不穩定,細節能不能想清楚。小月可是 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)
2017 年: shik (Rank 4), Kirino (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)
2017 年:dreamoon_shik (Rank 4)

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


結語

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