對不起又是流水帳（感覺似乎有人在抱怨... ?），不喜歡的話就不要看嘛 >_<
Distributed Code Jam 是 Google 今年第一次舉辦，原本我都沒有特別注意這項比賽，甚至到了我進入 Round 3 以後，我才知道原來要進入 Round 3 才有資格參加，更甚者，直到剩不到一周的 Practice Round 我才知道 DCJ 的比賽內容是什麼 @@ 看來是在比我在大學時修的平行程式的東西啊... 嘛...就我當初修課的印象，程式因為平行而增加的效率也挺有限的，最基礎的平行方式就是把問題拆成可以分開計算的好幾個子問題，讓每個 Node 去各別處理這些子問題，除此之外也沒其它招了吧？
姑且還是練了一下 Practice Round 的一些題目，Practice Round 題目還真多？ pB 就只是普通的分塊，我試著寫了一下，唔... 要寫之前得先下載它提供的 tool 嘛... 我現在習慣使用的作業系統是 windows 7，並沒有裝 Python 等工具，唔唔唔好麻煩喔 >_< 我最討厭研究怎麼安裝東西了... 最後決定使用 pietty 連線到學校的工作站，並且使用 FileZilla 在 local 端以及工作站間傳送檔案... ，對不起我這種作業方式一點都不像是資工系出身的人 >_< 但是我真的不想為了不過三個小時的比賽認真花時間去研究要怎麼比才會比較有效率...
在學校的工作站上作業起來就簡單多了，程式寫完就只要輸入官網上提供的指令救可以執行了，唉不對...還得改一下權限才行 @@ 總之 pB 並沒有太花時間的救完成了。
接著看 Practice Round 的 pC，題目如下：給 $n$ 個數，請問是否存在某個數出現次數過半？
這如果在一般的演算法競賽理出現這就是個簡單題，開個 map 紀錄救行了，但是啊，在這題你光是讀 input 時間就超過了！（題目有清楚告訴你讀完所有 input 需要花多久時間）所以 input 一定得由所有 node 分別讀進來，唔...讀進來然後要在把所有訊息合併嘛？可是每個 Node 可使用的記憶體諒也有限制，也不可能把所有 input 都 send 到同一個 node 裡，於是在稍微想一下後發現，若存在一個出現次數過半的數字，那它一定在至少一個 Node 理面出現次數也過半，所以我們只要去檢驗每個 Node 出現最多次的數是否維答案即可。於是我就把這題的 code 也寫了。但後來發現，每個 Node 呼叫 send 這個 function的次數不能太多次，但我在寫 code 時沒注意到這件事，於是大測資 Judge 後就炸了...
之後在看了 Practice Round pD 的題目：數字 $1 \sim N$ 以某種順序維成一圈，給你兩個 function call 分別能得知某個數字的左邊是哪個數字，以及右邊是哪個數字，請根據這兩個 function來決定 1 和 0 的相對位置。
這題我想了些許時間都不之到要怎麼作，總覺得... 只能 random 選 和 Node 數量一樣的數字們然後交給每個 Node 去跑，但真的是這樣嘛＠＠最後我就喇塞只用一個 Node 去處理整個問題，然後 pass 了小測資，大測資也隨手傳了上去， Judge 後理所當然獲得了 TLE。事後看了一下別人的 code，似乎真的是使用 random 的方式解這題@@
寫完這三題，還剩下最後一題，但我覺得我對 api 已經熟悉的差不多了，所以就懶得在做下去了...最後一題至今都還不知道題目是什麼 :P
來到正式 Online Round 的當天，也就是證常的 GCJ Round 3 的隔天，嗚嗚嗚 GCJ 昨天比的好慘，開場看的第一題就掛蛋了，今天比得怎樣都無所謂了啦，反正這個 DCJ 本來就只是個類似於興節目/表演賽之類的東西吧？決賽入取人數只有 10 人，第一名獎金只有 GCJ 的五分之一，規模小了好多，我把 DCJ 說成這樣那為什麼我還要比呢？我就是喜歡參加比賽不行嘛 >_<
比賽開始。有四題，題分分別是 8、22、32、38，小測資的題目則分別只有1、2、2、1，比賽時間有三個小時是吧... 第一題應該是真的相當簡單吧？前十名的門檻會在哪呢？最簡單的 pB 肯定是得 AC的吧 （ 題號是從 pB 開始 @@）？ 扣除這一題後，認兩題的題分總合都高於任一題的題分，所以要先猜門檻會是幾題大測資，應該不可能門檻是滿分吧 XD 那門檻會是兩題嗎？若門檻是兩題，我想我是一定沒機會的，在時間內我大概只能處理完一題？就算門檻是兩題好了，那應該也會是前兩題吧？以一個第一次半的比賽來說，應該會確保最後一提足夠難。所以若要寫兩題，應該要挑 pC 和 pD，但若門檻是一題呢？挑 pC 應該沒望吧？pE 對我來說可能太難了也不足以考慮，所以說，若目標仍放在進決賽的話，無論如何我都得做出 pD，來不如開場就先看 pD 吧！
pD 題目如下：有 $N$ 張卡片，任兩張卡片都有固定的勝負關係，請把這 $N$ 張卡片分成非空的兩組 A和 B，使得 A 組的任一張卡片全輸給 B 組的任一張卡片，並且 B 組的卡片張數要盡量多。
由於我擁有 flow 腦，所以我第一個思考方向就飄往 min-cut 了... 但是我想不到什麼好做法，甚至連是否真的存在 min-cut 的方式解這題都不知道，想了將近 20 分鐘左右以經有些許人 AC 了 pB，所以我就決定先回來把 pB 刷一下。 pB題目是：已知一個數列每個數原本的位置和自己已排序好的位置相差不超過 $D$ （$D \leq 10^6$）請輸出此數列排序後的 hash 值。這題我讀完題就知道怎麼做了，若有 K個 Node，就把序列切成 $K$ 段，第 $i$ 個 Node 就把第 $i-1, i, i +1$三段的數一起排序之類的。總之這題我沒有花太久時間救處理完了。 submit 後比賽還剩下 2時 23分。
寫完 pB 後我決定還是先看一下 pC的題目，和 Deadlock 有關啊...我和系程最不熟了我可以直接跳過這題嗎 >_< 然後我回答自己：就跳過吧。
於是按照原本的策略繼續想 pD，先把 flow min-cut 什麼的先從腦海裡撇掉，都想了那麼久了還是沒想到什麼，那應該不是 flow 題吧＠＠ 改從簡單的 case 想：如果已知 A 組有某些數，那會發生什麼事呢？如果 A組已經有第 $x$ 張卡，那麼所有 $x$ 會贏的卡片也得在 A 組！於是每新加入一些卡片時就可以再根據新加入的卡片決定哪些卡片還得加入！直到沒有必要再加入卡片時，這些 A 組的卡片就是再包含 x 卡片下的最小集合！所以枚舉一剛開始 A 組至少有哪張卡片，就可以搜出 B 組的最大 size，這樣的話複雜度是 $O(N^3)$，要平行的話也很好平行，A組不同的出始卡片交給不同的 Node 去執行就好了。但是這個做法並無法 AC 大測資，因為此做法每個 Node還是得讀入所有 input，但大測資光讀入就 TLE 啦！但我還是決定先快速的把小測資 AC一下。
小測資 AC 後，比賽剛好勝兩個小時，我依然繼續思考 pD 的大測資要怎麼解決，過了幾十分鐘，我終於意識到這題根本就是 SCC 問題 = =，當下覺得好蠢啊.. 在一般的演算法比賽我不會花那麼久時間才注意到它只是 SCC 吧？把它變成 SCC 問題後，平行前的複雜度就降到 O(N^2) 了，但 SCC 要怎麼平行呢＠＠又卡住了 Orz
不對，光是 SCC 還不足以展現這題的所有 feature，並沒有用到競賽圖的性質，一個競賽圖的 SCC會長怎樣呢？SCC縮點後會長成一個 path！我們只要找出此SCC的最前端的強聯通元件的 size，就能解出這題了！也就是說... 我們要找出dfs 離開所有點的順序？若能找到一條通過所有點的 path 的話事情就好辦了... 但這樣的 path 有那麼好找嗎？或者是說，這樣的 path 一定存在嗎？ (此時完全忘記以前根本就有看過找出競賽圖上通過所有點的 path 的演算法....) 不不不要再深入的想下去，認真說起來，就算找到path還是得讀入很多邊，很麻煩的，有沒有什麼可以不每個Node都只讀完某些點的所有連出去的邊的方法呢？只讀完連出去的所有邊我們能獲得什麼資訊？我們能知道每個點的 out degree！out degree 在這個問題有什麼作用？B組的所有點都會連到 A組，所以B組的所有點的 degree嚴格大於 A 組所有的點的 degree！
總覺得我快要接進答案了 >_< 在繼續絞盡腦汁吧 >_< 也就是說若把所有點按照 outdegree 排序，A、B組的分法一定會恰巧把此序列切兩半？所以如果我們已知 A 組有某個degree為 $v$ 的點，那所有其它 degree 小於 $v$ 的點也一定在 A 組？如果一個點 $x$ 在 A 組，它所有憐到的點也會在 A 組，但我們就只要關注 $x$ 連到的點中 degree最大的那個點就好了！？如此一來若點 $x$ 在 A 組，$x$ 連到的點 degree 最大的是 $v_x$，那麼所有degree小於 $v_x$的也必須在 A 組！於是我只要知道每個點的 degree，和每個點所連到的點中最大的 degree，就可以解這題了！
接著是思考要怎麼平行，其實也沒有什麼好思考的啦，就每個 node 各字計算完自己所分配到的點的 out degree，在把這些資訊互相傳給所有 node，每個 node 再計算所有點連到的點中最大的 out degree，然後再把這些資訊都傳給最後一個 node，剩下的事情就交給最後一個 node 做。
我在比賽開始後 2 時 19 分左右寫完大測資，測了一下 Sample 並修了一些 bug 後 AC sample 了，於是我就把它 submit上去，同時我也順手把新的 code 傳上小測資，保險一下確認是否能 AC 小測資，但是，兩分鐘過去 judge的結果傳回來了，我竟然 WA 掉了！？WHY ！！！
我在認真重測一次我的 code，然後發現....我的 code 每次執行結果可能不一樣 = = 這世在搞什麼＠＠ nodes 間傳遞訊息出了問題？我對 google 提供的 api 還理解有誤？於是我又花了將近 20 分鐘把 code 改成我比較肯定的寫法，多測幾次每次結果都一樣後才 submit，也順手再傳一次小測資，這次兩分鐘後得到的結果是 AC，那大測資應該也沒問題了吧＠＠。
比賽只剩下 23 分鐘，我的名次好後面... 六十幾名的樣子？看來進前十是沒望了吧？勝下這點時間我還能做什麼嗎？寫 pE小測資？還是寫 pC 小測資？ pE小測資分數比較低，而且我連題目都還沒看，所以還是寫 pC 小測資得得分期望值比較高？但... pC 小測資要怎麼做呢＠＠
雖然之前已經讀了題目，但還沒認真想過，乍看之下覺得有點難耶？但仔細想過後發現就只是個 dp 而已 0.0，於是我就很拼命的寫 code，在剩下五分鐘的時候把 code 寫完，但我並沒有那麼神的一次就把Sample AC。
剩下的時間我就邊 printf 中間過程邊修正一些邊界加減一的 code，在剩下一分鐘時總算把 Sample 1 AC了。此時我另外兩個 Sample 都還沒下載下來傳到工作站上 (在強調一次，我是使用我的筆電，作業系統是 windows，使用pietty 連工作站用 vim 寫 code，檔案是用 FileZilla 互傳) ，在測完剩下兩個Sample可能就來不及 submit了 @@但更重要的是：若我真的測出 bug ，我幾乎沒有時間修正 bug後測試在上傳吧...？所以我就直接 submit 上去了 >_< submit 時間是比賽結束前 42 秒。
在比賽結束過後一分鐘左右我得到 judge結果，我竟然 AC 了！！！ 好感動喔 >_<，雖然 AC了，但我的排名仍就是 49 名這種怎麼看到沒機會 Judge 後前進到前十名的名次，呵呵呵，但我已經盡力了吧 >__< 在最後 1 分鐘內 AC題目耶 >_< 雖然只是小測資而已 >_< 這時系統發出公告說：大概兩三個小時後才會公佈 judge 結果。
我就在電腦前枯等了兩個小時(?) 看了移下大家在 Codeforces 上的討論，原來 pD 只需要每個點的 out degree 資訊就得到答案啊... 所以我求出每個點連到的所有點的最大 out degree 只是多此一舉嘛 OAQ 修練還不夠啊 >_<
這兩個小時左右我大概每幾分鐘就去 score board 按 F5一次，某次按的時候看到分數出來了！馬上瞄郭去前幾名，咦咦咦第一名竟然沒有出破台！？哇 shik 第三名耶！那我呢...於是我把頁面拉到最下面（因為 code jam若該使用者沒有出現在該頁，就會把該使用者放在最前面或最後面），咦？為什麼沒看到我？我在仔細看移下前三十名的頁面...咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦！？？？？？？？？？？？？？？？？？？？騙人的吧我第十名？咦咦咦咦咦咦？？？四十九名 judeg 後變成第十名究竟是發生了什麼事 >_< 嗚嗚我腦袋當機了 >_<這是整人計畫吧，過一個禮拜後我就會收到：對不起我們不小心把你的 code judge 錯誤了的通知吧 >_<啊哈哈哈哈 ....
四天過後 Final 的邀請信正式寄到了，看來這是真的 0.0 嗚嗚嗚獲得參加 DCJ 的 final資格一點也不會開心啦 >_< 我真正想參加的是普通的 Algorithm Round 的 final 啊 >_< 嗚嗚嗚嗚
沒有留言:
張貼留言