Author Archives: DQ

Week 3，Life never changes

好吧，我承认我又忘记来这里了。又是新的一周开始了，我才想起来。

上周其实就两件事情，正如我今天开组会汇报的一样，一个是做UI Automation，说白了就是用C#去控制MFC，蛋疼了一点，然后是为了自动点击一些对话框，每天早上开机启动的时候要点很多，唉~不过这个工作跟上周Client Setting那个一样，估计到最后也不会用的，只是我没事情做，先开始做着呗，写点好的api造福后人吧。

另外一件就是HummingBird的database migration了，由于table schema改了，column name和type也都改了，所以先用excel造了一个庞大的对照表，不得不说新的DB无论从schema还是从column name来说，都比老的专业不少，显然pete和kevin是专业的。好吧。庞大的对照表建好之后开始用pete的新library写migration programme，进展还算顺利的，嗯，今天早上交差，其实周五下班就交差了。然后没什么大问题，嗯嗯，很好。

上周开始每周都有Lunch & Learning Event，嗯，还跟SG那里进行video conference，真正的video conference啊，才发现去年夏天我们做的东西多么小儿科，镜头就不是广角的，分辨率也好低，屏幕也小……不过每周有一天的lunch就必然是三明治了，不过不是普通的餐旦治，很正宗的西式三明治，培根，西冷牛排，啧啧，还是不错的，不过就是凉的，呜……

好吧，周五一早很蛋疼的8点就到，因为有个什么diversity breakfast，就是叫几个人来跟你坐一起吃三明治，有一搭没一搭的说几句。灰常的木有意思……不过会上碰到banking的一聊，才发现tech还是很幸福的，banking的人每天都是11点（PM）下班，有时候2/3点都有，5点通顶的都有，唉……真是……我宁可少拿点钱吧……这简直就不是人过的日子，还有什么生活质量可言啊。

嗯，周五去看了布拉德皮特的《生命之树》，果然情节慢啊慢，风景不错的，特效做的也不错，就是人物出场的时间少了点，说的话也拖老长，为的就是少说两句吧……唉……传教片，表示木有看懂。

哦对了，最近training很不来势，被自己鄙视了…更努力…

Week2 – Wing Lee St.

啊，一个小长假就忘记来这里了。今天补上，趁记忆还不是很模糊……

实习进入第二周，各种权限设定也都告一段落了，只是被visual studio的安装搞的很头大，RTM版的VS2008装不了SQL2008的Management Tool。可我不要SQL Server就要这个Tool，实在是悲催的最后装回2005。好吧，这周五是公众假期，所以只上4天班。

周一开始例行周会了，不过会上倒没我什么事情，就是坐那听听这周有什么news，工作有什么计划，反正价值高的活混不到我来做，Kevin和Pete两个专业写手很强大，我打打杂老老实实做support吧。这周的主要工作是找HummingBird的UI里的一些Bug，这个东西还是很早以前写的了，做了一周的Code Review，结果发现这个写的实在是不怎么Elegant，唉……开始艰难的Debug。

不过这周就这么一个活，还是很轻松，我实在想不通是哪个傻X会每次Load所有的Data，再每次重新逐条Update进数据库，check一下会死的啊。然后一本正经写了一个O(N^3)的check，结果无论如何都是return true的，搞毛。于是Save一下Data需要10秒，一共就1000条数据……真是佩服的五体投地。好在这个UI就这两个月凑合用用，等Kevin那边re-engineering完就totally报废。不的不感叹我干的活真是木有长远价值……

其实到周三我已经基本上把能改的都改了，我知道周四我们team一半人修年假，所以周四我就做了一天ACM题，呵呵，有点说不过去哈，题目是joe给我出的，7月16日local赛。首次跟阿joe合作。周四晚上做长春07的题目，被集体虐杀，只靠chin爷华丽的做了一道，然后剩下两道一题错在我，一题TLE。后来又轻松过了一道最短路，实在是非常坑爹。

有空写题解。Mark住先。

周末背着单反去了趟上环，去找那传说中的永利街，拍岁月神偷的地方。上环比起中环，保留了一些旧时代的气息，我基本上从山脚下爬上了半山的豪宅区，结果找不着路返回一路走到了西营盘。于是萌生了买张地图踏遍香港的想法，然后走过的路就在地图上标记起来，看看自己有多少能耐。后来洗澡的时候突发奇想想把这个做成一个app，依旧Mark住先，有空再来想。永利街在最后我将要放弃的时候找到了，比我想像中的还要破败，还在翻修，要不是回去一对比，我还真认不出来了。不过暴走3个小时，还喝到了曾特首最爱喝的竹蔗水，还是有点小满足的。

周日一口气看了三部速度与激情，虽然情节滥俗，但是车技还是很不错的，N2O让我想起了跑跑卡丁车，真是岁月不饶人啊。想起那时候买张点卡都是横凑竖凑，这么七八年过去了，什么都涨，唯一不涨的还就是那几张点卡…

有时候，一个人走在街头的感觉，也很不错。

（不知道为什么，照片就是传不上来……）

 

Week 1 – Nice start

其实，本来打算一天写一篇的，一开始两天忙了一下，后面两天懒了一下，一看周五了，好吧，我改写周记。

合同上本来写的是9点到6点是工作时间，鉴于我们team的情况比较特殊，于是我被要求8点半就到去开系统。好吧，其实这没什么，因为我老板的老板坐我旁边（实在感叹香港地方真是小，换在国内早就独立办公室了），每天早上7点半就到，把我狠狠的震惊了。之前培训的时候听neil说英国人是工作狂人，也没想到是这个样子。之后我养成了去那吃早饭的习惯，于是8点出头就到了，就问他为什么到的这么早。他只是淡淡的说，要和伦敦同步。

拜一个，当初就是他第一个面试的我，然后一个劲的对我说nice start，因为我是那天interview的第一个人。后来我们在闲扯的时候说，当初面试的时候他就想把我直接留下来开始干活算了，受宠若惊。

好吧，之前扯了这么多，从头说起吧。我在的team – auto pricing，属于equity derivative下面的，RBS在IT上的架构还是很宏伟的，人也很多，各种team，各种department。我的team里遇到了当年面试我的Jung，韩国人，当初聊的很欢，我的buddy和manager就不多说了，嗯，这个team里本地人比较多，所以我跟kevin说广东话，跟yip说英语，虽然yip跟别人都说广东话。

第一天其实还是intern们一起听各种IT部介绍，然后领自己的job description。大概下午5点回到自己的座位吧，然后大概看了一个环境，3显示器2电脑，因为RBS收了ABN，所以一台是RBS的一台是ABN的，嗯，办公用品齐全，电话很高级，跟电脑都连着的。然后座位还是很宽敞的，嗯，就是这样~不过不得不惊叹RBS的条件，茶水间要啥有啥，可乐雪碧苹果汁柠檬茶，各种饼干水果，各种咖啡茶包，相比于lyf美林的自动售货机，好的不是那么一点点……

OK第一天就这么愉快的结束了，kevin跟我说基本上都是6点半撤的，好吧，6点半就6点半，木有关系。第二天开始8点半到，因为我负责的auto pricing系统叫HummingBird,每天8点半要开始启动，嗯，然后就要去观摩学习自己操作。悲催的是我把7点闹铃按掉了，结果王左的铃声拯救了我，醒来7点半……即刻奔下去，进办公室8点31……以为死定了，幸好人不多……这一天就在搞各种request，request权限，安装文件，系统设置，blablabla……又一天结束了……

好了第三天开始就我负责每天开系统了，每天kevin会坐我旁边然后看我开，并给我介绍介绍，我有时的确很惊讶投行的系统……居然跟我说用excel来做的，然后excel这个东西不稳定，容易crash……所以他们正在全部转成.NET。早干什么去了，那个excel看的我纠结啊……各种bug，各种runtime error，各种resource unavailable……算了，我充其量也是路过打多几次酱油……不作评论。

事情在第四天开始真正有点事情做了，kevin告诉我要写一个utility，用来给一个monitoring system做插件，嗯，好的，其实就是连连数据库，写写log file，不过用c#写，外加一点外部class比如log4net，好吧，这才是我该做的事情嘛~于是乎，我花了两天时间，就搞定了，等我第二天上午跟kevin说我写完了，他表示压力很大……

之后的空闲时间，多半是在浏览rbs内各种网页，各种系统，各种申请，然后周五下午打算做SGU，发现提交是global error，之前听过有人上传code被解雇了，我怀疑会不会有问题……事实证明是sgu SB，好吧，下周开始如果木有事情我就做题去了……

周五yip跟我聊了一个多小时，说说公司业务情况，IT部人进来的发展线路，无外乎两条线，一面向PM进发，一面是Senior Developer，就我观察，PM的工作比SD工作轻松，毕竟都是动动嘴皮子，写写proposal，然后具体就交给Dev了。唉，每天PM走的都比SD早，情何以堪啊。

好吧，下周开始，估计该有点事情做做了吧。

————————————————————我是谁你知道—————————————————————

《A BEST》，每天在地铁里穿梭的2个小时，就是这张专辑陪我度过的，相比摇滚轻快的风格，我还是比较喜欢沉重一点带点忧郁的味道，AYU的这张不愧是日本唱片史上销量第6大的专辑。《End Roll》，之前一直没发现这首歌，只是前天晚上望着穿梭的地铁，耳畔想起的这首歌，让我一下子觉得很有感觉。正好是高考放榜的日子，三年了，青春能有几个三年？

有时候怀念只是一刹那，却留下无尽的感伤。

Training Week – I have to admit RBS is a nice bank

2011 RBS GBM Technology Intern.

人生第一份工献给了投行，第一天onboarding的时候我跟James说我就这样把自己卖掉了，James笑着说UG会觉得卖给投行很亏，但是PG会觉得终于把自己卖出去了，不用卖给实验室了。原来PG的生活真的也是很惨烈的，UST的PG一年只有24天假，连RBS都有22天年假，这也太说不过去了的。Anyway，卖的卖了，卖卖看吧。

6.13 – 6.17, 是training week。第一天6点45就起来了，8点10分就到了CKC – 李嘉诚的老窝。当年interview的人我都认识，都在那里了，然后一起上去，开始接待。不得不惊讶RBS居然一共招了58个intern，28个是banking的，6个tech，1个risk，4个finance，几个operation十几个market。果然有政府撑腰就是有钱就是野心勃勃，大肆扩张啊。一个不大的会议室，8张桌子，随机找坐，我跟James坐一起，旁边是个很可爱的小男生，叫涂画，后来才知道他跟咪呜上学期一起去austin交换来着。其他几个都是banking的人，local，某女生high，小受不了。先是一通讲话，再是一通讲话，可能还没适应英语听力，印度口音让我听着很抓狂，不过后来慢慢就好了，onboarding的时候拿了3张门卡，感觉很好。

下午market的人去楼下有bloomberg做training，我们其他人留在上面做一个叫做assertiveness的training，简单的说就是如何让人变得aggressive但是又不让别人觉得你很贱。投行的文化大概就是这样的吧。给我们做training的是一个叫7city的培训公司，一个中年威尔士老头，英式英语很重，开始听的很吃力，后来也就差不多习惯了。

晚上是一个networking酒会，跟line manager，buddy见见面，简单聊聊，我的line manager很强壮，UK长大的，人感觉很不错，我觉得在投行能懂work life balance的人已经不多了，他就是其中一个。我的buddy又一次让我感觉世界好小，居然是99年中大cs毕业，跟刘立志一起参加过acm比赛。当时真是热泪盈眶啊，终于找到组织了……人很不错，总是带着微笑，事实证明我的manager和buddy都是good guy，嗯，很好~

好的，第一天就这么愉快的结束了，喝了几杯酒，回去的路上有点轻飘飘……

之后的四天被发配到太古去做finance&market训练，就是听lecture，然后对这个投行有一个初步的认识，培训的内容对于tech的人很深，对于finance的人很浅，但还是把我们放在了一起。呼，讲课的还是那个中年威尔士老头，人倒是非常gentlemen，可是他不是这个专业毕业的，所以讲的内容还是有点把握不好，anyway，全当是了解了。每天9点到5点，中午一个小时吃饭，3天就这么过去了。

最后一天早上还是这个老头来讲create an impact，8点就到，然后是HR来讲税，发现香港的税跟国内还是很不同的，除了MPF必须要交之外，税的话是按年算的，单身一年收入少于108,000的免税，结婚的double，有孩子还要多，剩下的钱头40,000-2%，接下来40,000-7%，12%，最后17%。嗯，来讲的是一个PWC的人，感觉很普通，很普通，很普通。

下午是一个团队合作训练，就跟当年参加的历奇差不多，教练是从SG请来的，中年威尔士老头也是SG请来的，做的游戏很有意思，的确能启发人一点道理，第二个游戏是组装一辆四轮车，能让人坐上去开的，最后我们组还拿了第一名，还有个奖杯做纪念，感觉很好。

所以，不得不说，RBS这一周的免费培训，还是很给力的。

下周开始工作。

 

如何利用Stack实现Queue？

好吧，我承认这其实是个很简单的解法，在复习阿mole的414的时候，一个问题是说怎么用Perl的Shift&Unshift以及Push&Pop去实现一个FIFO的队列。

Maintain两个Stack，叫做A和B，一开始全空。

Enqueue:

Push element into Stack A

Dequeue:

If Stack B is empty, Pop element from Stack A and Push to Stack B until Stack A is empty.

Pop element from Stack B.

不给力啊，少年，这个都想不到！

 

好吧，我知道我很久没来了。

RT。几乎荒废了这个blog，再次下决心要收拾一番，不知道这次又能坚持多久。

如果要从上次写blog算的话，差不多快1个学年没来过了。追溯一个学年前的往事，一样样说的话估计我也没这个时间没这个能力说完。估计写到哪是哪吧。

迈入final复习期，其实事情还是一堆一堆的，443还有两份作业，414还有个pro，精研组又冷不丁的杀出来个report和present，还有三个final，真是搞的头很大，几乎无从下手。两天复习差不多复习了443的一半和326的1/5，效率不算高，不过阿mole的notes永远需要配上录音才能明白，外加peter大神在录音里的贱笑实在让我理解起来有点困难。不过不得不说比起听315的录音，我的广东话的水平还是提高了不少的。

毕竟，三年了都。

好吧，让复习先一边去吧，说好final不玩魔力的，昨天还是上了那么一个晚上，的确发现自己开始无聊了，不知道顾拜蛋当初是怎么帮我练猎人的，猎人上不去厨师跟着赚不到钱。弓手45级依旧很瓶颈，就跟当初一样，7年前也是一样的，我有预感我又会在50+二转之后就放弃。曾经的阿堵物。

有时候时间的确是个杀千刀，冷不防出来偷袭一下。当我这次开始玩魔力跟人说自己是老玩家的时候，掰掰手指，1，2，3……我以为一只手已经够数的了，却发现需要两只了。8年了，刚玩那会刚上初中，现在还有一年大学就快毕业了，周围的玩伴越来越少，各自奔天涯的确木有任何问题，离家越来越远，但是想起当初第一次玩的时候还是拨号上网，一个月回来老爹就换成宽带了，心里还是很感慨。

很久不听飞儿的歌，蓦地想起当年在寝室里哼唧，还有球场上广播里的无限，还有大清早偷偷的跑到教室听MP3……

华年似水。

SRM481D1 500 (Greedy + Math)

一晃好多年，我终于爬回了D1，可是今天这场不怎么好过……NA LIB的无线果然不好使……断了两次……
其实250没做出来也不怪它……逻辑性好强……我没想清楚……唉……不早了，明天再想……

唯一值得庆幸的是最后过了500，虽然比赛规定时间内没完成，不过思路差不多对了，只是算法细节上要注意好多……

500是道概率题

问题是给你一条流水线，有n个job要做，但只有一台机器，每次只能做一个job。每个job都有需要的时间以及请求这个job的人。这个系统很聪明，他会schedule一套方案来让所有请求job的人（注意是人）等的时间的平均值最少。如果有几种方案，取任意一种。求的却是每个job完成时间的期望。

好了，首先我们要知道的是，这个机器是怎么schedule的。如果没有“人”这个条件的限制，很明显就是一个greedy，先做时间最少的。但问题这里是minimize人的平均等待时间。如果还是照之前的greedy，就出问题了。题目的Case1就是例子。稍微推一下就可以发现，schedule的方法是把每个人的job都合并起来，对总时间排序，先把一个人的做完了，再做下一个人的。但一个人的工作中间的次序是任意的，谁前谁后这就是要算期望了。推出这个期望跟杨辉三角很有关系~嗯~但是还没完，如果几个人的工作总时间相同，他们之间的顺序也任意，这又是一层期望。所以要算两层，外面这层还是跟杨辉三角有关……推出公式就发现很简单了，剩下的就是仔细code了。

code的时候因为时间最大是10^9，所以int超了，fail一次……改long long，有两个小地方没改过来，又fail一次，最后过的很顺利。印象中第一次做出D1 500，再接再厉。

贴code：

#include "cmath"
#include "ctime"
#include "iostream"
#include "string"
#include "vector"
#include "map"
#include "cstring"
#include "cstdio"
#include "set"
#include "algorithm"
#include "queue"
using namespace std;
typedef long long LL;
LL t[55];
 
bool cmp(const int i,const int j)
{
    return t[i]<t[j];
}
 
class BatchSystemRoulette {
public:
    vector <double> expectedFinishTimes( vector <int> duration, vector <string> user ) {
        int n=duration.size();
        map<string,int> m;
        vector<int> v[55];
        int id[55];
        vector<double> ret;
        memset(t,0,sizeof(t));
        int nu=0;
        for(int i=0;i<n;i++)
            if(m.find(user[i])==m.end()) { m[user[i]]=nu++; }
        for(int i=0;i<n;i++)
        {
            ret.push_back(0);
            t[m[user[i]]]+=duration[i];
            v[m[user[i]]].push_back(i);
        }
        for(int i=0;i<nu;i++) id[i]=i;
        sort(id,id+nu,cmp);
        for(int i=0;i<nu;i++)
        {
            int p=v[id[i]].size();
            for(int j=0;j<p;j++)
            {
                ret[v[id[i]][j]]=duration[v[id[i]][j]]+(t[id[i]]-duration[v[id[i]][j]])/2.0;
            }
        }
        LL now=0,pre=t[id[0]],cnt=1;
        for(int i=1;i<=nu;i++)
        {
            if(i==nu||t[id[i]]!=pre) {
                for(int j=i-1;j>=i-cnt;j--)
                {
                    int p=v[id[j]].size();
                    double tmp=(now*2.0+(cnt-1)*pre)/2.0;
                    for(int k=0;k<p;k++)
                    ret[v[id[j]][k]]+=tmp;
                }
                if(i!=nu)
                {
                    now+=cnt*pre;
                    cnt=1; pre=t[id[i]];
                }
            }
            else cnt++;
        }
        return ret;
    }
};

UVA 11813 Shopping(SPFA+DP)

以前从来没真正写过SPFA，难怪training的时候做不出来了……大悲剧啊……题目的意思就是说在一个很大很大的图中从一个固定的点开始访问其中一些点并最终回到起点，求最短的路径。一些点的数量不多过10个。很容易想到状态dp。
设dp[i][j]表示的是当前在i点并且已经访问了点的状态为j。转移方程为
dp[i][j]=dp[p][k]+dis[p][i] if( (j^k)==(1<<i) && (1<<p)&(k)==true )
其中j的已访问节点数比k大1。所以做bottom-up的DP，以已访问的节点数来做。

最后最麻烦的就是SPFA的写法，参照百度百科写了一个。效率还不错。

int n,m,s,st[11];
int next[200010],ev[200010],ew[200010],nbs[100005];
int used[100005],q[100005],dis[11][100005];
void spfa(int s,int id)
{
    int head=0,tail=1,u,v,w;
    for(int i=0;i&lt;n;i++) { used[i]=q[i]=0; dis[id][i]=inf; }
    dis[id][s]=0;
    q[tail]=s; used[s]=1;
    while(head!=tail)
    {
        head=(head+1)%(n+1);
        u=q[head];
        used[u]=0;
        for(int i=nbs[u];i;i=next[i])
        {
            v=ev[i]; w=ew[i];
            if(dis[id][v]-w&gt;dis[id][u])
            {
                dis[id][v]=dis[id][u]+w;
                if(!used[v])
                {
                    tail=(tail+1)%(n+1);
                    q[tail]=v; used[v]=1;
                }
            }
        }
    }
}

要加油了。

ACM Summer Training June 10,2010 – POJ2018 + IPCP 4477,4478,4479

唉，原本准备每次training完就写report的，结果你看……还是拖了这么久，而且上个星期的那套题目还没有补上，我这是多么的懒啊……

今天是GAG GUY 讲题目，这是我目前为止见过的最nb的acmer……因为他只是个高中生（中七），水平比我高……跟阿joe，Leo，Kn有的一拼，这让我再次明白了一个道理，那就是……没有谁是不能被替代的，长江后浪推前浪啊~~

（好困……）

ACM Summer Training May 27,2010 – SRM 470 DIV1 500

歇了好几个月的blog终于重见天日了。时间总是过得如此之快，一眨眼，3个月就这么过去了，期间发生的事情太多太多，而我又突然变得又忙又懒……于是，悲剧就这样产生，很多事情，我已然不是记得很清楚了。

然而我总是该写些什么的。

本来不想把这里变成一个技术blog的啊啊啊啊啊啊~~~

好了，言归正传。

下周开始星期一、二、四Training， 星期一老队员讲课，星期二老队员打code，星期四老队员Seminar。 这个暑假我负责讲DP……DP……一个又爱又恨的东西……

昨天敲定了这些事情，接着Gary讲了一道SRM470 D1 500的题目。

题目在这:http://www.topcoder.com/stat?c=problem_statement&pm=10735&rd=14153

一道关于概率的题目……不由得让我想起了327的final，最后就差一个概率题没做出来，不由得感叹数学是多么的重要。（这是后话）

题目的大概意思是说，有上下两排点，分别由N个，我现在告诉你其中一些pair已经连起来了，还有剩下的没有连起来的点随机的组合相连，问得是这N个pairs相交的数量的期望是多少。注意题目说的是Number of Crosses, 不是Number of intersection points。 所以不需要考虑交于一点的可能。

然后……这个题目该怎么做呢？

我们知道期望是线性关系的，所以可以拆分……Totally我们一共有N条线，对于其中任意的两条，假设叫line X 和 Y。（且line X 的top point index 小于line Y的index），那么我们的总期望就是每一个这种pair的期望的和。对于line X 和 Y，一共有4种可能。 两条都是fix的，两条都不是fix的，X是fix的而Y不是，Y是fix而X不是。对每种情况都可以计算。

1）对于两条都fix的，那么就直接判定它们相交与否。top[i]<top[j] && bottom[i]>bottom[j]

2）对于两条都不fix，期望是0.5。这个需要推算一下，应该不难，用CTLi的话说，应该好直观= =||

3）对于一条fix一条不fix的，统计下相交的点的数目再算出概率就行。

贴贴代码……这是O（N^2）的算法，ZQ有O（m^2）的算法，就不是挨个统计而是集体算= =||对于N很大的话可以瞬秒

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 10005
#define clr(a) memset(a,0,sizeof(a))
class DrawingLines{
	public:
	double countLineCrossings(int n,vector up,vector down)
	{
		bool top[maxn],bottom[maxn];
		int  sa[maxn],sb[maxn],match[maxn];
		double ans=0;
		clr(top); clr(bottom); clr(sa); clr(sb);
		for(int i=0;imatch[j]) ans+=1;
				}else
				if(!top[i]&amp;&amp;top[j]) {
					ans+=((double)(n-match[j]-up.size()+sb[match[j]]))/(n-up.size());
				}else
				if(top[i]&amp;&amp;!top[j]) {
					ans+=((double)(match[i]-sb[match[i]]))/(n-up.size());
				}else {
					ans+=0.5;
				}
		return ans;
	}
};