網頁

Monday 22 December 2014

吐槽

雖然說過「歐洲的城堡都一樣」,不過美國基本上沒有真正的城堡這點還是非常遺憾



還有很莫明奇妙的是,在 Espresso 旁的雪櫃有 85% 是 reduced fat milk,但同時又要落 syrup (罪大惡極),耐人尋味

不過,至少還沒看到 canned coffee 這種不能稱為咖啡的物體.. 其實喝過「真正」的咖啡以後就完全鄙視像雀X的罐裝咖啡

但多得有 Amazon ,我早已在 Expresso 的路上奔馳


Sunday 7 December 2014

Quora haqathon 2014

Quora haqathon today, from 11am to 7pm - Pacific standard time! Features 9 problems mixed with tradition algorithm tasks, machine learning and system programming tasks.  Link to site.

Ontology
Linearize the tree - each query reduces to "in question q[x...y], how many of them start with prefix p?". Offline query + Partial Sum Trie. Linear time.

Wombats
Maximum closure.

Labeler
Use training set to calculate \(\text{Pr}[q_i \in t_k | w_j \in q_i ] \) for all question \(q_i\), topic \(t_k\) and word \(w_j\). Improve using bi-gram.

Duplicate
Use \( \text{Pr}[w \in \text{question_text}_i \text{ and } w \notin \text{question_text}_j ]\) as classifying criteria - 60% accuracy. Consider also \( \frac{\text{view_count}_i }{ \text{view_count}_j } \) improved it to 70%.


Wednesday 19 November 2014

PhD 4: Peaky Blinders

無意中在 Netflix 發現的英劇, 看了第一集還不錯
尤其是看完 這種水準的之後, 還是先換一下類型
這劇主要看點是歷史感
另外看完美劇後緊接看英劇就很明顯聽出不同的 accent
image from wikipedia

Wednesday 12 November 2014

PhD 3: Old news is so exciting

近來看到一個「早該知道」但昨天才知道的 fact: if \(X \subset L^d_2\) then \(X\) isometric embeds to \(L_1\)
如果只說 idea 很簡單 -- pick a random vector \(r\) in unit sphere \(S_{d-1}\), consider map \(f: x \mapsto \langle r, x\rangle\), then

\( \mathbb{E}[|f(x) - f(y)|] = \mathbb{E}[|\langle r,x \rangle - \langle r,y\rangle  |]
= \mathbb{E}[ |\langle r, x-y \rangle|] \propto ||x-y||_2
 \)

所以只要取"足夠"(無限)多的 sample 然後做 scaling, 就可以準確地 preserve 原本的 distance
加上因為 \(L_1^* \hookrightarrow L_1^{\binom{n}{2}}\), 所以是存在 finite dimension 的 \(L_1\) embedding

Monday 10 November 2014

PhD 2: Netflix

Netflix, 線上睇片網站, 月費 $9, unlimited streaming (嚴格來說 bounded by 2 screens * 30 days), 睇美劇一流, 而且似乎唔少歐洲電影

花了三個星期把  Breaking Bad 追完, 才剛發現原來在 imdb top TV 居首
(一開始不完全是因為出名才看, 而是看完簡介覺得劇情半重口味很合胃口)

1. 發現原來只用英文字幕也足夠, Netflix 練英文一流
2. 很成功地避免了所有劇透
image from wikipedia
睇完又將 "好劇" 的 threshold 提升, HBO 快點出 internet streaming 吧...

Thursday 6 November 2014

PhD 1: 食物篇

超市一般不叫 supermarket, 叫 grocery store
U village 有 QFC 和 Safeway
QFC 有相對大的 cheese area, 是真正的 cheese 不是 pre-packaged 那種
啤酒的選擇也很多, 值得一提的是有 Pilsner Urquell
不得不吐槽的是, 如同眾多 stereotyping, 很多東西都重甜
雖然 sample size 很小, 不過我發現 US 產的紅酒似乎都偏甜
其實不加糖的 sparkling water ($3-4/12cans) 完全可以取代汽水

不得不提 UW 的食街 University ave
其中有一間 U:Don 不得不推, self service 式 (免 10% service charge)
基本上整間店就只售各種烏冬, 相對上正宗
兩圖分別約 $7 (after tax)

Friday 12 September 2014

PhD 0: HKG → SEA, stopover in Seoul

Seoul is the near-optimal stopover from Hong Kong → Seattle


Zoom in:

Of course, actual flight path deviates considering flight route, winds etc.
Stopover in Seoul is great too, with airport (ICN) awarded in SKYTRAX, and free transit tour


Seoul 12 hours stopover

ICN Airport → (AREX) → Seoul station → 南大門市場 → 明洞 → 仁寺洞 → 東大門  →
國立民俗博物館 → 景福宮 → 市政廳 →  Seoul station → (AREX) → ICN Airport



明洞, 不過其實無咩行

Monday 4 August 2014

雲南 Grad Trip

21/7/2014 - 3/8/2014
香港 → 廣州 → 昆明 → 大理 → 麗江 → 香格里拉 → 昆明 → 廣州 → 香港

Wednesday 16 July 2014

IOI 2014 Game

主要是為了跪拜 solution 3 所以打一下..

Problem: imagine there is an undirected graph G. Implement an adversary oracle, that opponent queries hasEdge(x, y) and you returns true/false. Goal: opponent cannot figure out whether G is connected using less than C(|V|, 2) queries. |V| ≤ 2500

Solution 1: idea: return false unless G will be disconnected eventually (even if all unqueried edge presents). Naive implementation O(n4). One can view as starting from a complete graph, and support operations:
- addEdge(x, y)
- removeEdge(x, y)
- queryConnect(x, y)
which is the Dynnamic Connectivity Problem. From here, it can be done in O(polylog n) which may not fast enough and probably coding-infeasible for IOI.

Solution 2: idea: relax the constraints for returning true. Assume there are several components in the graph currently. For every two components we will have an edge connecting them directly, but only reveal it when opponent queried all pairs of vertices from that two components. Implementation: maintain a counter for every pair of components. Merging components takes O(n) to update the counters, but we only do merge operation n-1 times so in total O(n2).

Solution 3: for query hasEdge(x, y), wlog x < y, 0-based, increase cnt[y] by 1. Return yes if and only if cnt[y] reaches y.
Intuitive explanation: eventually every vertex (except 0) will has 1 edge to a smaller label vertex, forming a tree. Also for this tree to be formed, C(|V|, 2) queries is required.

References: live video feed.

Monday 16 June 2014

比賽 × 4

Topcoder SRM 624

題目非常 standard, 估計是為了測試 TopCoder 終於肯 support 大於 50 的 vector input
加上不久前開始 support special judge TopCoder 支援的題目類型終於可以跟其它 OJ 相提並論

E 在 system test fail 了, 不過憑著 5 棍 hack 和 RP 仍然保住 T-shirt 一件

終極 fail

Task H: 構造 integers input 使得 C++, Java 的 hash table (對應為 unordered_set 和 hashset) insert n 個 integer 的時間為 O(n2)

Contest 時沒有做, 不過若不是這題也未必會知道 C++/Java hash table 的 implementation
兩個 language 的 hash table 也是用 chaining, insert 時會 search 一次整個 bucket, 所以只要不斷 hash key collision 就可以退化為 O(n2)
然後跟據題解的不斷 dig into source code, 就可以發現:

- C++ 的 hash table size 必為 prime, 並 default 在 load factor = 1 時 double hash table size; 而 hash function 則為 modulo 現在的 hash table size
- Java 的 hash table size 為 2's power, load factor = 3/4 時兩倍化, hash function 則是用 shift bit

知道實際的數字就可以輕鬆殺掉 unordered_set 和 hashset! 所以以後 CodeForces 繼 anti Java Quicksort 後可能會出現 anti hashtable..


Task M: 求 s-t maxflow, 額外限制: 每條 s-t flow 長度不長於 L. Small: L ≤ 3, Large: L ≤ 6

Small 的話可以很容易 model 做 maxflow, 很 standard
Large 解題報告用了一個例子去說明很可能沒有 "一般" maxflow 的做法, 因為當 L > 3 存在 integral capacity graph 但答案不是 integer
但其實不難發現可以 model 為一個 O(L|E|) 個 variables 的 LP, 相當於 60000 個 variables.. 於是放棄之

Contest 過後看題解, 原來這個就是 intended solution! 不得不說 simplex 真是奇妙的東西

題解 booklet

Wednesday 26 March 2014

Cross the Pacific - UW-Seattle Campus Visit

因為拿到了 UW 的 offer 所以應邀到他們的 campus visit day, 似乎是很大型的活動, 很多 grad student 和整個 department 都參與其中
Visit 的部份, 簡單來說就是和 potential 的 advisors 還有 theory 的學生見面
不過 visit day 受到的待遇實在是太好了, 收買人心啊

University of Washington
UW 的感覺就是, 和 stereotype 中的美國大學一樣, 平地, 散在四方不是太高的建築
去的時侯剛好看到櫻花開:




CSE 大樓的設計也很不錯, 採光率很高, 而且自帶咖啡店 (加分)


Seattle downtown
既然是第一次來就去些 tourist spot 吧..
傳說中第一間 starbucks


市中心的地下巴士/輕鐵站, 很 optimal 的設計, 個人覺得最理想的市中心應該把所有的交通放到地底下, 行人和辦公室在地面


還有 Seattle Starbucks 的出現率不合理地高, 一個 5 分鐘行完的 u-village 竟然就有 4 間

Flight

Delta, 去程終於坐到了 767, 現在就只差 787
回程 333, 中停東京, 在同一個位置中一共坐了 15 小時

在 NRT 見到 ANA 的 787, ANA 用來飛 Seattle, 所以應該還是有不小的機率可以坐到

Tuesday 11 March 2014

頹廢的二月,去年的極光,SDP,grad school 和咖啡

- 自從二月初收到 UW 的 offer 終於不用 F5 gradcafe (其實已經是一個月多前),之後便開始頹廢
- 頹廢的 year 4 sem 2 已到中期,而且幾乎每天都是陰天還要加上頹廢的 ELT 和 325
- 三月中,grad school 的消息幾乎塵埃落定,到底是去雖然不夠凍而且經常下雨但環境優良交通方便的 UW-seattle 還是 complexity 人數較多位於東部的 Rutgers 呢 ?
- 去年約這個時侯在看極光還有雪景,又想去旅行了
- 不得不說 CS5060 比想像中有趣,一開始的印象是類 optimization 的 course (其實還是很像)
- 對咖啡的要求似乎愈來愈高了,已經從 French press 轉到 Expresso machine, 而且從兩年前的 "lunch → 兩半" 轉為 "買午餐上兩半",不過這兩件事是沒有關係的