遥想小魔王的计算机竞赛峥嵘岁月 --- 附楼天成回忆录

遥想小魔王的计算机竞赛峥嵘岁月 --- 附楼天成回忆录

这是一篇回忆录性质的文章。Growth hacking 的文章写得累了,接下来写几篇自己喜欢的。现在的公司搬入了新的办公室,高大上的位置,精致且有考究的装修,真是仿佛回到Facebook一样的办公环境一样。

--- 言归正传 ---

很多人问我:之前是如何进入Facebook的,或者是如何申请进入CMU的。关于进入FB或者CMU,我都有长长的故事可以说。(比如 Facebook之前面试的博文:[朝花夕拾系列] Facebook,Google,Microsoft面试记录---我的奋斗 1/2 - 覃超帝国兴亡史 - 在希望的田野上 - 知乎专栏 ,文章写于2010年的4月份,一晃眼已经五年了,真是岁月蹉跎) 不得不承认,不管是之前进入 Google Intern,还是后来的申请CMU,以及最后的Facebook面试,编程能力都起了关键作用。而客观说来,我自己的编程能力几乎都是大学里参加 ACM-ICPC (和后来参加TopCoder)打下的基础。

开始接触编程,还要回溯到初中时期。当时学校里开了计算机竞赛班,学的是 basic 和 pascal,老师教了一些基本的算法和数据结构,然后就开始比赛。可惜当年学校和环境实在是太难,走了一轮NOIP的水赛,就做对了一个题目,想起来真是自己的黑历史。我还清楚地记得当年湖南OI的第一名是张一飞,后来他也顺利进入了冬令营和国家队,最后获得IOI的金牌。

初中不顺利之后,整个高中就没有再参与计算机竞赛(其实我们学校就压根没有高中生的竞赛班,因为我们从来都没有获得过省赛的名次。我们的数学和物理也就最多获得过省内的一等奖,离保送还有着不小的距离)。整个高中就是在正常而紧张的高考复习中继续着。

可惜高考也没考好,去了同济大学。不过平台的高度远远好于之前的中学。整个大一我还在懵懂地学习课程之中,直到一个偶然的机会,接触到了当时面向大一新生举办的计算机程序大赛。我获得的名次并不好,不过这次比赛让我渐渐地找回了当年在初中写程序的快乐感觉,外加同济大学当时有一个非常好的在线做题系统:Tongji online judge。于是对于编程和程序竞赛,我重新提起自己的兴趣。

大二上学期,我正式注册了Tongji online judge,开始刷题。当时最火的OJ是浙江大学,而北大的OJ系统还在公测的状态下。做过题的同学都知道,有时候刷起题目来是会上瘾的。而我当时就进入了这么着魔的状态。我的确算是ACM-ICPC里面起步很晚的了,大二才开始复习写一些简单的程序,然后学递归和回溯,再然后开始写一些搜索(BFS / DFS 等等)。在Tongji组内的排名也慢慢跃至前几名,后来就一直保持着,直到后来TOJ的主机挂掉。现在我依然记忆犹新的是大二时候的那个暑假,当时参加学校的暑期集训,和很多刚刚高中毕业保送来的大一新生合作。我们每天都按时完成规定好的 SGU 上面的题目,还要写解题报告,总结和强化那一类题目的解题方法。那个暑假是我编程能力上升最快的时候,也是我对于编程来说最最美好的回忆。有时我甚至觉得,如果历史可以回滚,回到那个暑假,过着早上起来买个早饭,然后就去机房开始做题;中午和晚上吃个饭,接着又是不停做题的节奏是一件非常愉悦的事情。每天按时作息,每天都可以学习到不少有用的知识,然后慢慢积累起来,在量变中等待那么一个质变的过程。有时候我很讨厌现在这个移动互联网的时代,让人养成了动不动就去刷一下手机的习惯,让人变成了一个“碎人”。很多时候没法长时间专心地做、思考一件事情,甚至连朋友们一起出来吃饭的时候,都变成了一个看手机比赛。


接下来就进入了TopCoder时代。同济ACM队里面的几个人开始研究TopCoder,并且在一次Google的比赛中认识一批中山大学做TopCoder的人,于是快速开始了合作。我也马上加入了TopCoder的行列,开始做算法,后来转为做Dev。TopCoder和做大学生程序竞赛的一大区别就是可以很好地赚钱。当时还在06年时代,TopCoder上聚集了一对来自浙大的编程大牛,再到后来的中山大学,有时候给人的感觉就是TopCoder里面的开发任务基本上被中国人承包了。遥想当年,物价水平低,大学吃顿饭3块或者5块就可以搞定。美元和人民币是 1:7.5 的兑换关系。当年一个月1000到2000美元的收入,在我们同济那个郊外校区就是完全花不完的节奏。具体如何参加TopCoder的可以看我在知乎上的一个回答:你在大学里是怎样赚到钱的? - 覃超的回答 今天再读这个答案,依然还很有感触:当年追随的大神们一个个在工作或者比赛中见到真人,偶尔和里面的一批人成为了线下的朋友。在一起打游戏或者工作或者滑雪或者hiking中聊起当年竞赛或者TopCoder的事情,收获的是满满的回忆。

后来进入Google实习,以及后来拿到CMU的录取,ACM-ICPC和TopCoder都给了我最为重要的知识基础。即使是后续的Facebook面试,参加面试的人都知道基础的编程能力对于解面试题是多么的重要。而我们ACM-ICPC所解决的那些编程题目,难度都几倍于这些互联网公司的面试题目。在Google实习的时候,我认识了楼天成(楼教主),我还记得他在Google电脑上对打魔兽争霸(08年的时候),而他更加喜欢在我后面看我打星际争霸。他那一句”牛逼!瞬间120人口的爆兵“永远地留在了我的记忆中。2009年的时候,到了TopCoder Open决赛,至今我还记得,在赌城拉斯维加斯的算法决赛中:开始楼爷一直决赛领先,但是最后的500、1000的题目没有过 machine test。而最后一个中国的高中生(保送交大)爆冷夺得了2009 TopCoder Open算法比赛的冠军。(见下图)


2010年底,我进入了Facebook,碰到了很多之前的老面孔。我走到了张一飞的桌前,说到:“你好,我叫覃超。今天刚刚入职Facebook,也是湖南人。小时候我参加NOIP的时候,你是当时那年的冠军。” 他憨厚地笑了笑说,很高兴认识,以后便是同事了。我说对的,以后请多多指教。外加心里一句:我奋斗了XXX年,终于可以和你在一个公司的桌子上,握一次手,打一个招呼。在Bootcamp上,我见到了 Kent Beck 和 Lars,我一一和他们打招呼还有膜拜。他们两个,前者是 JUnit 和 Extreme programming 的发明人,后者是 Google maps 和 Google wave 的掌门人。如今我得以在Facebook的平台上和他们一同工作,是多么幸运和自豪的一件事情。


好朋友李老师(李睿):(下图牛人无数)

一想起他,我几乎可以笑出声来:我们打过无数次台球,一起滑过好多次雪,还有在湾区的汤司令无数次地撸串。即使今年5月他回国内,我们还在杭州的酒吧切磋台球。我想我们都会变老,但是唯一不变的便是当年编程比赛所建立起来的友谊。

再后来的后来,里面的有些大牛陆陆续续地离开Facebook,去追逐自己的梦想。也有一批大牛们(比如 张一飞,毛子青)还在Facebook里继续发光发热。而我也将选择我最喜欢的道路和方向,暂时离开他们和我心爱的Facebook,去追求我下一个阶段的目标。俱往矣,属风流人物,还看今朝~

所以,很多人高中或者刚进大学的人问我以后道路要如何走,我始终会推荐他们去参加ACM-ICPC和TopCoder,这一路来它们给我带来了太多的机遇和精彩的回忆。希望国内ACM-ICPC高手们,我们可以多聚聚多交流(私信欢迎)。

最后附带楼天成当年写的文章,说关于自己参加各种比赛的会议。非常干货,也极为精彩。大家 ENJOY~


最后,所有的朋友们,如果你喜欢我知乎的回答或者专栏的文章,或者我之前分享过的一些轶事让你有所收获,亦或是单纯喜欢我文字诙谐而又深邃的风格,那支持一下呗 :D ---> 喜欢的话,就买一件我QC帝国的体恤, that would inspire me so much!!

覃超小魔王求支持~T社



(以下为楼教主 ACM-ICPC 的回顾节选,最后附上完整文章的链接)


利用假期空闲之时,将这几年 GCJ,ACM,TopCoder 参加的一些重要比赛作个 回顾。昨天是 GCJ2006 的回忆,今天时间上更早一些吧,我现在还清晰记得 3 年 前,我刚刚参加 ACM 时参加北京赛区 2005 和杭州赛区 2005 的情况。

2005 年 ACM-ICPC——酸甜苦辣

我进入清华大学开始本科学习的时间是 2004 年 8 月,在进入清华大学的第一

年里,由于基础课学习比较紧张,再加上计算机系不允许大一学生自带电脑,我没 有参加 2004 年的 ACM 比赛。不过在大一一年中没有停止这方面的练习,对 ACM 还是热情高涨。

大概在 2005 年 7 月底,与同班同学 shell(贝小辉)和 superzn(张宁)一起 决定组队参加 ACM 比赛。对于队名没有太多的想法,就随便取了一个字典序靠前 一点的 bomber。随后进行的几场训练中,我的编程状态一直保持得很好,训练比 赛的主要方式都是:我主写程序,shell 和 superzn 负责翻译题目,思考算法和测试。 这种组队模式一直沿用到我们后面的所有比赛中。

2005 年底,我们报名参加了 2005 年的北京赛区和杭州赛区的比赛。顺利通过 了预赛进入了现场决赛。记得当时北京赛区预赛的时候,我和 superzn 一起在参加 百度之星程序设计大赛,shell 依靠一人之力过了 6 题,最后以第二名的资格参加 北京赛区现场比赛。


北京赛区:
2005 年的北京赛区地点设在隔壁的北京大学,由于交通非常方便,我们没有

和大部分选手住在一起,不过也没有参加 Java-Challenge 和晚上的表演。 练习赛之前,说到比赛位置抽签,本身意义不是很大,可是邬老师神奇的 RP

把两只清华的队伍抽在一起,结果练习赛进行了一半,另一只清华的队伍 THU1 (队员是:吴景岳,栗师和金凯,好像后来队名改成了 DreamCatcher,不是很确 定)被要求换到一个比较远的地方,理由是有些学校觉得这样不合理。后来很多赛 区也出现过队伍座位在一起的情况,邬老师的 RP 果然不是盖的。

记得练习赛时和复旦的 LemonTree(盛城)一起在场地里闲逛,结果果然不到 10 分钟就被要求回座位了。还有当时比赛场地是一个体育馆,有些队伍把气球放 飞之后气球就飘在天花板下了,总裁判李文新老师还威胁我们说,如果明天正式比 赛把气球放飞,就不算通过相应的题目,除非有办法把气球取下来。

  然后就是比赛的过程了,下面有底纹的文字是我找到的当时留下的比赛总结:

E:快速排序。5 分钟 1Y。
我想 5 分钟的时间可以争取这几年 ACM 国内赛区的最快出题记录了吧。 G:二分答案+最小生成树。25 分钟 1Y。 这题就是经典的最优比例生成树问题,我们一致认为这题比较简单。不过后来

被李文新老师批评了,说法是误导其他的队伍。不过说到最优比例生成树问题, TCO2006 的时候 fwj 和 tomek 竟然都没有见过这道题目,这题可是源于 POI 呀。我 想我们认为这道题目简单的主要原因是我们都在冬令营上见过这到题目,如果第一 次看见,想出算法可能确实需要一些时间。在这里向被我们影响的队伍的道歉,最 终 G 提交了 200 多次,但是只有 8 个队伍 AC。


C:二分图最大匹配。42 分钟 1Y 题目要求计算一张图的最小覆盖集,可能唯一的 tricky 是发现图是二分图。 D:遇到了一定的困难,发现 A 很简单,于是先放一下
D 是一道比较综合的题目,设计一些简单的计算几何和字符串处理的知识。 A:简单的几何问题,出现了一个低级错误,提交了 3 次均为 WA。
A 是北京赛区最简单的题目,我的程序里犯了一个很低级的错误,可能也是经

验不足造成的吧。

D:重新写,但是没有考虑一种情况,WA 了 1 次。

87 分钟,复旦的 Abuacus 过了 4 题占据了 Rank1。由于队伍模式的原因,我们 在还有很多简单题目的情况下卡住了长达 30 分钟。

A:shell 突然发现了 A 程序中的低级错误,105 分钟 AC,重新夺回 Rank1。 这是很重要的一步,现在想来如果没有这个发现,后果可能不堪设想。 B:二分答案+2SAT。129 分钟 AC。
B 是一道明显的 2SAT 问题,由于题目比较长,我们没有很早发现这道简单题。 D:发现了 D 的没有考虑的情况,140 分钟 AC。

看了一个 board,那时 Abuacus,Eccentric 都只有 4 题,能够在第一次参加正 式比赛就做到 6-4 的领先,当时心情很激动,不过由于缺少经验,也影响了接下来 的发挥。其实,现在回想起来,这次比赛其实是一个很好的 AK 的机会。

F:DP。程序比较复杂,WA 了 4 次。

F 是一道比较复杂的动态规划的题目,其实 WA 的原因是一个应该用 int64 的 地方,我们使用了 int,这个地方的确很难发现。

  对于我们这种组队模式,当主写程序的选手状态不好的时候,很容易出现连续
卡题的情况,这种情况的出现很不利于水平的正常发挥。在北京赛区的比赛中,我
们很有幸没有出现连续卡处的情况。

记得,当时北京赛区的 Judge 的半自动的,就是说如果结果是 AC,速度就会非 常快,否则由于人的介入,不能 AC 的提交往往需要等一段时间。我们第 2 次提交 H 之后,没有得到很快的回复,以为已经 WA 了,于是我和 superzn 继续测试一些 数据。但此时,突然有一个 mm 从左边走过来插气球,这个气球也成为了全场唯 一的蓝色气球,这个意外之喜最后成就了第一个分区赛冠军。

在最后时刻我们似乎发现了那个 int64 的错误,不过当时思路已经比较混乱了, 没能改对。F 的问题也导致没有时间写 I,当时如果直接重写后者换 superzn 来写 F, 完全可以在比赛结束前 AC。

比赛的大致过程如上所述,那个神奇的气球,我现在仍然记忆犹新。最终有 4 个队伍攻破 7 题,Abacus 的组成应该是盛城,timegreen 和 suzhan 吧,Eccentric 中我只记得辛韬,ZSU_Panku 中我记得 Savior(陈实)。上述的老朋友之后见面的机 会就很少了,分区比赛也成为了我好需要老同学重要的交流机会了。


我 ACRush 的 ID 估计就是那时开始使用的吧,转眼就已经 3 年多了。

  比赛前后还记得经常与复旦大学的吴永辉老师聊天,在那之后的每次比赛我都
能见到他年轻的身影。

现在回想起北京的分区赛,很有幸能够在第一次参加 ACM 正式比赛就获得分 区比赛的冠军。我想是由于现场气氛对许多队伍都有不小的影响吧,当时许多队伍 都卡在几道比较繁琐的题目上了,题目的算法性都不是很强。我大概从那时才刚刚 接触 TopCoder,如果能够早一些,相信会更适应这样的比赛。

杭州赛区:
2005 年的 ACM 杭州赛区比赛在浙江大学举行,杭州赛区的时间就在北京赛区


结束后一周,最初选择杭州赛区的原因很飘逸:我自己家在杭州。实际上也差不多, 我随队伍(当时 THU 派了 3 只队伍参加杭州赛区的比赛,除了我们队之外, b142857(侯启明),zhy(周源),ysy(杨 思雨)组队,另外一只由汪汀,王俊 和黄源河组成)一同抵达杭州车站之后就马上回家休息了,直到比赛前才赶回。在 北京到杭州赛区之间的一周中,我的状态就在 不断下滑,在家中完全失去了比赛 的气氛,回到赛场再也找不到感觉了。一场悲剧即将上演。我们先看看比赛过程吧, 下面有底纹的文字是我找到的当时留下的比赛 总结:


G:初看很简单,但是调试了 30 分钟没有结果。

G 是一道数学问题,其实《具体数学》书上有明确的公式,不过我们使用的递 推方法应该也可以得到正确的结果。程序中犯了一些低级的错误,由于实在不在状 态,调试了 30 分钟还没有找到错误。这里还暴露了一个组队模式的问题,在后来 的组队模式中,如果像这样没有想清楚算法的题目队友是一定不允许我去写的。

A:模拟。41 分钟 AC,当时肯定没有想到这是唯一一道 1Y 的题目。
A 是一道模拟题,1Y 的时候已经很晚了,排名也很靠后。 C:图论。但是由于堆栈逸出 RTE 了 5 次,浪费了大量的时间。
C 的问题关于树中祖先关心的判定,题目很简单,实现的方法也很容易,就是


通过一遍 DFS 来计算。但是我们忽视了一个从来没有遇到过的问题:堆栈溢出。 而且,堆栈在本地机器上运行过程中,Eclipse 提供了 8MB 左右的堆栈,所以没有 溢出,但是在提交之后的环境下运行就溢出了。而且每次 RTE 之后,我们一直在 尝试修改数组的大小,一直没有找到根本原因。调试 C 的同时,我也尝试修改 G, 结果 G 也错了 8 次之多,并且始终都是 WA。


:shell 在我郁闷地调试 C 和 G 中 AC 了,之前 WA 了一次。
I 是动态规划问题,WA 一次可能是忽视了一些边界情况。 D:网络流,没有想到先贪心进行优化。TLE 了 5 次最终没有通过。

D 就是计算最小割,我们事先准备了先流推进算法,不过根据这道题目的模型, 先流推进算法遇到最坏情况:二分图。由于当时 dinic 还不是很流行,我们 TLE 了
5 次还没有通过。


郁闷地调试D和G。在随后的时间里,不断调试 D 和 G,但是始终不能 AC。之后又尝试 E 和 B,E 通过分段的方法可以处理,B 是数学题目。正常的话 E 和 B 并不是很困难的题目, 但是当时已经非常混乱,连样例都没有通过。


最终我们只过了 3 题,排在 21 名,经历了我参加 ACM 以来最惨痛的失败。 这次失败主要归过与我状态太差,基本上什么题目都不能顺利通过。当然题目的选 择也有很大的问题:G 确实不是难题,但是由于未知的原因始终不能通过,后来我 把纸上的程序敲在 ZJU 上就 AC 了,至于现场为什么不能 AC 我现在还是不能明白。 如果说第一题的选择直接影响了我们的信心,那么 D 的堆栈溢出则完全打乱了我 们的节奏。对于我们的组队模式,卡出 2 题已经超出了极限,我们不可能再尝试 其他题目。

Abacus 也来到了杭州,他们前期体现了强劲的先期优势,在 2 小时就达到了 6 题;b142857(侯启明),zhy(周源),ysy(杨思雨)的队伍表现得相当神勇, 在最后一小时超越了 Abacus,夺得了冠军。

  杭州赛区的失败至今仍是心中痛苦的回忆,不过这个教训也是对我今后的学
习生活的一种警示。

总结:
2005 年是我第一年参加 ACM-ICPC 的比赛,两场 ACM 分区赛,我们经历了夺

冠的兴奋,也经历了环顾四周等待比赛结束的无奈。2004 年清华没有获得任何分 区赛的冠军,2005 年清华打了个漂亮的翻身仗,先后在成都,北京和杭州夺得冠 军,而且是三支不同的队伍。

两个赛区的 G 都是有传奇色彩的题目。北京赛区中,我们 25 分钟 1Y 了 G, 导致许多队伍跟风失败,最终达到了 208 提交 8AC 的低通过率。但是,杭州赛区 中,G 从比赛一开始就占用了我们大量的时间,直到最后都没有通过,估计至少浪 费了两个小时左右。真所谓成也在 G,败也在 G。

北京赛区后,POJ 的论坛上传闻说我曾经说过“起身去厕所,不许碰键 盘。。。”,很敬仰那些同学搞笑和扯淡的功底,我们虽然定下了以我主写程序的 组队模式,但是也非常重视配合和每个人在队伍中的重要作用。

当时清华没有组织校内 PK 选拔,选择了成都赛区的冠军队 THU1 参加全球总 决赛,当时总决赛队伍是以参考第二赛区的成绩决定的,现在回想起来也是很合理 的。由于最终我们未能得到机会参加全球总决赛,接下来几个月我们情绪低落, bomber 从那时也就宣布解散了吧。


2005 年的比赛过程中,我见到了许许多多的老朋友。用吴永辉老师的话, ACM 竞赛可以看作一些老朋友一起进行的一场智力游戏。

(太长,我的专栏里先打住)

楼教主的回忆录实在太长,所以把整个PDF放在云上: https://dn-freesblog.qbox.me/@/qinchao/ACRush比赛回顾.pdf ENJOY ~


--- END ---

最后,所有的朋友们,如果你喜欢我知乎的回答或者专栏的文章;或者我之前分享过的一些轶事让你有所收获;亦或是单纯喜欢我文字诙谐而又深邃的风格。那支持一下呗 :D ---> 喜欢的话,就买一件我QC帝国的体恤, that would inspire me so much!!

覃超小魔王求支持~ T社

---Salvation Lies Within.

文章被以下专栏收录
49 条评论
推荐阅读