上海MS Intern V

無錫一日遊
第一次 5 個香港 intern 一起去玩, 選了個不遠而大家也沒去過的地方



早上七點出發, 九點抵達上海火車站, 買票比想像中複雜



高鐵, 買票的時侯要回鄉証, 幸好大家都帶了
買了企位 (其實是不是會搞到超載的..)



到達無錫, 經過多方洽談, 決定跟一些旅行社交易 (它提供交通和景點門票, 比正價平一點, 應該是從景點那裏抽佣)
一開始 whh, helic, tong 和我都很不行, 不過最後還是付了錢



三國城 - 為拍電影/電視劇而建的 (好似係)


坐船遊太湖, 架船下層冷氣的散熱口對正上層甲板, 咩設計來的 (o:


「水軍訓練營」- 途中 helic 跌左副眼鏡落去, 花左一番功夫先搵返


唔知做緊咩既演出



之後過隔離 - 水滸城, 其實都係差唔多



買了弓箭玩具



大家係度瘋狂買野(又幾抵), 最搞笑係入面檔檔賣既一樣 (o:


$5 騎馬影相



$10 玩射箭


根據計劃, 本來是去甚麼古鎮的, 不過被黑的司機說服了我們去甚麼動物園




動物園夜場 - 其實我地入去玩機動遊戲的
右圖的機動遊戲堅正
表演 - 無劇情可言, 不過有些 tricks 係第一次見


走既時侯大雨到hihi, 最後差唔多 11pm 先返到火車站, 發現無哂車
討論好唔好 book 間房過一晚, 最後決定搭 3am 的車回上海
找到間 24hr 麥當奴 hea, 玩超用腦 game & Italian





呢架火車由成都開來, 已經行左 30hr, 所以上到車成地垃圾



這算是中國「真正」的火車吧, 老老實實, 企個半鐘已經差示多是我的接受極限



回到上海, 搵左間中式快餐店食早餐




統計支出

項目	支出(RMB)
教師之家->上海火車站	7
早餐	10
高鐵	60
無錫火車站->三國城	2
三國城+水滸城+太湖遊船	120
7-up	4
午餐	19
木弓玩具	10
果粒橙	5
射箭	10
水滸城->動物園	15
動物園夜場	65
雨衣(share)	1
晚餐	36
動物園->無錫火車站	1.2
支裝紅茶	5
麥當奴(share)	4.8
K車 (無錫->上海)	20
早餐	10
上海火車站->教師之家	7

一共用了 412 RMB

上海MS Intern IV

先簡單說說工作: 在 team 上主要是做一些輔助的 tools, 差不多做好一個 project 了, 聽說做完後要 present 呢

近來都是星期六玩一整天, 然後星期日則睡到下午, 在黃昏踩單車去不同的餐館吃飯 (其實是因為來上海後每星期六晚上都有比賽, 所以都很遲睡)
上星期六跟團去了蘇州, 不過印象不是很深刻, 始終比較喜歡自己 plan 行程而不是跟團

然後就講下晚上娛樂啦

遊戲
其實Braid不是來上海才玩的, 不過也一拼記下吧
Braid: 和時間有關的遊戲, 破關的難度不亞於做題目! 故事很深奧, search 了幾個網站才明白, 絕對稱得上經典
World of Goo: 物理遊戲, 有點像起橋, 但很多變化, 也當是解謎遊戲, 另外 soundtrack 很好聽

書
由於不遠的交大有間書店, 又有85折, 於是養成定期去買書的習慣, 目前在看東野圭吾的書
時生: 和 Back to the future 差不多, 沒甚麼驚喜
殺人之門: 不錯
單恋: 很喜歡故事的發展速度

不過其實成篇 blog 既重點, 就係我開始睇 Star Trek !
其實是在看 The Big Bang Theory 時, 入面的角式都很迷 Star Trek, 於是便看看, 發現真的很好看
上 wiki 一看, 發現有 11 集電影, 七月底前看得完嗎?

上海MS Intern III

單車大冒險!

由教師之家出發, 沿著龍吳路, 踩到徐匯區吃午飯
然後轉向東面, 在陸家浜一帶乘渡輪到對岸

過了岸便是在拆卸的世博, 發現演藝中心館變成了一個商場的地方
途中經過一間一年前吃過的餐廳, 感覺很特別, 一年前這裏還是十分熱鬧的地方, 現在變得很冷清

轉向東北, 踩到世紀公園, 發現好像要錢 (上海很多公園都要錢的) 和好像快關門, 便到科學館附近吃晚飯
最後沿著和原路差不多回教師之家

粗略估計今天踩了>7 小時, 主要問題唔係攰, 而係個單車坐位會令到屎忽好痛
同埋這裏的天文台預測今天陰天, 但結果是, 「說好的雲呢?」

晚上 SRM, 又做不到 500 了 (連續幾次做不到了..), 不過 250 危機四伏, 順利地 cha 掉 3 個
第一次覺得 challenging phase 太短 :p

上海MS Intern II

開始intern以來主要都是改改別人的code, 這幾天終於要寫新的東西 (雖然都是加在以有的東西)
其實時間主要都不是花在打code上, 而是無限google一些自己不懂的東西, 有時會想如果那些 function, system 一早識的話, 我基本上可以 1 日做完佢 assign 我 1 星期做的 task, 不過佢應該是預左時間我用來學習的吧

另外, 終於買了單車 (其實也是二手的, 不過睇落幾新), 又可以遲點起床:p
順帶一提, hea 踩單車返工和 whh 跑的時間差不多

看完 TBBT 後, 又看了兩本書+電視劇 (因為夜晚其實無咩做..)
內含劇透

流星之絆

其實一直也沒把它當成推理小說, 也沒有猜兇手是誰之類, 我比較喜歡一邊看一邊享受劇情
看完小說後發現還有電視劇, 便一拼睇埋, 不過我對電視劇的評價偏低, 原因:

1. 感動位/搞笑位太多, 主角成日有講有笑, 完全沒有那種復仇的感覺, 不夠黑暗
2. 主角搵明星做, 完全唔 match 書入面既人
3. 最後栢原竟然沒有自殺! 最後仲要整個 happy ending, 迎合市場

總結來說, 除非是很得閒想 fing 時間, 否則都是不要看電視劇


隔離島

由於 faifai 又要睇又要驚, 令我很有興趣
結局不算 surprising, 至少佢唔係第一個故事係咁, 不過並不影響整個故事的可觀性

又發現原來有電影, 準備看, 在 IMDB 上有 8.0 的, 看來拍得不錯

CodeForces Contest #75

近來幾次 Codeforces 都出現 D 和 E 一樣分數的情況, 其實是對我有利的, 因為有機會懂得做的題目多了 -> 做到 D 或 E 的機會大了

E - 有 N 個 igloo, 在時間 = t 時, 第 i 個 igloo 的高度為 a_i + b_i * t . Queiries: 在時間 = t 時, output 第 x 個至第 y 個中最高的那個

看完題目, 最先想到的是:
1. 90% 可以用 segment tree
2. 可以把 queiries 按 t_i sort 好
3. 高度那 part 想起 Best Plan[1]

由於想要知道 [x..y] 中最高的那個, 因此 segment tree 上的每個 node 都儲著一條 queue, queue front 就是當前最高的那個 igloo
現在目標是對 [x..y] 中, 找出 sequence S, 使得一開始 S₁ 最高, 過一段時間後變成 S₂, 如此類推

一開始我按 b[i] 由小至大排, 再 remove 那些 a_i 比後面小的, 之後每次 query 只要睇下使唔使 pop queue front 便成, 不過過不到 pretest
之後發現假如有 3 個 igloo A, B, C, 會有機會出現以下情況:

(A > B > C) -> (C > A > B) -> (C > B > A)

即是, 在 B 超前 A 之前, C 已經超前 B
解法方法: 像做斜率優化 dp [2] 那樣, 要計算超前時間, 即是對於 A, B, C , 在 push C 入去時, 除了 check 是否好過 B, 也要 check 超前時間, 即 Cross(C, B) > Cross(B, A)




C - 一個 Graph, 每次 add 一條 edge, 問有多少種方法選取 edge set S, 使得 S 能拆分為數個 edge disjoint cycles

很多人做到 (雖然聽說和某 TC 題目相近 [3]), 不過又想不到怎樣做, 看完題解覺得很有趣

做法: 每次 add edge 時, check 條 edge 的兩端是否已經 connect (用 disjoint set), 如果是, 則把答案 x 2

不過最精彩的還是證明, 大約是這樣的:


把每一條 edge 寫成一支 1 x N 的 vector, 連接的點 = 1, 否則 = 0
例如 N = 5, 則把 edge (2, 5) 寫成 <0, 1, 0, 0, 1>

[Propeties] 如果有一 set vector 把它們 XOR 起來的結果是 0, 則乎合選取方法, 反之亦然
[Proof] 把它們 XOR 起來為 0 <==> 每個 node 的 degree 為偶數 <==> 存在 euler cycles

問題變為, 現在我們有一 set vector S, 有多少種選取 S 的 subset 方法使得 XOR 起來 = 0 ?
答案是 2^{|S| - rank(S)}

解釋: 先任意找出 S 的 basis, 對於不是在 basis 中的 vector, 可以任意選取 (2^{|S| - rank(S)} 種方法), 然後有 exactly 1 種方法在 basis 中選一些 edge 去補上乎合條件

所以, 每次 add 一條 edge, 只需看它的 vector 是不是和 S linear independent, 可以證明, 如果這 vector 和 S 是 linear dependent <==> 這條 edge 的兩端已經 connect



References:
[1] HKOI 2007 Junior
[2] http://www.topcoder.com/stat?c=problem_statement&pm=6779&rd=10002&rm=249950&cr=13358640
[3] POJ 3709

Official solution: http://www.codeforces.com/blog/entry/2179