這場我按照順序開題，先看了第一題，題目有點長，嗯...其實向來 Code Jam 題目都很長，所以這題算短的吧 Orz，理解題意後瞬間理解這題的解法，只要 check 每個 arrow 的四個方向是否至少有一個方向也有 arrow 就行了。馬上寫完了 code， 沒有 bug Sample 一次 AC，我要不要仔細重新檢查一次 code 呢？但是 Round 2 開始 若不是拼全部小測資，penalty 並不重要，所以我就直接下載 small 的測資了。 small 的測資 correct 以後，幾乎可以相信我的 code 沒有 bug ( 除非我耍蠢陣列開太小...?) 於是我就直接下在大測資了。寫完第一題時我排第 29 名，台灣比我快上傳的只有皮皮 (peter50216) 和 shik。
接著看 pB，乍看之下就只是個特殊的線性規劃題，這時我心裡想：這題該不會去抄個 simplex 的 codebook 就能 AC了吧... ? 但我還是乖乖走正道好了，出題者應該不希望我們使用普通的線性規劃 tool (賽後證實有人是使用 simplex AC 的)。這次我學乖了馬上在紙上列出式子，線性規劃題往往可以轉成網路流問題或是計算幾何問題，但這題的式子看起來比較向計算幾何，直覺的想法是：先使用 binary search，然後再判斷某些係數在時數區間的二維向量的線性組合是否可以組成特定向量。似乎就只是個經點問題，但我對解法沒有印象。我先想想兩個向量的 case，感覺上挺簡單的啊，若有向量和目標向量方向一樣，就直接使用該向量組成目標，否則可以決定出兩個向量使用的係數比，也不難算出至少需要多少係數。甚至連 binary search 都不用。
之後我在想想 $n > 2$ 的 case，就是再這裡我想歪了 Orz，我想成至多只需要使用兩個向量就行了...(再次強調，這個結論是錯的)。當比賽當時我並不覺得我有想歪，於是就直接 coding，並 WA 在最後一筆 Sample，當時我這樣想：可能只是 $n > 2$ 的某些 case 我 code 有 bug，於是決定還是先傳傳看小測資。但小測資竟然 WA 掉了 @@
之後我左看右看，都不覺得我 code 哪裡有錯，就算我 $n > 2$ 的版本有錯， $n = 2$ 的應該沒道理錯吧！！！過程中我也把 code 改成純粹的 $n = 2$ 的版本，自己測了不少測資，也還是不知道哪裡出了問題，這時心裡好焦躁。
debug了一個小時左右，眼看比賽一個小時，我看了一下 score board，我已經落到 1500 名外了... 看起來就算我 現在去 AC 了 pC 和 pD 的小測資，也不可能進 Round 3，如果放棄 pB的話，就要在剩下的一個小時完整解決 pC 或 pD 其中一題，但看了一下目前上傳人數，似乎後面兩題都不簡單耶...，要繼續在 pB 掙扎嗎？還是要換題呢？
我現在可是處 pB 在連小測資都過不了的狀態，但以經有 $1/3$ 以上的人都 AC 小測資了。以前幾乎不會在個人賽那麼多人 AC的題目上，毫無一點進展那麼久...，但是任何時候都沒有最蠢，只有更蠢吧？所以這時候大概放棄會比較好，於是我開始閱讀 pC。
讀完題就覺得 flow 感很重，只有兩種語言，許多 flow 問題都是建立在只有兩種區隔上。可是我沒辦法立刻感受到它的模型建出來長怎樣。想了一分鐘以上後還是感受不出來...，嗚 QQ 我可是 ioicamp曾經的 flow講師啊 OAQ 怎麼可以敗在 flow 題上 OAQ，自從我當 flow 講師以後幾乎所有 flow 題都可以分殺 (秒殺有點太超過，所以使用分殺這個詞) 啊！好吧，重新想想我當時是怎麼教 flow 的，如果我自己教的東西都無法幫助我解題，那我算什麼講師啊！！！！
從頭來！首先，通常題目中都會有看起來就像是可以當做網路中的點的物件，這題可以當做點的有：句子、單字。其次，列出所有限制條件，再跟據限制條件建出網路的弧，有時會為了使限制能表現出來而增加點(ex:點容量) (粗體字是當初我在上課投影片上出現的文字)，這題的限制有：同一個句子是同一個語言、前兩個句子已知是兩種不同語言、若一個字被當成兩種語言會有 1 的 cost。由於 cost是在點上，所以可以相信我們建出來的 flow 模型，有必要把每個 word 拆成兩個點：入點和出點。
接著想想 min-cut 問題的模型代表意義。「我挑完後，剩下的給你」。聽起來好蠢 = =，可是這就是我當初講義上所列的子標題，真實意義為：「min-cut 所分成的兩個點集 ，包含源點的點集是所有原點所能流到的點，而那些點所代表的東西會被歸為一類，剩下的東西會被歸為另一類」。所以我必須建出一個模型，使得除了被 cut 掉的點外，是英文的單字都會被source 連到。由於同一個 sentence 裡都是同一國語言，於是我就把有出現在相同 sentece 的 word pairs 也在當中建一條 cost 無限大的邊。
於是我最後建出的模型由以下兩個 model 組成：
比較特別的地方是我把建了 source -> sentence -> sink 這樣的關係，如此建邊可以確保這兩個弧恰有一個在cut裡。除此之外，第一個 sentence 我沒有把它連到 sink，同時我也沒有把 source 連到第二個句子。這樣建出來的模型，min cut 值減去 INF*(句子數-2)就是答案了。可以檢驗看看，求出來的 min cut 的確能把屬於英文的單字和句子都和 source 相連。
這是憑我的直覺建出來的圖，實際上似乎可以不存在代表 sentence的點，取而代之的是直接把 source 連到第一個句子出現的 words，以及把第二個句子出現的 words 都連到 sink。
submit 完這題後排名就衝進了前 500 名，我的做法正確的話那麼 Round 3 就穩住了，可是還剩下一些時間，還是繼續回來幫 pB debug 吧 Orz。再重新想想只有兩個向量的 case ... 啊！！！若兩個向量都和目標向量相同，可以兩個向量都使用哇，這麼說來... 三個向量以上的 case 我完全想錯了啦！！！再仔細想一下，發現我原本的 code 可以很容易改成讓小測資 AC，所以在最後的一些時間順手改了一下並 submit。呼 ... AC 了。看來當同一個 bug 卡太久的時候還是讓頭腦先去做點別的事後再來 debug 才會比較有效果 @@，比賽比了那麼多年還是學不了這個教訓＠＠
比賽 ending 了，我傳的兩題大測資都有確實 AC，有真的進了 Round 3，真是好險...，差點以為我的人生要倒退走了＠＠
沒有留言:
張貼留言