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

Yandex 2011 Round 2

好不容易才打到 Round 2, 不過都係與 T-shirt 無緣

A - 見識過 Round 1 的 A, 對這次的 A 已有心理準備, 先寫一個慢的 program 去找 observation, 有 2 個重要的發現:

4, 49, 499, 4999, 49999.. 是 peak 值 ;
去除這些 peak 值, 如果 x < y, 有 weight(x) < weight(y)

所以解法是先試試 weight(r), 然後試試 4, 49, 499 .. 等


B - 題目個 tag: Constructive algorithm
一開始還是被嚇住了, 之後想到一個很麻煩的做法:

1. 對每個 row, 每堆連續的 space 可以用 length 2 和 3 的 figure cover (2+2+2... / 3+2+2+2...)
2. 之後就是 handle 一些 alone space, 我先把垂直相連還未被 cover 的 space 用上述方法 cover
3. 最後便是一些

#000#
##.##
11122

的 space, 如果上下都是 #, 則無解; 否則可以「痴」到上下的 figure, 但還有一個麻煩情況, 就是

#.#.#
#...#
#.#.#

不合法的 figure. 所以如果上下的是 "000" 的形狀, 我會把它們砌成:

#.###      #0###
#111#  ->  #011#
#.###      #0###

怎看也很煩膠的方法, 用了 >30 分鐘去寫+debug, 不過最後還是過不了, 原因是我 label 那些 figure 時應該出了錯, 用了同一個數字去 represent 算法「認為」不是同一個 figure 但相連的 figure, 其實我寫的時侯已經有刻意留意, 不過問題是只有 10 個數字用, 十分不足, 逼不得已去「重用」一些數字時出錯..


C - 又是 AC 自動機 + DP, 完場前 5 分鐘寫完, 不過連 sample 也未過到; 之後都用左好多時間 debug, quote Joe神一句

因為曾經做過的關係，有些第一次做會錯的地方都避免了

原來第一次做真的會有很多地方出錯, 而且是對著錯的 data 才發現錯處, 即是就算放棄 B 不做也應該過不到 C, 而且過到 B 也入不到頭 70, 結論就是無論如何也入不到頭 70

SRM 504.5

250
又是和 4,7 有關的數論題
想過用BFS, 但想想又覺得會寫得很長
最後還是直接把 10 個 case 打落去

550
花了一段時間, 觀察到 money[] 會續漸趨向一樣, 然後就可以很快計算結果
但想來想去也覺得就咁 simulate 趨向一樣前的 process 會很慢..
加上不懂得在不 overflow 的情況下計算 average (是出題者刻意的伏?), 所以決定開 900 做

900
其實是頗 standard 的機率題..
我的做法是計算 p(x) = 前面有 x 個人, 後面沒有人時, 被選中的機率
可以在 O(N²) 計算..
但是完場時還是過不到sample, 後來發現沒有 handle 「只剩自己一人」的case