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 讀不懂題目真吃虧...