[技術] Code Jam資格賽心得分享

看板Soft_Job作者derekhsu (華麗的天下無雙)時間16年前 (2008/07/18 13:53)推噓16(16推 0噓 23→)

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

上個月報名的Google Code Jam，原本我以為第一輪的比賽是7月26才會進行的，想不到這兩天上網才發現在台灣時間7月17日早上七點到7月18日早上七點有舉行一次資格考，必須要在這24小時之內，完成三道題目，並且在時間內上傳到Google，當然，還包括原始碼，每個題目都包括小輸入和大輸入兩個部份，完成小輸入可以獲得5 分，完成大輸入可以獲得20分，要通過資格考的成績是25分。小輸入可以上傳不限次數（不過失敗的紀錄會被記錄下來），在下載完小輸入之後，必須在四分鐘內執行程式，獲得輸出之後把輸出的檔案和原始碼上傳，如果超過時間就算失敗。每次的失敗，都會讓小輸入重新產生，所以每次所下載的小輸入都會不一樣，上傳的結果會馬上知道。而大輸入就不一樣了，大輸入的輸入值不但比小輸入既多且長。也許還會藏一些小輸入沒有的陷阱也說不一定，而且大輸入上傳的結果不會馬上知道，而要等到比賽結束之後， Google才會去檢查大輸入的上傳是否正確，當然，他也會驗證你所上傳的程式碼是不是真的能夠產生出這樣的輸出值。裡面的題目其實都不太簡單，原來連資格考的題目都這麼靠北了，那第一輪的題目可不是更難嗎？而且我在完全沒有心理準備的狀況下，我本來想要用.net來作題目的，結果因為種種原因，我沒有辦法及時在我的電腦上安裝Visual Studio（最近才換成Ubuntu），只好改換 Eclipse來寫Java，但是想一想最後我還是用PHP來完成的，PHP這種鬆散結構的語法在處理這種需要短時間完成的問題時非常有威力，非常快。如果我要是用.net或是Java，恐怕花在定義類別和資料結構上所花的時間，就會耗掉我半條命吧。最後我只解出來兩題，但是大輸入的結果目前都是對的，理論上有50分，前面兩題都算是我比較擅長的演算法題，一題考「可預知未來的最短路徑」（我是指它的精神，實際的出題內容不是這樣子），另外一題則是兩點的排程問題，這兩題都我比較擅長的演算法，但是第三題是幾何題，計算蒼蠅拍打中蒼蠅的機率，這對我來說實在是太難了，我現在的幾核能力退化到我連圓面積的計算公式都要靠Google來幫我找。看到榜上前幾名的一堆強者，半小時內就搞定了第一題和第二題，第三題雖然比較久，但是還是在一個多小時之內疚可以完成，我實在太佩服了，我第一題花了3個小時，第二題則花了4個小時，合計做完題目的時候已經花了10個小時了（我九點多才開始解）由於第三題完全沒有頭緒，所以只好放棄了。原來寫程式也有在考幾何學的，偏篇幾何就不是我擅長的項目。不過看到這些高手，我覺得我的第一輪還是當作磨練好了。談一下第一題的題目吧，我想大部分的人都應該解得出來第一題，我是用比較蠢的暴力破解法，把每個搜尋引擎都丟進Query裡面試，哪一個能連續處理的Query最多，就用那個當作是選擇的Search Engine，然後看能處理到第幾個才會遇到不能處理的Query，就換其他的搜尋引擎重複這樣的過程一次，並把$n++，等全部的Query處理完，就知道總共要切換幾次。是計算兩個點兼第二題稍微難一點，是計算兩個車站間班次表，兩個站點必須在一天內最少準備多少火車，才能滿足所有的班次發車都不延誤，火車到了以後必須等待一個轉換時間（0-60分鐘，大樣本，0-5分鐘，小樣本）才能再發車，0表示馬上就可以發車，一台車可以在兩地之間來回多次，這一點就使得在考慮的時候必須同時考慮A地跟B地的狀況，我原本只是單純的比較depA（從A出發的時間）跟ariA（到達A地的時間，即B站班表中的到達時間)，結果上傳了三次都是錯的，才知道這一點會有很大的影響，於是只好改用模擬的方式，計算每個時間點各站的狀況。我建立了一組資料結構： $schedule = array( $time => array( 0 => array( "TYPE" => ["DEP"|"ARI"], "PLACE" => ["A"|"B"]) ) ) 來紀錄每個時間點發生的事情，比如： $schedule = array( '07:10' => array( 0 => array( "TYPE" => "ARI", "PLACE" => "A"), 1 => array( "TYPE" => "DEP", "PLACE" => "A"), 2 => array( "TYPE" => "DEP", "PLACE" => "B") ) ) 就是說在07:10的時候有一台火車到達A地，有一台火車從B地出發，有一台火車從A地出發。而ARI的順序一定在DEP之前，因為當T=0的時候，火車可以到達後馬上出發，如果不先紀錄到達，就會發生錯誤。接下來再用兩個資料結構： $trainAvail = array("A"=> string, "B"=> string)在A站或是B站可以發車的火車時間，這是火車到達時間+T，當有火車到達的時候就寫進這個資料結構，當有火車離開的時候先檢查這個資料結構理面試不是有小於發車時間的火車，如果有，把這個資料元素從資料結構移除。如果沒有，則修改另外一個資料結構： $trainCount = array("A"=> int, "B"=> int)，把從A地或B地出發的火車 +1，表示站內沒有可以發車的火車，必須多準備一台火車。把我有的時間點跑玩之後，$trainCount就是答案。第三題的話就真的難倒我了，我知道方向，也知道是計算洞（蒼蠅可以閃過拍子的面積/拍子的面積），但怎麼去計算邊緣的那些不完整的方形.... 完全不知道，就請高手解答囉。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.5.99

推

TonyQ

07/18 14:28, , 1^F

07/18 14:28, 1^F

推

TonyQ

07/18 14:32, , 2^F

07/18 14:32, 2^F

→

TonyQ

07/18 14:32, , 3^F

07/18 14:32, 3^F