[心得] Google Code Jam 2008 參賽心得

看板Soft_Job (軟體人)作者redray (澈)時間17年前 (2008/07/28 23:29)推噓8(8推 0噓 4→)

留言12則, 8人參與討論串1/2 (看更多)

這次趁自己給自己放假的時間，參加了 Google Code Jam 比賽，那是一個程式設計比賽，裡面有全世界的怪物參加。我那時候參加的動機是，想試試看自己有多少能耐，看看自己能走到哪一步，雖然我大概知道自己是到不了後面的比賽的，但是還是想試試。在他還沒比賽之前，有開放幾題的練習題給大家做，我做之後的感想是，這是數學與演算法的比賽，演算法方面我還算 OK，可是針對 Dynamic Programming 方面，我看到題目真的是沒有什麼直覺可以快速組織出如何使用 DP 演算法，畢竟上次使用 DP 大概是快五、六年以前，感覺似乎已經流失了許多，我看到許多可以使用 DP 的題目，但卻沒有感覺如何寫。所以比賽之前，我就猜到我應該會死在這一類的題目上面，因為有使用 DP 跟沒使用 DP 而使用最笨的方法解題，無論在解題時間或是執行時間上面都是差很多的。再來，我在練習題中，發現每三題之中一定會出一題以上的數學題目，像是求機率，求方程式...等等。哎呀！我又知道了，我大概 95% 也會死在這種題目上，我以前在數學上沒有下太多功夫，所以會死在數學題目上是應該的，只能碰碰運氣，看看能不能碰到正好會的。我稍微簡單的介紹一下他進行的方式，給你三題，英文出題，題目會跟你講輸入資料的格式是什麼，也會規定輸出資料的格式。他的輸入資料是給你下載的，其中又分小資料集檔案跟大資料集檔案，小資料集檔案一旦你開始下載，就開始計時，計時四分鐘，你必須把你所下載的檔案內容用某種方式輸入到你的程式中 ( 例如讀檔 )，然後輸出他所規定的格式的結果出來，放入一個檔案中，然後上傳你的輸出檔案與程式碼。而大資料集檔案，是你下載之後，給你八分鐘的時間，時間內也是一樣，把結果與程式碼上傳。大資料集跟小資料集，顧名思義，就是一個是資料量比較小，另外一個資料量比較大，資料量比較小的讓你可以先不用考慮最佳化，而資料量比較大的就一定要考慮最佳化，不然有機會會沒辦法計算出結果。但是我這次的經驗是，一開始最好就要考慮最佳化，不然你大概也沒時間考慮了，第二個經驗是，一定要先寫好讀寫資料的程式框架，這樣才可以節省時間。喔！對了，大資料集的正確性只有在比賽結束之後，你才會知道，而小資料集是在你上傳之後就會跟你說正確與否。資格賽沒多久就到了，他的時間給你 24hrs 來解三題，兩題演算法、一題數學題，演算法都可以使用貪婪方式解決，可是數學題目是幾何機率問題... @.@ 我一開始連機率都有點忘記，還要去看圖形，時間很快的過去，我解完了兩題演算法題目，然後最後一題數學題就在一頭霧水中沒做。不過資格賽只要你有做完任何一題的小資料集與大資料集，且結果正確，就可以參加下次的比賽 Round 1。很高興，我成功的通過了資格賽，不過看到那題數學題，我大概就冷了一半，所以我把志願放在希望能走到 Round 2 就好了。 Round 1 要開始的那段期間，我正好也要考駕照，所以大部分的時間都花在練習開車以及準備筆試上面，再加上早上跟晚上都有英文課程，所以那段期間沒什麼在準備，不過我知道，準備了也沒用，這種東西臨時抱佛是沒什麼用的。 Round 1 分成三個時段，參賽者可以選擇兩個時段參加，也就是說，你有兩次機會，第一次沒成功，還有第二次，每個時段挑選 840 名參賽者出來。我選擇了禮拜六的早上跟禮拜日的晚上，也就是第一場跟最後一場，我個人認為，個人認為啦，沒精算過，第一場應該是最多人參加，但是可能題目會比較簡單，而最後一場，由於前面兩場把精英都挑走了，所以第三場應該是最有機會晉級的，為什麼我會強調個人認為呢？因為我發現國外論壇也有討論參加哪場是最好的，還有人開始在上面用機率來精算，有個人看到了大家開始拿數學公式狂討論機率，就發表了「大家果然都是數學的狂熱分子，大家加油吧！」，唉，我看到卻是心涼了一半。 Round 1 A 終於來臨了，第一題是個送分題，兩個向量相乘，要怎麼排列才能算出最小的乘積，這題很簡單，題目我也看懂了，但是在做的時候，不知道哪根筋不對，人家明明說兩個向量的數量相同，我卻到後面在思考數量不同的情況，最後才突然想到不需要考慮這個，浪費了許多時間。第二題題目英文對我來說有點艱難，我在題目看不太懂的情況下，沒辦法寫出演算法，因為有一個地方我一直沒弄懂他題目的意思，而這個會影響到最後結果。當然，最後我就在這種情況下，只解完了第一題，然後第一輪失敗。在 Round 1A 結束後，我研究了別人的解法，才瞭解題目的意思，「The minimum possible number of batches are malted. 」意思是加麥芽口味的數量要最小化，而我當時以為他的意思是「加麥芽口味的當成最小值」，差很多，所以當然解不出來。再來， Round 1B 是禮拜六晚上開始，不過我沒參加，但是我還是跑上去看了題目，順便試做，然後我還挺慶幸我沒參加 Round 1B 的。因為，第一題最少分的就是一個類數學題，而且最重要的是，我題目也有一點看不太懂，我事後來看整個三輪的正確率，也是 Round 1B 的正確率最低，這一輪打擊了我不少自信。 Round 1C 在禮拜日晚上五點，終於到了，第一題計算手機按鍵上面的字母如何配置可以讓按的數量最小，這題雖然挺簡單，但是我還是花了 30 分鐘，而最快的人只花了 5 分鐘...第二題是計算 Ugly Number，老實說，我看到這題我大概猜的出來是要使用 DP，但是我實在沒什麼感覺要如何使用，最後只好用暴力解法，只是暴力解法就是又花時間又慢，而且我中途還一度腦袋打結，最後，沒在時間內完成，而我進入 Round 2 的希望也破滅了。不過我最後還是把那題用暴力法寫完，大概是因為不甘心吧，只是暴力法只能解小資料集，碰到大資料集大概就無能為力了。比賽對我來說已經結束了，老實說心中有一些沮喪，不過也感覺理應如此，因為演算法跟數學對我來說，一個是很久沒碰 (在公司裡面頂多用用簡單的演算法，而不會用 DP )，一個是更久沒碰而且也沒強過。而 Google 的比賽比較像是數學家的比賽，感覺跟 ACM 、 TopCoder 很像。如果我還想參加的話，我大概要把以前沒擁有過的數學認識非常多下，然後狂做 ACM 跟 TopCoder 的題目，把演算法的那種直覺抓住。就我的感覺，這種比賽是可以訓練以及準備的，訓練的方式就是一直做題目，然後數學也一直做，而參加這種比賽最好的時機就是你在當學生的時候。出去工作之後，東西很容易在一不小心的情況下流失。不過也許這只是我的藉口吧！這種比賽精英真的很多，這次我還特別選了優勢比 C++ 大的 Ruby 來做，不過我看到上面高手大部分是使用 C、C++、Java，所以我輸也沒什麼藉口，只能說實力就是這樣。不過這次在上面也看到一些很有趣的現象，還有人用 SQL 來解題，也發現有人每一題都用不同的語言來解，可能是想跟別人與眾不同吧！在參加比賽還能有這種閒情逸致，真的是高手。不過也可能是這種比賽大部分都是演算法正確就沒問題，所以重點不在語言上面。但是我覺得語言還是有優勢存在，因為我使用 Ruby 就不太需要擔心大數的問題，可以專心在演算法上面。比賽對我來說雖然結束了，心中也有一些失落，但是也激起了我想要把數學搞懂以及想要做題目的慾望，我要大喊！「Google Code Jam! 我明年一定要進入 Round 2!!」 XDrz -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 202.151.55.252 ※ 編輯: redray 來自: 202.151.55.252 (07/28 23:39)