網頁

Tuesday 25 October 2011

URAL 1464 - Light

很感動, 搞了幾天終於過了
開始有信心做其它 sweep line 題

詳細算法在 kn 的 blog 有, 都是 sort by angle + sweep line
不同的是我用的是 heap
開頭以為可以用 stl priority_queue, 但在處理 delete 時, 不能像以前 expire + reach top 才 pop, 因為只是存在在 heap 中就會打亂次序
所以只好人手寫一個 heap

在發現無數的 bug (例如離散角度時沒有處理 -PI 和 PI 同時存在等等) 後, 加上無限的 WA, 終於過掉了!
之後再把無用的 code 刪掉, 竟然可以 runtime 第一
雖然其實沒有甚麼大不了, 但還是興奮了一陣子

Tuesday 18 October 2011

SSU School Team Regional Team Contest 2011

好像是 SSU (Saratov State University) 的人出的題目, 類似 SSU 的邀請賽?
Anyway, 由於在 CF 也有同步賽, 在香港時間的下午, 不過星期二等價於 day off (317 + 323 + 323), 於是就在家獨自打
5 小時 10 題, ACM ICPC rules
題目

由於午睡的關係遲了半小時開始..
A-C 都是頹題, 不過 C 看錯了所以錯了一棍; D 寫得不是太好+沒看清題目又是一錯棍; 看到 tourist 跳過了 E 做 F, 便先做 F, 很簡單的計 tree diameter; 看了看 E, game 題, 不懂又不想花時間找 pattern; H 好像不太難, 做法是枚舉所有可行的簡寫, 最多 264 個, 中途可以 prune 掉很多 - 再做二分圖匹配; G 是閱讀理解模擬題, 沒有想像中複雜, 不過沒看到要順序 output 錯了一棍.. 之後寫 E 的暴力看 pattern, 發現原來是很簡單的 pattern, 怪不得很多人很快便過了; J 挺有趣的, 想了想其實是找距離, 所以可以先把所有點 flip 至第一象限再做最近點對, 因為 1-base 又錯了一棍.. 剩下 I, 有點煩膠的 greedy, 一開頭打算寫 dp, 但發現又不用, 只要逐個位試便可以, 但是也是寫得很長, WA 後寫了暴力對拍 debug, 最終在 278 的時侯過了, rank 37

雖然真正比較難的只有 2-3 題, 但單挑還是很有趣的 :)

Thursday 13 October 2011

Team Training 10/10/2011, 12/10/2011

ChengDu 2007

D: simulation by whh
J: 簡單題 by whh
B: AP by gg
- 其實很早就寫完, 不過沒發現伏, 花了點時間把所有情況想清楚
H: 1999題 by faifai
A: partial sum by whh
C: dp on tree by gg
- 寫得很差, 想漏一些東西導至 code 得很複雜 -> debug 困難, 之後重做短了 40 多行
F: state dp by whh
- 好像是插頭 dp, 錯了很多次, 懷疑有比較簡單的做法
E: by gg + faifai
- 和 faifai 討論了一下, 發現原來看穿了就很簡單, 我負責 RMQ 的部份, TLE, 發現可以很簡單地用類似 histogram 的方法降至線性, WA 了幾次後發現是 LL 的問題, 最後 293 + 4 過了

I: 見此
G: 原來用 A* 就可以, check 的時侯只考慮有機會 intersect 的 rectangle


Kuala Lumpur 2010

很難得的接近full team打.. (3人出席時間加起來應該有13小時, 好像是開學以來最多的一次..)
就扮真比賽記錄吧

開始 whh 負責打template, 我分題目, 發現把很多題目都分了給ff. 不久 ff 發現簡單的 B, 瞬切. 我看的 I 很像 Jakarta 的 B, 很快便推到式, 在 ff 做完後便接著做, 過不到 sample, 先給 whh 做 H (因為忘了 output test case number 錯了一棍), 很快找到 bug, 改之, WA 後發現把 test case 數目看成 input size 了.. 改好便過了第 3 題, 暫居榜首 (好像是). 此時 ff 寫 D, 我手上有 F (grid, 可能是 BFS), G + J (geom), 同時 whh 問我 C 是不是很熟面口, 一看發現竟是我 211 project 的題目! 不過由於有太多題目在手加上 whh 好像沒有其它題目做, 便把算法告訴他由他來想細節, 等自己可以專心做我負責的題目. 不久後 D 輕鬆 WA, 由於 debug 不能, ff 便改做好像較簡單的 A, 不過寫到一半又發現 trivial 的 greedy 好像有反例, 和他討論了一下又找不到方法解決. G 是 standard 的二分, 於是便搶先寫, 途中他們發現很多隊過 A, 便覺得應該可以頹做, 結果是可以的. 我的 G 也緊接著 A 過了. 之後好像是 whh 和 ff 交替寫 C 和 D, 突然發現 live archive 的題目和 official site 的 D 是不一樣的! (好似係minor difference), 改後仍是 WA, 而 C 就 AC 了, 便讓 whh 幫 ff 的 D debug, 我做 F (standard steiner tree, 比較麻煩的是 vertex 有 weight). 不久後成功過 D, 我的 F 則 WA, 不過可以用 machine 有效率地 debug, 很快便發現 vertex weight handle 錯了, 改+過之. 此時剩下一半時間和 2 題, 如果不是預先知道題目難度的話應該會覺得很大機會全清的. 分工是我做 J, whh 做 E, ff 則 2 邊協助, 和 ff 討論了一下, 很快便找到不是過 2 點的 case, 便想到一個很複雜的line rotate 算法. 不過 whh 好像對 E 沒有甚麼想法, 便問了一下他的意見, 他覺得過 1 點的話 line 是 fix 的, 我覺得合理, 也會易寫很多很多, 於是便開始寫. 不過也是寫得很差, rotation 的部份不長但花了很多時間, 過 sample 後好像己經是 260 了 (寫+debug 了一個時間..), WA 後發現 1 點的 case handle 錯了, 改後竟然得到 TLE, 便努力 opt rotation 的部份, 繼續 TLE, 最終發現 rotation 的 index 有點問題, 改之, 此時剩下數分鐘, 雖然只是 training 沒有緊張的感覺, 但在 297 時 AC 也是很興奮的

Sunday 9 October 2011

POJ 1739 Tony's Tour

非常慘烈的AC..

題目是最最最基本的插頭 dp, 其實在隊中不是我負責的, 不過做做也無妨
由於只有 39 種狀態, 所以便不用 hash, 直接做
但是因為不用 hash, 所以不能用 4 進制做 bitwise, 每次我都要把狀態 decode/encode
寫好後便是無限 WA..

WA 到不行的時侯, 便上網找別人的 code, 再怒 gen test case fc 自己的 output
不過也找不到 bug, 很灰, 一度懷疑是 test data 有 > 8 的情況, 但放了飛彈又沒有
最後發現 decode 一個 invalid 的狀態時, 會 access stack[-ive], 但不知為甚麼這情況只在特定 test data 出現

現在是 5/8 個男人了..!

Friday 7 October 2011

Team Training 6/10/2011, 8/10/2011

Tehran 2010

A: 簡單 by whh
B: 麻煩題 by faifai
H: Graph by whh
- 我用了 SCC 做, 其實只搵 source SCC 可以寫得簡單點
G: by whh
E: 枚舉 by gg
- 發現 hint 是錯的..
C: game 題? by faifai
D: 煩膠 by gg
I: 頹sim by gg
- 水過的, gen 個全是 robot 的 map 輕鬆 TLE..

K: 可以用 DnC on tree + BIT 做, 不過很麻煩, 懷疑可以用動態樹


NWERC 2010

A: greedy by faifai
H: sim by whh
C: by faifai
E: count degree by gg
B: dp by faifai
F: lower bound flow by gg
- 本身無諗住咁早打.. 統粹唔想空置 machine
J: by gg
- 很簡單, 但大家也好像很遲才發現這題
G: by gg
- 用類似 stack 去做

Wednesday 5 October 2011

Sem 3 3/13: 315 Asg 1 之後..

終於做完315 asg1 (還有 4 份), 鬆一口氣
其實份 asg 很簡單, 不過由裝 gentoo, compile kernel 等等都是第一次, 所以花了很多時間在無謂的錯誤上
一開始以為功課是寫 kernel, 不過可能是 S 班的關係, 變成了這份 (其實我覺得寫 kernel 好像比較有趣)

asg1 要使 user 可以令一個 process 變成 invisible (ps, top, /proc 不顯示, 不能 kill)
開頭完全無從入手, 感覺明明 lecture 都聽得明但是一到 asg 就顯得很不足夠
即使知道是改 /fs/proc/base.c, 但 base.c 有 3000+ 行 code, 每個 function 也很'可疑' (每次試也要重新 compile+reboot, 很費時間)
不過做完的時侯其實也很有成功感的, 也發現這個 course 的好玩之處在於做 assignment, 做完後會對 OS 多很多認識

還有雖然不用part pro, 但 315 終於令我覺得朋友很重要呢