上海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

上海MS Intern I

來了上海一個半星期, 工作了 6 天, 開始知道大約在做些甚麼
工作主要是寫 C#, 其實和 Java 十分相似, 目前覺得學過 Java 和 SQL 在工作上十分有用
不過其實有咩問題都係問 mentor, 很方便:D

目前週末都會到市區, 由住所到人民廣場站也要差不多 90mins, 另外上海的科技館挺有趣的
不過一出市區價錢就是香港價了
計劃過了雨季 (六月) 就試試離開上海去其它地方玩

過去一週每天晚上都在看 The Big Bang Theory
由於在搜狐上中國地區(不包括香港)是授權播放, 所以大部份時間都沒有連 vpn
不過由於實在是太好看, 所以忍不住要宣傳一下

主題曲:



Our whole universe was in a hot dense state,
Then nearly fourteen billion years ago expansion started. Wait...
The Earth began to cool,
The autotrophs began to drool,
Neanderthals developed tools,
We built a wall (we built the pyramids),
Math, science, history, unravelling the mysteries,
That all started with the big bang!

"Since the dawn of man" is really not that long,
As every galaxy was formed in less time than it takes to sing this song.
A fraction of a second and the elements were made.
The bipeds stood up straight,
The dinosaurs all met their fate,
They tried to leap but they were late
And they all died (they froze their asses off)
The oceans and pangea
See ya, wouldn't wanna be ya
Set in motion by the same big bang!

It all started with the big BANG!

It's expanding ever outward but one day
It will cause the stars to go the other way,
Collapsing ever inward, we won't be here, it wont be heard
Our best and brightest figure that it'll make an even bigger bang!

Australopithecus would really have been sick of us
Debating out while here they're catching deer (we're catching viruses)
Religion or astronomy, Encarta, Deuteronomy
It all started with the big bang!

Music and mythology, Einstein and astrology
It all started with the big bang!
It all started with the big BANG!

GCJ 2011 Round 2

Rank 6xx, 徹底地輸了
A - 一開始不斷把 velocity 和 displacement 調轉.. 大約 20 mins 完成
B - 算法很直觀, 但 debug 了很久, 用了 50 mins
C - 一開始以為最小和最大分別是 1 → n 和 n → 1, Incorrect 後寫了個暴試把 n=10 以內的都試過, 在繼續以這假設正確的前提下又找不到 bug, 就放棄了
D - BFS → DAG → DP. 但一直在 Incorrect. 找到 N 個 bug 後也是過不到. 完場

最後也有 T-shirt 但不能晉級. 後來搞了很久也過不到 D, 發現有個致命漏洞, 但又想不到怎樣改. 剛才才想到個 state 係 [previous][current], 咁樣先可以唔重覆地數 Thereat node..

POJ 3709 K-Anonymous Sequence

斜率優化DP

重要的observation
1. If k->i is better than j->i and k > j, then for all r >= i, k->r is better than j->r
2. For all j < k, there exists i such that for all r >= i, k->r is better than j->r *

然後做 DP 時, maintain 住一條 queue, 乎合以下條件

1. 在當前的 i, q[x] 比 q[x+1] 好
2. q[y] 比 q[y-1] 好的時間 大於 q[y-1] 比 q[y-2] 好的時間

每次取計算 DP 值時, 先用條件(1) pop 走 queue 頭
再用條件(2) pop 走 queue 尾, 再把 i-m+1 push 進 queue 尾


* 有時 i 會是 +inf 或 -inf, 可以 handle 做 0 或者 n+1 咁