2018年8月18日 星期六

2018 Facebook Hackercup Round 3 流水帳

由於前兩年都進了 Facebook Hacker Cup 的 Final,所以壓力有點大,因為我向來自詡自己能到達的階段是不太會退步的 XD

開賽時中規中矩的從 pA 開始看。今年的題目似乎比往常的短很多,也比以前還要容易理解,但這題就算理解了題目,也是沒什麼想法呀...,想了幾分鐘後,就決定想到什麼就寫什麼,例如說:我想到了若有連續三個井字號,則這三個井字號以及後面的字源可以全部不用理會。又或是若有連續兩個井字號,下一個字元不是星號也不用理會。

總之就是想了各種條件,大概就是又分成答案是 $0$、答案是 $1$、以及答案大於 $1$ 的 Case,其實也就三種 case 啦...但是真的很難想的清楚,所以我提交時已經過了 45 分鐘了。

但以開場來說,這個速度其實還算正常,我是第 30 個提交題目的人,但真的正常嗎?這也很難說,因為可能其他人不僅已經提交了一題,而且還把所有題目看完了,但我剩下三題都還不知道題意。

接著我選擇看第二題,題目理解後沒什麼頭緒,說是沒什麼頭緒也不對啦,總之一定有複雜度超高的 dp 方法能做,但實在是高過頭,想了一下對於壓低時間複雜度的方法毫無頭緒,於是決定先看第三題。

第三題讀完我腦中就猜了個 Greedy 類的做法,感覺還蠻對的,但沒有仔細證,可是時間複雜度是 $O(N^2)$ 而這題 $N = 30000$,嗯...依照 Hackercup 過去以來的尿性,真正 $N$ 是滿的測資其實很少,相信 O(N^2) 也是能過的!於是我就直接寫下去了!但為了讓心裡更有底些,我在寫的過程中,同時也想著要把常數壓小,導致雖然做法簡單,但還是寫了很久,終於寫完後,卻發現我 Sample 錯掉了!!!

這可怎該怎麼辦?看來看去,都覺得我的程式碼寫得很穩呀,到底是哪裡寫錯,還是有哪裡想錯了?仔細分析了一下挫的那組測試資料,實在是看不出所以然...

這時比賽只剩約 70 分鐘...完了...完了...感覺一切都完了...但我還是繼續拼命地動腦 QwQ

我一直在想著,我的 greedy 方法到底拿理會錯調,想著想著,我突然靈光乍現,想到一個更穩妥的 dp 方法,雖然一樣不知道是不是對的 XD 不過它超好寫,於是我迅速的把它揉完,並發現 Sample 因此通過了,也沒時間再驗證做法正確性了...總之就傳吧 (>__<)

看了一下 scoreboard,我大概落在五十幾名吧...而且只剩一個小時左右了,這時才開始讀新的一題並且想+寫感覺時間不夠呀...但是第四題這時有好多人傳了喔...感覺不寫第四題說不定就沒機會晉級了...所以我開始看第四題,繼續把第二題擱著。

第四題讀完後覺得不得了不得了,這題的感覺和 tmt514 在今年某場比賽初的某題有 87% 像呀... 於是我先想了一下下正確性到底如何,但是...感覺時間不夠讓我好好證明 tmt514 用的方法是不是可以直接套用在這題上了,但感覺就是很對嘛!於是我就把之前那場我寫的程式碼找出來,改了一下後, Sample 就輕鬆全過了...就直接傳了吧,傳完後我的名次就進到前 25 名了。

剩下半小時,我還是努力有想要寫出個 pB 的代碼,所以我也是想到什麼就寫什麼,但是寫到剩下 5 分鐘時,發現我寫的方向錯掉了,很難修正...於是就放棄了 Orz,剩下時間就盯著 scoreboard 看。其實這個時候我的名次已經遠遠掉出 25 名外很多了,但我真的沒辦法在做什麼了吧 (>__<) 就一直觀察著我的名次我後落...

四點一到, score board 刷新後,發現我竟然三題都通過了!!!勉強的重新回歸前 25 名!這真是太令我感到意外了(?)我...我...就這樣又進到 Hackercup finallist 了 (>_<) Facebook 的出題群是不是要檢討一下呀 XD 連三年都讓笨笨如小月我這樣的人水進 final XD

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