網頁

Tuesday 29 November 2011

Sem 3 12/13: 315 Asg3 之後..

因為去 regional 的關係, 加上 sem 尾又多 deadline, 導至 deadline 前幾天才開始做
更確切地說, 是在 deadline 那一天的下午才開始改 code, 完全感受到 deadline 的壓力
幸得 peter 大大的幫助才可迅速完成

很討厭趕 deadline, 而這次更是 deadline 前 2 小時才有初步結果
不過做完後又好像對 spin-lock/semaphore 多了不少認識
我想如果有無限的時間的話也許會比較享受 315 吧..

加上 317 又因為 regional 的關係炒了一份 asg, 沒有了 course grade 3 分, 導致心情十分煩燥
不過 313 總算彌補了種種的不滿 :)
很久沒試過很認真地去做一份功課, 與做 315 的感覺完全相反
欣賞了 SAT → 3SAT, SAT → 3COL 和 Cook-Levin Theorem, 非常有趣 + 精彩
平時很多 slides 看完都不會留下深刻印象, 不過我想這些應該很難忘記吧
過了這麼多年, 總算弄清楚 P, NP, NPC
終於開始覺得這個 sem 不是一事無成..

Tuesday 15 November 2011

CodeForces Contest #94

差不多一個月沒打CF (因為和 training 的時間相撞)
感覺題目的整體難度又提高了

A - 沒看到是 8-dir 寫了 4-dir 所以錯了 2 棍..

D - 感覺有些像 shy tortoise, 建立 freq[] 後由左到右處理, 不斷進行 freq[i+1] -= freq[i]

B - 比以往的 B 難, 做法有點像 suffix array 的思想, 先比較第 1 個位, 然後比較第 2 個位.. 但是 TLE 了, 因為用了 v[] 去表示可能開始的位置, 但其實應該用一條 list[] 去保留便可以, 前者的時間複雜度最差情況會是 O(N2)

C - 花了很多時間才想到可以 x, y 分開做, 得出 cnt[i] = sum{cnt[j] * (j - 1 - i), j > i}, 但仍然是 O(N3), 把式重寫成 cnt[i] = sum{cnt[j] * (j - 1)} - sum{cnt[j]} * i 可降至 O(N2)

今次的題目難度和次序很奇怪, 對我來說, 難度應該是 A -> D -> C -> B..

Sunday 13 November 2011

ACM ICPC 2011 - Kuala Lumpur

比賽前要把背包放在一個房間, 中途看見只有 9 種氣球, 代表只有 9 題, 即是很有可能要以罰時決勝負, 對我們有點不利, 因為我們的罰時一向都不是太好

其實比賽在 9:15 便開始了, 比去年準時很多. 我負責分題目, 感覺上沒有甚麼頹題. 不久後 whh 上 A, submit 後得到 WA.. 此時己經有些燥, 在開始便已經落後人. 幸好第 2 棍便過掉

A - tui (whh, 19 + 1WA)

中途 ff 告訴我 E 的題意, 我一看便知道是一般圖匹配, 這時還覺得挺開心, 因為有武器而且我覺得不會很多隊伍能做到. 不過由於代碼很長, 決定先放在一邊, 和 whh 研究 I, 很快發現用多一支 vector 一定不會使答案變差, 所以 vector 的次序並不重要, 便猜想可以把 vector flip 至第1, 2 象限再處理, 不過不是很確定, 所以交給 ff 和 whh 處理, 我則處理 G - string 的題目, 很快便想到可以用 suffix array (其實用 kmp 便可以), 於是便啪啪啪打武器, 中途和 ff 交替讓他做 H. 寫好 G 後 submit, 返回 WA, 不久後 ff 的 H 也 WA 了, 很差的開局. 約 15 分鐘後發現一些 for loop initilize value 寫錯了, 此時 ff 的 H 也過了

H - dp (ff, 67 + 1WA)

G - suffix array (gg, 74 + 1WA + 1RTE)

此時完全沒有興奮的感覺, 因為很多大學己經拋離我們 (台大好像己經 5+ 題). 此時 ff 和 whh 又沒有其它題目可做, 於是便打 general graph matching 的武器, 其中一行代碼是 g[i][j] = g[i][j] = -1, (馬後炮) 使我有點懷疑武器的可信度.. 不過還是要打, 順利過 sample, submit 後得到 TLE, 便給 ff 做 F (shortest path?) 和給 whh 做 I, 我則把60多行的 code 印出來做人肉 diff..

之後便是差不多一小時的空白, 我的 E 完全找不到 bug, 他們的 F, I 也嚴重卡題的情況 (加起來 WA 了 5 次), 而我隨便 gen 了一個大 case 發現會在一些 do{}while() loop 中 loop 死, 但又找不到 bug, 使我十分焦燥. 大約過了一半的時侯 ff 終於過了 F, 總算有些進展...

F - shortest path (ff, 166 + 2WA)

終於 4 題, 但罰時是在同題數中最高的. 我們的分工是: whh 做 I, ff 做 C, 我則做 B - 在去年的 training 中見過類似的, 做法十分麻煩, 是 segment 內嵌 BIT, 如果之前沒做過的話我也懷疑我寫不出.. 此時腦袋己經十分疲累, 但幸好是第 2 次寫, 故寫得頗順利, 提交卻得到 RE, whh 的 I 也繼續 WA, 愈來愈令人焦急.. 幸好 ff 的 C 一棍過了, 十分慶幸不用 debug C 這種題呢

C - evaluate expression + randomize (ff, 227)

不久發現 lower_bound() 有些位 handle 錯了, 改之, 終於過了 B, 鬆一口氣

B - segment tree + BIT (gg, 234 + 1RTE + 1WA)

之後看之前看錯題目的 D, 認真想了一想後覺得不太難, 便接著做, 是比較像"OI" style 的題目, 當然由我解決掉~

D - adhoc (gg, 260)

這時侯我們仍然有希望可以全清的, 因為可能 E 只是一個小 bug, 加上 I 有很多隊做到, 在剩下的 40mins 我們應該也可以做到. 但愈試 E, 愈是開始覺得是武器出錯.. 他們的 I 好像也試了另一個 approach, 但最終也是過不了.

完場後十分灰, 也不想知道自己的 ranking, 在發現 E 竟然可以用 bipartite matching 水過後更加燥.. 隨手畫一個 case 都可以炒掉 bipartite matching, 怪不得這麼多隊伍過了..

其實以我們的實力 9 題是可能的, 雖然開局很差, 但其實還是有很多機會可以全清 (例如放棄 general graph matching 的武器嘗試水, I 也應該更早放棄 iteration 的 greedy 算法), 不過還是輸了, 感覺十分差

今次分題目不是分得很好, 不過有數題也是有 (x, y) 的坐標 input, 但其實全部都不是"真正"的 geom 來的; 不過對台大這種 "三名高手型" 來說可能沒有甚麼差別吧

今次完全浪費了 whh 的戰力, 大部份時間都在試 I 的錯誤做法 (greedy flip vector), 希望 fuzhou 的題目可以讓 whh 發揮吧

Friday 11 November 2011

Sem3 10/13: Prolog

因為 AI 的關係所以接觸到 prolog
一開始覺得很莫明奇妙, 即使想拿到 list 最尾一格也要搞一大輪, 很躁
功課也完全沒有頭緒, 無從入手
不過得到 david 大大的指導, 逐漸明白其實就是在寫 CFG 的 rules (雖然也很煩)
功課有個 online judge system, 可以大約知道自己寫的對不對, 也是不錯的
總括來說對 prolog 的印象還是正面的

由於要準備武器的關係, prolog 的功課做到 8x 分便放棄了 (無左 course grade 2 分..)
即是說 project 又要努力一點了

其實人身在吉隆坡, 後天便比賽了, 雖說有 59 team 參加, 但仍然是十分緊張
不過每次 regional 過後便要還 assignment 債..