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 讀不懂題目真吃虧...
張貼者：
小月的耍廢日誌
於
清晨7:43
以電子郵件傳送這篇文章BlogThis！分享至 X分享至 Facebook分享到 Pinterest
沒有留言:
張貼留言