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)
2017 年:eddy1021 (Rank 16)

小月講評
這個比賽小月剛好在第一屆還沒什麼人知道這個比賽在搞什麼的時候撿到車尾啦!不僅是吊車尾晉級的,決賽結果也是吊車尾 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)
2018 年: Kirino (Rank 18)

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

5. Code Festival (Host by Atcoder)



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

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

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

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

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

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

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}$ 中不可能由該數產生的數去取最大公因數,就能得到另一數了。

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

2017年3月17日 星期五

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

由於現在是個忙碌的上班族...題解就隨便講一下吧...

Problem A --- Guess the Number


這題我似乎估太難了?似乎大部分的人都會做嘛!

由於對於一個數愛麗絲心中所想的數 $i$ ,隨著艾利斯的猜測可能的範圍下界會愈來愈大,上界會愈來愈小。所以我們從 $a_1$ 看到 $a_N$ ,若 $i = a_x$,我們去找到比 $i$ 小的數中,艾利斯最後猜的數字是哪個,記做 $low_i$,以及比 $i$ 大的數中,艾利斯最後猜的數字是 $high_i$,並令 $dp[i][0]$ 為猜到 $i$ 的過程中會猜到幾個比 $i$ 小的數,以及令 $dp[i][1]$ 為猜到 $i$ 的過程中會猜到幾個比 $i$ 大的數,於是我們有 $dp[i][0] = dp[low_i][0] + 1$ 及 $dp[i][1] = dp[high_i][1] + 1$,於是第 $i$ 行只要印出 $dp[i][0] + dp[i][1] + 1$ 就好啦!細節請自行想像囉(可能要用一些簡單的 STL或資料結構。)

Problem B --- Swap Color

這題我估太簡單了...? 

$k=1$ 的測資,只要去數相鄰的格子對有多少組是顏色相異的,並且看看是否存在一組相鄰格子對顏色相同,就可以算出答案了~

$k = 2$ 的測資呢 ...依照有多少格子與原本的格子顏色不同個別處理,不同的個數只可能為 $0$ 或 $2$ 或 $4$。

相差為 $0$ 的一定辦的到。

相差為 $2$  的,又可在分為兩種情況,第一種為兩格相鄰,第二種诶兩格距離為 $2$。實際上若相異的格子對距離為 $1$ 或 $2$,在 $n, m \ge 2$ 時,一定有辦法用恰兩步交換構造出來 (若 $n = 1$ 或 $m = 1$ 就不一定囉!原本想說我沒有考這種情況已經夠善良了 XD)

相差為 $4$ 的,一定可以用兩組相鄰為的異色格子湊出。所以我們就計算兩組的組合有幾個,在扣掉有重疊的部分,重疊的情形有兩種,一種是重疊在黑色個子,另一種是重疊在白色格子,最後還要要在扣掉形如 "WB\nBW\n" 或 "BW\nWB\n" 的情形,因為有兩種可能的組合都會算到他。我自認為很善良的把這種情形放在 範例測資裡,不知道大家有沒有看到呢 @@

像這種題目啊... 若是出在 TOI 這種長時間的比賽,不如寫個暴搜的程式碼,在隨機產生小測資,驗證自己的答案是否正確,通常你寫的若是錯的,大概 $2 x 3$ 的測資就會讓你錯掉,你就可以想想看你是否漏想了什麼。

Problem C --- Count Simple Cycles

小測資直接暴力搜索就行了,可以自己試著估估看複雜度,當 $n = 10$ 時,就算是完全圖,遞迴搜索的步數也不多,但要注意是否會算到重覆的 Cycle,例如 $1-2-3$, $2-3-1$ 這兩種情形會不會重複算到,要步重複算到也有多種處理方法,可以自己想想看~

大測資的話,首先要知道 Cycle Basis ~,有了這個東西你就會知道 Cycle 數目一定不超過 $2^{18}$,所以也可以暴搜啦!!!

對不起這是騙你的。

要暴搜,首先要把度數為 $1$ 的點都拔掉,他們一定不會對 Simple Cycle 有貢獻,接著要把度數 為 $2$ 的點也縮起來,反正他連那麼長也沒什麼用, 就算把 $10^5$ 個度數為 $2$ 的點連在一起縮成一條邊也不會影響 Simple Cycle 的個數。

所以做完這些步驟後,掐指一算,會剩不到 $40$ 個點也不足 $60$ 條邊~,這個時候暴搜就可以過啦,但我不知道怎麼估這時暴搜的複雜度... 但就算不暴搜,我們也可以使用 Cycle Basis 的性質,好好做個 $O(2^{19} \times 60 )$ 之類的事情來解出這題,這裡就不細講了。

2017年2月28日 星期二

農場例行賽 #25 後記

這篇已經現在我的 FB 塗鴉牆試過水溫了,現在把他轉到這裡來 >__<
= = =
好久沒有為了準備一場農場例行賽感到如此焦躁了,於是決定把這次的經驗記錄下來,也讓大家看看一場農場例行賽是怎麼誕生的。
若不知道什麼是農場例行賽的朋友可以參考我們的粉專 競程日記 的關於頁面,啊不過似乎也沒什麼說明XD,總之就是每周辦該粉專的小編們會想辦法弄出一場有關演算法的程式比賽給台灣的學生們遊玩
= = =
起初的農場例行賽(在我還沒接手前,也就是第十場以前),有一半的題目(比較難的那一半)是挑現成的題目,剩下一半則是小編們自己出。
而我接手後,由於我無法忍受自己辦的比賽放著不是自己準備的題目,於是就改成全部自己出了。但出題目是件很花時間的事情,後來就盡可能到處拉人幫忙出題目,雖然我們一直釋放善意希望台灣的學生能自己來找幫忙出題目,但最初主動來找我們的都是非台灣的學生 0.0,那時覺得沒什麼拒絕的理由,就都答應了。
而昨天這場農場例行賽就是使用一位非台灣學生所提供的 problem proposal,雖然題目是根據別人提出的 proposal 出的,但具體細節以及要不是使用都是由我強烈的主觀所決定的 >__< 所以若覺得題目不好的話,千錯萬錯都是我的錯!
雖然是這樣說啦,這周的原定比賽時間是禮拜五,但這位出題者直到星期三晚上才跟我們說生不出最難的那題,大家看到這裡應該會問說,都有 proposal 且也被我同意了,為什麼會生不出來呢?這是因為,在當周的星期日時,他告訴我,他後來覺得這題放在最後一題太簡單了,他希望能搞出一個再難一點的題目,並告訴我他能在星期二以前完成。但到最後似乎沒有擠出任何點子...
其實我本來就有覺悟會遇到這種事,所以也沒受到太大動搖,於是就接手這份工作,開始思考我要怎麼補上這個洞。
原則上,我會希望,我能夠根據他給我的 proposal 來加強難度,達到能讓大家都滿意的標準,他原本給我的 proposal 是這樣的:

```
給一個連通且有權重的圖 G,每條邊的權重會是個與 t 有關的(一次/二次)式,給一個 t 所允許的區間 [t1,t2],求最小的 MST(Minimum spanning tree)。
點數(N) <= 100,邊數(M) <= 200,預期複雜度 O(M^3 log(N))。

P.S. 後來好友們表示,這題的單筆詢問版本其實曾出現在台灣的三四年前的國手選拔比賽中,也曾出現在 USACO 的題目中。
```

其實我看了 proposal 後就知道其實存在 O(M^2 log(N)) 的做法,可是覺得這個方法對我來說超麻煩,只跟他說:我覺得這題難度大概是第四題的難度(一般來說題目共五題,由簡單到難),且因為二次式的處理再加上去可能會太複雜(我不太喜歡硬是把兩個不同問題結合成一題的東西),使用一次式就好。
但現在為了要說服他原本的題目其實也夠難,所以就告訴他這個方法的存在,再把它改成多組詢問一定就足夠難了,並告訴他我會幫他生出解答。於是我決定放棄星期四晚上的打羽球活動來準備這題。
但星期四晚上有個意外插曲:星期五我們辦比賽的時間在星期四晚上才公告說也有一場 Codeforces 的比賽,Codeforces 就是我們借來辦比賽的平台,他們自己也辦了比賽的話我們就無法再同一時間辦比賽了。而且我相信若兩個比賽半在同個時間,大家會選擇參加 Codeforces 的比賽而不是參加我們的... 總之小編們因此決定把比賽時間一到星期日晚上。
由於我身性懶散,接下來的時間點就跳到星期六晚上了...
由於我所理解的 O(M^2 log(N)) 做法要使用到 Link-Cut Tree,並且這是個我從來沒有寫過的東西,整個就不知道要從何寫起... 又胡思亂想一陣後,決定還是先來寫個爛爛的時間複雜度 O(M^3 log(M)) 作法,但我連寫這個做法都覺得卡... 寫完後就冒出了自暴自棄的想法:其實就這樣出個 N,M <= 100 也沒有真的太簡單。而且當時已半夜兩點了,所以我就開始實踐這個自暴自棄的想法啦!首先來弄比 Sample Input 看看。
決定範例測資是一件很大的學問,你給的測資會影響題目的難度,如果可以使用很小的數據就涵蓋各種邊邊角角的 case,就能夠讓參賽者比較好理解這個題目的各個面向。以這題來說,我會覺得,點數和邊數少,且若隨著 t 的改變, 構成 MST 的 tree 也常常改變的話,那就是個好的、能讓大家容易理解的範例測資,於是我就構造出了三個點三條邊,且三種 spanning tree 都存在一段時間區間會是 MST 的測資,我把他們的函數圖形畫在紙上仔細端詳並看了我生的測資的答案後...
!!! 怎麼開始覺得 MST 對於 t 的函數圖形是凹函數... 這時我完全瘋掉啦!因為這若是凹函數,題目的設計就會變得很有彈性。我馬上敲卡恩叫他幫我一起想,到底這是不是凹函數,若是的話要怎麼證明。結果呢,證明方法其實超簡單的,卡恩馬上就想到了。很多數學證明都是這樣啦,沒人告訴你這件事是對的你都不會注意到,但告訴你是對的並叫你證明,卻有可能馬上就證出來。嗚嗚此時我感到超難過的,我沒有聽完題目就馬上聯想到他是凹函數的直覺...若當初有這個直覺得話,這幾天的日子一定很好過...不過這件事也再次驗證我在 ioicamp 所講的話:「通常畫一些簡單的測資能夠幫助自己更理解題目」。
所以說,若是凹函數,會有什麼好性值呢?是凹函數的話,一個區間的最小值一定發生在區間兩端啊!所以每組詢問只要做兩次普通的 MST 就可得到答案,再得到這個結論後,就覺得求最小值實在是有點蠢,也有點容易讓參賽者不小心就 AC,所以就把題目改成求區間的最大值,那麼你就還得用三分搜預處理出整個函數的最高點位置及高度。
於是之後就繼續把後續的事情處理一陣,包括決定數據範圍、生測資、測假解之類的,弄完的時候大概快六點了吧(倒),而 link-cut tree 的做法就從此不了了之,我也懶得測 link-cut tree 的做法能否通過我生的所有測資 (我的設定是希望若真有人寫 O(M^2 log(N)),應該要 AC 啦)。
就結論來看,不只有我沒這這個直覺,這場比賽的大部分參賽者也沒這個直覺(雖然是有一個人在 code 裡使用了三分搜,但他每個詢問都做一次三分搜就 TLE 啦),所以這題應該是有一般 Codeforces 比賽的 (Div. 2) E 以上的水準的。應該是有滿足客戶 (參賽者+原出題者?) 的需求 XD
= = =
最後拿整個事件來討論另一件事:出題能力和解題能力有關係嗎?這個問題雖然稱不上月經文,但每一兩年還是可以在 Codeforces 上看到有人討論。
首先先定義好這裡的「出題」是什麼意思,一般的演算法比賽的出題包括了「設計題目」和「提出解答」兩部分。「設計題目」就是題出一個有標準答案或有標準衡量答案的好壞的問題。「提出解答」則是給出一個解決這個問題的方法。
一般而言,我們用來評斷一個問題的好或壞的標準通常是:1. 設計出的題目,是否是一些 well-known 的問題,如果是,就會被大家嫌棄你這題只是個很多人都知道,會讓解過的人在比賽中受惠的「壞」題。 2. 提出的解答,究竟有沒有創意,是不是大部分人想不到的作法,若是,這題則是「好」題。
要避免 [1.] 的情形發生,那就是要看得夠多題目,才不會自以為想出一個新題卻是期很多人都看過的題目。而要達成 [2.] 的目標,需要的怎麼想都是解題能力吧?
順帶一提,如同時滿足 [1.] 和 [2.],那就可以發論文了吧,畢竟這代表著你在 well-know 的題目有嶄新的突破 XD
若大家判斷題目的好壞的標準真的和我所描述的差不多的話,你們是否有發現,若一個人很有創意的設計了很多問題,但都只是簡單題,那他也只是創造了很多不壞的題目而已;反之,若一個人偶爾才擠出一點題目,但解法都很精妙,那我們會說這個人出了不少好題。
好啦連我自己都覺得上面這段感覺上是在玩文字遊戲而已 XD 那就再舉個更極端的例子好了,若 A 提出一個問題,想了好久都不會,但 B 卻解出來了,你們會覺得誰功勞比較大呢?
說到這我就想到... 最近有個人寄信問我:「我想辦一場 Codeforces Div.2 的比賽,但目前還缺難題,我已經設計好題目了,你可以幫我想解法嗎?」看完這則信後,我思考了一下,想說剛好最近習得已讀不回的技能,也對他使用看看來提升技能等級...
拉回來 = =,總之,我覺得設計題目是相對容易的事,最近有另外一個人問我說,我到靠什麼來激發我出題的靈感?我回答說:「玩小遊戲、到戶外走走、看動畫等等」,他就回我說:「看動畫能提供你點子? :p 但我從未能從動畫中得到點子XD」
我來舉一個我在看動畫得到點子的例子:有一部動畫,在片尾曲的時候有一個人一直在螢幕裡走來走去,我看動畫的習慣是片頭片尾曲都會完整聽完,但這個時候沒有劇情嘛於是某天我看到這一目的時候就在想...如果他有留下腳印且左腳和右腳的腳印是可以區隔的...我有辦法根據他留下來的腳印知道他有至少有幾步是倒退走嗎?於是 Codeforces 578E 這題就誕生了。
我聯想到這樣的問題,大家會覺得很奇怪嗎?但我覺得聯想到題目這種事情感覺上也不是我自己能控制的啊,我個人是覺得,看看新東西,看看不同風景,都有機會激發題目的靈感,雖然那個片尾曲我也是看了好幾次,不知道為什麼突然其中一次就有靈感就是了...
但我覺得比起有靈感,更重要的是你是否會抓住那個靈感,認真去想突然在心中冒出來的問題,並真的把他解出來,以腳印這題為例,我冒出這靈感後大概又原地發呆了超過半個小時才想到解法。 (補註:以這個例子來講,半個小時其實算是花的時間超少,很多時候其實是想好幾天的...)
嗯...寫到這裡突然覺得我舉的這個例子似乎只會讓人覺得:你就天才吧!舉這例子只是想炫耀吧!我是能從你這個例子得到什麼收穫啦!
那我就拉回這段討論的原點吧,我原本是說,我是要拿前面所提到的,出這次農場賽最難的這題的事件來討論「出題能力和解題能力有關嗎?」這件事。這題「設計題目」的人就並不是我,但原出題者只提出了 O(m^3 log n) 的作法,若這題就按照他原本的 prposal 出出來,大家會覺得他是個好題嗎?應該只會覺得他就只是普通不壞的題目而已吧。對解題者而言,通常把時間複雜度壓到可以 AC 的程度後,就不會再想下去了;但身為出題者,則該盡可能的壓低演算法的時間複雜度,或是把題目調整成限定難想到的做法才能 AC 的數據限制。也就是說你一定得比參賽者還更了解該題目的各種性質,能做到這點,就意味著你擁有更高的解題能力。所以,你擁有更高的解題能力時,就愈能把「不壞」的題目變成一個「好題」。我想,我有在這場比賽確實地幫他把一個「不壞」的題目變成一個「好題」。

結論:出題能力和解題能力很有關係的!所以大家快來幫農場例行賽出題所不定也可以反向激發解題能力唷!(詭辯?XD)

2017年2月12日 星期日

農場例行賽 #23.5

為什麼會有這場奇怪的比賽出現呢?主因是 tmt514 和 drazil 在出題目時,常常會不小心舉出一些太偏離普通的演算法競賽或有些刁難的題目,於是我就想說,就辦一場讓大家隨心所欲、不限至題目類型的比賽吧~雖然最終看來...這些題目大部分還算是普通的 = =,大家還是很克制的沒有出真的非常奇怪的題目 (drazil 之前跟我舉了好多他想出的題目,但最後都自己否決掉了 XD)

這場由我生的題目有 B、C、F,A 和 E 是 drazil 出的, D 是 tmt514 出的。

我這裡就稍微解釋一下我出的題目大致上的獲得 AC 流程和對這些題目的看法,就不附上程式碼了。


Problem B - Everyone look forward to high rating user


會想到出這題是因為... 就如題目敘述所說的,我還蠻喜歡看這些關於厲害的人的表現數據的,但是我過去又很懶得研究 API 之類的東西,所以就沒有什麼動力寫程式碼列出我想知道的事情。

但最近工作後,其實每天做的事大概就是解這題所需要做的事情吧 = =,一直查一直查 tools 怎麼用,實際思考程式結構的時間挺少的。於是漸漸地對查 tool 怎麼用這件事麻痺了吧?把這提出成題目也不會給自己太大壓力,是個輕鬆三個小時左右就可以生完的題目。

先附上 Codeforces API 的連結。先聲明,我並不釋出完題目就知道用哪個 method 的,出題前我還不知道那些 method 怎麼用 = =,但至少... 這題要做的事用想的就覺得不太難,API 如果不能輕鬆得到結果的話,那這個 API 也太沒用了吧 0.0

我簡單地用 Python 試了幾個 method,最後決定使用 contest.ratingChanges 這個 method 來獲得 rating 資訊,因為我只要獲得每場比賽所有人的 rating change,就可以獲得這題所想要的結果了,而且只需要不到 $1000$ 個詢問,若你真的每個 Codeforces user 都詢問的話,由於它限制一個 ip 每秒中最多能詢問 $5$ 次,可能跑一天還跑不完吧 XD (不過我這樣寫可能還是要跑個十幾分鐘吧 )

使用了此 API 後,我就先把他丟給我的 JSON 檔案丟到 online json visualizer,例如 這個,於是我就可以快速地了解他的 json 結構,找到我想要的資料的位置,於是我就寫了一個能印出所有滿足 newRating > 2765的 (user, newRating) pair,之後再用 c++ 處理這些資料,把答案寫死在 code 裡,這題就大功告成了!

順帶一提,據說賽內唯一一個 AC 的人是肉眼一個一個看排名前面的人的 rating 的 ... 所以說我這題目並設計得不好,讓人還有機會不藉由 API 就在塞內獲得 AC... 應該要使用排名在一千左右的人當主角...。

P.S 可能還是有人想知道我 api 是怎麼使用的,我還是貼一下我的程式碼好了,但我對 python 真的完全不懂 >_<,相信熟悉 python 的人一定能有更輕省的寫法


Problem C - It's a hard problem that I believe you can't solve by yourself


這題則是標準的 OEIS 題,標題都說地那麼明白了,並不期望大家在三小時內寫出來啦... 若這種題目有那麼多人能在三小時內解出來,那麼那些研究這個問題的 paper 大概沒什麼太大的價值吧 XD

雖然這題是 OEIS 題,但也不是最簡單地把前三個數放進去就能找到答案的 OEIS 題。首先,你會注意到,第 $n$ 個數一定是 $n!$ 的倍數,所以我們就可以把它除以 $n!$,若你把前三項經過這樣的處理,或許就有機會找到答案了~但可惜的是,在我寫這篇 blog 的時候,輸入前三個數將獲得高達 $324$ 項結果,你要一個一個檢查是不是你想要的序列,可能比 Problem B 人眼搜索 Rating 前 $80$ 高的人還難吧 XD。

接下來要做的事應該已經呼之欲出了,寫個簡單的爆搜程式搜索出第四個數,就可以在 OEIS 上找到唯一的序列,剛好也就是這題的答案~ OEIS 上也有附了一個簡單明瞭的公式,使用它就能 AC 了。

若有興趣想深入研究這個問題,請自行翻閱 OEIS 附的 reference 吧。

最後提一下,為什麼我會選擇這個序列呢?這個問題其實是我當兵期間研究的眾多問題之一。有時睡不著就會亂想題目,有天開開心心地再這個問題上獲得了一個 $O(N^2)$ 的解,想要之後出在比賽上,但當時並沒有把解法記下來。直到退伍後才認真把 code 寫出來,但這時我只能做到 O(N^3),已經想不起來在軍中時 O(N^2) 的作法到底是什麼,抑或是根本當時就想錯了?但最後我還是把它當它寫成題目的 proposal 投稿到 SRM,結果卻被 cgy4ever 發現其實 OEIS 有這個序列!而且還有好多論文在研究這個問題!知道後整個崩饋 T_T 最後這題就不了了之啦~

最後的最後再提一下, 賽中唯一 AC 的人並不是靠 OEIS,而是 google 了關鍵字:"number of partitions with k-intersection matchings" 而找到相關論文的。

Problem F - This is a sign-in Problem!


這題就如同標題所說的,是個簽到題

近來我們發現,若最簡單的題目不夠簡單,我們無法準確地獲得有參加比賽的人數,所以比進行間多放一題簽到題。並且我們因為簽到題多捕獲了 3 個有讀題的人!謝謝大家的餐與 m(_ _)m