No, that doesn't work

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

香港 → 廣州 → 昆明 → 大理 → 麗江 → 香格里拉 → 昆明 → 廣州 → 香港

主要是為了跪拜 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(n⁴). 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(n²).

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 相提並論

Zepto Code Rush 2014

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

GCJ 2014 Round 3

終極 fail

IPSC 2014

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

Contest 時沒有做, 不過若不是這題也未必會知道 C++/Java hash table 的 implementation
兩個 language 的 hash table 也是用 chaining, insert 時會 search 一次整個 bucket, 所以只要不斷 hash key collision 就可以退化為 O(n²)
然後跟據題解的不斷 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 中的美國大學一樣, 平地, 散在四方不是太高的建築
去的時侯剛好看到櫻花開: