Archive for August, 2005

【zz from Sghao’s blog】Sghao的金牌之路

Wednesday, August 31st, 2005

零 编者按

Sghao是zju02级cs的大牛,是zju acm战队02级中当之无愧的领袖。由于他曾经到杭州少年宫教过中学生算法,积累了很多资料,在8月的时候一讲题目就说见某某ppt,还在forum上列了一堆链接,所以我们尊称为“沈老师”,每当做不出他的题目的时候就发出一大堆“哭求ppt”的帖,类似于网络用语“哭求pp”。

下面就让我们一起看一下他在自己blog上写的青少年回忆录。

一 小时候

记得5岁那年,爸爸妈妈几乎倾家荡产买了一台计算机,CEC-I,是Apple II的汉化版,内制Basic和Logo的。那些日子每个晚上就缠着爸爸教我Basic,爸爸很耐心,虽然他自己也不会Basic,但是还是坚持了边看书边教我,保证了进度。小时侯没什么事情嘛,就乱编程序自己玩玩儿,也就那时侯喜欢上了编程。

上了小学1年级,经大伯不则手段的推荐,进了只有5年级才可以进的电脑竞赛组,开始了竞赛生涯。那时侯电脑老师姓卞,是我的恩师啊,是她让我知道了编程可以解决很多很多很好玩儿的题目,也是她告诉了我电脑是用一种叫二进制的方法数数的。那时学校的计算机应该是LASER 310,是个吱吱响的机器,很好玩儿,老师用Basic给我们编了一个游戏,无聊时自己玩玩儿,嘿嘿。那时候也参加了一些竞赛,有笔试也有上机的,似乎也拿过一些奖什么的。

ft的是,上了初中就没有电脑了,也没了电脑老师,也没有了竞赛 :( 。幸好还是爸爸给我买了一台新的电脑,i486,无硬盘无声卡无光区14′单色显示器,这个电脑只能跑一种叫TC20的软件。c语言不会呀><,把家里的电脑书全部拿出来翻啊翻,其实也都是爸爸订阅的杂志啦。在90年的一刊杂志上发现了c语言连载,然后就开始啃,初一那个年代的我,看汉语杂志还是个相当的考验了,而且又没人教我:(,只能自己看自己yy。还好它跟Basic还是比较相似的,很快就会写hello, world!了,那个激动啊!

然后就写程序啊写程序,在学校上课也在下面写程序。想起来也没写多少程序,写过一个画工程图的,功能只有画点画线画圆(还有支持我家EPSON TX-100兼容打印机^_^),用起来超级麻烦,还是爸爸为了支持我,用那个程序画了第一张工程图,完成了一个粉碎机。现在想起来爸爸用那个画图比我写那个程序难上百倍呀,仰慕。哦,还有哥哥有一台打印机,记得是TH3070吧,反正当时只有UCDOS支持他的,然后哥哥想打印朝鲜文就没办法。给他写了一套程序,生成朝鲜文字库,去踢掉UCDOS的中文字库,再写一堆转换程序,跟一个韩国的编辑软件之间做格式转化的。这程序倒救活了一台打印机,赚了哥哥一顿bg,嗷嗷。

终于写程序写到功课开始不及格了,已经是快初三了,考不上高中可不行啊><,妈妈就狠狠地把电脑锁在柜子里面了。然后就做一年的功课啊功课,开始做功课了成绩还是很好弄上去的,不过最后还是差5分没考上重点高中,自费去上的-.-。

上了高中发现居然有电脑老师的,还有人参加比赛的,不过传说10年来还连个3等奖也没人拿过-_-。后来发现了秘密,是因为电脑老师是星际争霸高手,说c语言就不会的,算了,还是自己看书吧。然后高一下终于可以参加省赛了,4题做出了3题,没做出来的一个就是表达式求值的,那时还不知道啥叫堆栈呢,搞笑啊。不过这样居然还有1等奖的,据说是第三,不过因不明原因没进省队,就只能等到第二年了。第二年题目更naive了,5题还没到时间就圆满了。后来长春来了个通知,要进省队请到长春考网页制作,占50%。ft,欺负农村学生嘛~~~ 然后说不玩儿了,都高三了认真做功课上个好大学才是王道。

又是功课啊功课,不过排名上升的感觉也蛮好玩儿的,终于要填志愿了,就填了一个ZJU,玩儿火啊小子,幸好后来还是考上了……

2005年8月26日 15:56

二 上了大学

一个人扛着行李坐了两天两夜的火车,终于到了杭州这个完全陌生的地方。在开学不久的一次朝鲜族同乡会上,经一位CS师姐介绍,知道了ZJU有图灵杯,重新唤起了我竞赛之梦。也经过她的介绍,认识了一个新疆保送过来的学长,lazybug,他曾经参加过图灵杯复赛,比较知道门路,给我介绍了一些情况,还给了个网址:acm.zju.edu.cn

还记得有一天,第一次自己去机房做题,找了个最简单的题,做了两个小时终于ac,然后暗自算了一下,5小时就可以做两题,三个人一起就至少可以做六题,可以了!好可爱呀…… 还记得有一次,跟师姐一起走在路上,她突然指着从远方走过来的一个sg,说他就是去年在西安ACM竞赛拿过金牌的人,那个仰慕啊。后来知道那个人叫oldbig。 还记得在那个jj组织的叫什么西湖论剑(?)的会上,瞻仰到了zoj no1,topcoder上top 10的WishingBone,还有之前一年在日本拿冠军,刚去美国final回来的longman,只能在远处默默地tk,呵呵。

然后马上就是校赛了,找了两个队友,raincoat和xtlist,那次比的不好,也比较郁闷,似乎是30名多一点,就没进复赛。其实也很正常么,谁叫我连最小生成树都不会。后来知道隔壁班有个truelazyboy,一个人砍了4题进复赛了,才见识到了福建选手的专业。既然看到了自己差在哪里,显然要去买本算法书开始啃了。

后来的时间比较堕落,各个方面的失败加上感情问题,就整天只知道趴在床上睡觉,突然有一天下午BlueriF把我从床上拉起来,告诉了我一个好消息。据说在zoj上做150题无其他条件直接可以入暑假集训队。那时是5月初,发现自己还只有70多题,然后就跟BlueriF一起开始了有追求的生活。5月份过去了,我和BlueriF的题数刚刚凑上了150,就给jj发了个信,然后6月份去准备考试了。

终于开始了第一个暑假,第一个集训,看到了新手上路题库,发现只有3题是之前做过的-_-,有的忙了><。然后就跟BlueriF开始了长达一个月的竞争,每天白天做个一两题超过他,晚上睡觉第二天醒来就发现他又比我多了一题。终于还是在最后关头,题库马上要关闭的时候偷偷去ac了几道,超过了他^m^。BlueriF家伙人还是蛮好的,轻易地原谅了我这小样。40题还是解决了我很多问题,诸如深搜广搜图论几何贪心dp等最基本的概念统统接触了一遍。然后就是8月份了,中间还有军训,不过还是坚持了集训。哦,应该要说:有集训,不过还是坚持了军训,嘿嘿。跟老手混合在一起比赛,才见识到了wishingbone, xuchuan, oldbig, polivic等人的实力,才发现我这种小鸟简直没什么可比性,所以后来没入选校队也没觉得奇怪。不过暑假的集训生活还是觉得蛮好玩儿,决定明年继续玩儿了。

人还是失败了,付出了惨痛的代价之后才会看到自己的缺口。很快就第二次校赛了,跟BlueriF和FishingMan一起组队参加了。结果前20分钟过2题排第2,剩下时间大家一起睡觉了,名词跌啊跌,跌到近20了吧,反正最后只有安慰奖什么的。当时实在不解为什么我们发挥这么不好,不过后来明白了,平时作题和比赛是不一样的,关键有个“发挥”在起重要作用,而这个也是要靠实力的,并不是什么rp。还有发现基础知识还是掌握的不够精,就是卡死我的那个bfs,说明了问题。然后就开始了OJOJOJOJOJ,全世界大大小小的online contest一个都不放过看到了全部参加,也是这时候认识了一起contest的telly。

又是一个暑假,不过这次的生活就不一样了,跟qherlyt一起从zjg扛着席子来到yq,开始了难忘的日子。开始没有通宵证明还无法入住503,就去那个著名的打牌寝室(collin & telly & riveria)先安顿下来,床位不够还是telly把他的床让给我,他自己到隔壁去睡觉,嘿嘿。终于入住了503,还把skatou也骗过来了。三个人,共同的兴趣爱好,共同的目标,相似的生活习惯,真是难得啊。哦对了,还找了一份暑期兼职,做韩国游戏软件汉化的。每天上午去上班,下午就回来训练赛,晚上去tk各大bbs的算法版。生活还是挺充实的,而且兼职那里几乎没什么事情,上午上班其实也是去做两个zoj题目,再看看算法导论,吃个午饭就回来。那段日子下午的比赛,因为有了之前oj contest的经验,发挥的都还可以。还有难忘那每天contest之后一群人到qzw的fb,难忘在那餐桌上热烈讨论题目的气氛。最后我意外地编进了校队三队,跟riveria和qherlyt一起,队名叫FoxTail,好高兴啊。

然后开始了组队训练,也是一个场次不多但是让我进步最多的一次训练。经过了组队训练,无论在分析问题上,队员合作上,代码能力上都有了显著的提高。这个要感谢队长riveria,带领我和qherlyt两个新手,一一传授他的知识、经验。还要感谢狗狗,为我们准备了这么一次相当正规的比赛训练,顺便感谢俄罗斯大妈的无数经典题目。组队训练结束的时候,我们三个人都觉得现在比赛简直三人如一,一人如三,呵呵。有个小插曲,第一次组队赛的时候,比赛进行中来了盒饭,然后15个人全部跑去吃饭了,谁都不管contest了-_-bbb,让做裁判的狗狗直接无语了,哈哈哈哈哈。

终于开始了梦寐以求的regional,北京和上海。两次比赛比的都不是很好,原因还是因为都太紧张了吧,开始太着急了,不过在比赛后期还是把该做的题目都做出来了,虽然罚时很多。想起来在北京,当第四个小时,ac了第四题的时候,rr望着气球说了一句:哦,总算没给学校丢脸。rr就是这样一个纯洁的孩子 8)。

很快就大三下了,qherlyt、skatou和我三个浮云保研男还是决定参加校赛了。队名取了TripleRed,不过三个人9个rating没一个是红的-_-bb,太yy了。比赛嘛,都没怎么准备过,就各自自己做了几个题目就上场了。结果两场比赛都不理想,原因很多但是主要还是实力不够,信心不足吧。不过最后还是充了不少公款,给以后的腐败活动垫下了深厚的经济基础-_-。

这学期还找到了一份好玩儿的兼职,上杭州少年宫给做竞赛的小朋友上课,是xuchuan让给我的。开始还很忧郁,觉得自己汉语表达不过关,算法功底也不够,不过后来还是接了这份活,因为相信只要自己答应下来的事情一定会去做好。第一次还是popo带我去,给我示范性地上了第一课,嘿嘿。第一节课就看出来了,小朋友的水平不是闹着玩儿的,肯定很难伺候。接下来的14个星期都拼命备课啊备课,最后还是勉强撑下来了。后来少年宫谢老师问我下学期还要不要继续讲,我一个劲儿的摇头,觉得已经实在没什么可讲的了。

少年宫讲课,没记得给他们讲过多少东西,倒是从他们身上学到了无数东东,让我收益不浅。以前在FoxTail比赛的时候,沟通一个算法rr都需要给我讲两遍,因为我都不怎么专心去听他讲,不怎么用心去思考他的算法。现在作为老师站在讲台上,当小朋友给我讲述他的思路的时候,我不得不全身心投入去听他的描述,思考他的算法。因为我必须在第一时间内给他一个答案。这个锻炼让我的大脑敏捷了不少。还有,听了不少小朋友的想法,他们的特点是思路很活跃,并不局限在题目类型或经典方法。很多异类的题目他们总能提出自己的新颖的解决方法。这对只会做做过的题,old题的我,是再好不过的锻炼了:做题是需要自己思考的。嘿嘿,当然最重要的还是结识了一帮好玩儿的小朋友^_^。

刚过省赛的一个早上,收到了jj的一封88信笺,说决定让我跟ob和popo组队作为一队去台北参加比赛。那时侯心情很复杂,因为是一种机会,也是一个责任。想了一下,回信答应了jj,也自己下了决心。

考试过去了,再搬家搬到yq已经是7月下旬了,要开始训练了。本来按照比例来说,我的瓶劲应该是做难题,不再是coding,但是考虑到新的队伍里面我该扮演的角色,不得不让我把自己的coding锻炼到极限。锻炼coding还是tc(www.topcoder.com)最有效了,然后接下来的时间每天做2个SRM practice,最后大概做了20个吧,coding无论在速度上还是准确度上有了显著的提高。还有telly给我介绍去SGU锻炼做难题,也每天去做了几道。呵呵,做了SGU,才明白什么叫准确率,因为他们的数据case不多,但是都非常有针对性,非常强,没有一个题目可以愣过去。

8月份了就没时间做自己的事情了,随机组队赛再加上出题还有导师的事情足以把我累死。组队赛的好处是比较好玩儿,比赛比较有激情,还有队员之间的沟通明显增多。不过8月份最让我难忘的还是两场uva,我们TripleRed在503用一台机器+打印机,用没人知道的qherlyt的id做比赛,而且两次结果都还可以。那个感觉就是,就是偷吃禁果的感觉嘛,哈哈哈哈哈。

实在想不出什么好的结尾,流水帐就这么结束吧。

2005年8月28日 15:00

三 竞赛有什么好处

不少人问过我,竞赛到底带来什么好处?为什么为它这么拼命?

如果你觉得,他带来的是多少多少奖状,以后会带来多少多少薪水,那我不的不要说:土!

当你跟病魔斗争,在那危险期你的最后一个心跳也许挽救了你一个生命。当你在赛场中,在那最后一秒钟的提交也许挽救了你们一个队。我想你需要的是同样的顽强。

当你在人生中面临一个选择,也许你的每一步影响着你后半人生。当你在比赛中面临题目的选择,也许你的这一选择决定整场比赛的结果。我想你面临的是同样的抉择。

当你遇到挫折,但没有气馁,认真总结经验,也许从此走上了光明。当你比赛比输了,但没有灰心,吸取教训,也许拿下了下一场比赛。我想你需要的是同样的勇气。

比赛带给了我成熟,比赛带给了快乐,比赛带给了我自信。但这一切的一切,需要一个根本的前提:要用心去喜欢它,要用心去体会它。

2005年8月28日 15:10

四 感谢

没有造物主就没有世界。首先必须感谢我们的chenyue jj,没有她,也没有我们ZJU的ACM。还要感谢FatMouse以及其他所有支持ZJU ACM的老师们,是你们建起了浙大ACM坚实的基地。

感谢狗狗,给我们指明了不少方向,肃立了不少模范。浙大目前ACM队的coding风格的根源就在于你的40个judge solution,还有那神奇无比的模块^_^。而且去年还亲自当教练,教会了我们不少东东。

感谢riveria,第一次带我参赛,让我这个新手很快融入到比赛中。感谢qherlyt,skatou,BlueriF,FishingMan,raincoat,xtlist,是你们陪我经历了大大小小的比赛,一起享受了其中的酸甜苦辣。

感谢所有参加集训的人,是你们制造了良好的集训氛围。

最后感谢我的父母亲,对我无条件的支持。8)

2005年8月28日 15:45

五 后记 by chemfrog

本篇的题目摘自88,是另一大牛collin所题。我觉得即使Sghao没有拿过金牌,他的奋斗历程也绝对值得拿一枚金牌。在zju,我发现有好多人,他们的生活环境要比我差很多,却通过更多的付出而得到本该属于他们的东西。可能世界上没有多少东西是属于自己的,所谓的本该属于也是通过自己争取才能得到。也许这是Sghao此篇给我最大的启示。

555,被8卦了

Monday, August 29th, 2005

今天突然听闻被8卦了,好在我的形象还不错。居然有人说我在浙大有gf了,严重影响了我销路T.T

集训结束后,在补习游戏。大航海还是挺好玩的嘛。不说了,打机了。

暑期集训小结

Friday, August 26th, 2005

毫无疑问,我现在写的程序和7月写的程序相比是很不一样了。这个暑期真的学了很多东西,也玩得挺开心。到了现在,倒也有点舍不得。

我们集训的形式是这样的。一开始cyjj把我们30多人分成4个营,分别为red,yellow,blue,green。每个营都有自己的小论坛,是其他营的人看不到的。四个营的组头分别是popo,telly,sghao,oldbig。我是red的,和cpcs,iceboy等人一个营,popo是我们的组头。每个营每个星期都要出一套题目,基本上就是每人出一道的样子。我当然也要出题啦。

周一是cyjj早就安排好的题目,周二~周五就是四个营的题目,除去自己营的题,每周有四场比赛。其中周一是个人赛,周二~周五是分组赛,组队完全随机,由抽扑克牌来决定,三人一队。个人赛是3小时,分组赛是4小时。周六是真人pk环节,即author点评题目。这也是对题目质量的一个保证。每天白天就是比赛,晚上要写总结。见过光的题目会放到题库里,比赛时候未过的可以再yy一把。

我的个人赛成绩比较糟糕,这是实力问题。我在分组赛中的贡献也没多少,属于打杂类。如果和牛人在一队,我就无所事事,如果和和我差不多的人在一队,我们基本上就要垫底的样子。不过到后期,这种情况有点改观,我还是会进步的嘛^_^

其实具体到每天的生活还是挺单调的。每个星期的头几天都在想着怎么出题,要知道出题可是多么累人。当然,出简单题、秒杀题就不要怎么动脑子,但这样多没意思。但出题要写标程,也就是说出的题起码要自己会做。以我的水平要出一道有点质量的题目真的是不容易,可以说,我所出的那几道都是到了我的能力上限的难度了。一般来说,我出道题要花三四天晚上的时间。所以我是不大可能把当天比赛不会做的题目全弄懂的,最多只能在论坛上知道个大概。我觉得这样挺可惜的,浪费了很多提高的好机会。但另一方面,我每出一道题目都感觉到自己在提高。当然,我写的标程还是比较土的,经常被鄙视,然后重写。。。

cyjj从见面的第一天就建议我们去参加TC,即topcoder的比赛。这是一个国际性的网上比赛,每隔几天就会有一场srm(single round match),另外还有比较大型一点的比赛,如TCO(topcoder open),前几天还有一场google jam,我的理解是google联合tc搞得一场比赛。像这种大比赛是有奖金的,很多zju的同学都抓到过米,我知道有拿到1000 dollar的,其实拿几十美金的也很不容易啊,反正我第一轮就被淘汰了。。。不过与前几场srm相比,我的stl显然熟练了一点,也可以说入门了。

说到stl,真是汗啊。我一开始是挺抗拒的,因为没学过c++,觉得门槛太高了。然后就发现有的时候用起来还是挺爽的,尤其是在TC下不用不行(TC居然没有c,只有c++ -_-bbb)。然后就是现在半桶水,不懂装懂,边查边用的状态。我也在说服自己,写程序不是为了acm,也是为了将来。像string,只能用cin cout,但在acm的比赛中(高层次的比赛不算,我没有机会到那个层次),cin cout要比scanf printf吃亏。但string 有很多很灵活的用法,我觉得以后用string代替char []是一种趋势,vector代替数组也是一种趋势,应该多用新的东西。

另一个从无到有的东西是模块。尽管久仰gougou模块的威名,但一直都没有用过。很多问题就是因为未用过而不会用,用了一次之后,知道怎么用了,以后就方便很多了。我对模块还不是很熟悉,要一字一句读明白又不大可能。其实我觉得最好弄一套例子,对模块的每个程序都作个说明,避免像上次调错函数那样的搞笑情况的再次出现。

这段时间,进步最明显的是bfs。现在基本上看见bfs都敢写。递归也没有以前抗拒了,写写也能写对。dp还是很弱,但很多时候都有思路了,只是写不出来-_-bbb 但分组赛的时候,给会写的人讲清楚就行了。我觉得自己图论比较差,有个原因是当年数据结构没有将图论讲得很清楚,要再好好看一下。还有一个进步可能是看不见的,就是阅读理解。我英语本来比较菜,突然发现集训队里面的人有很多英语也不怎么样。然后才知道这是acm战队的一个通病。aoao,英语可以的话还是再提高一点吧。

怎么说呢,集训已经到了尾声,要准备进入新学期的学习状态。今天开始放自己假,啦啦。

今天还不错

Monday, August 15th, 2005

还好,没有光头。成功抢到了最后一个AC。呵呵。

转眼间已经过了半个月,STL已经敢用 map 和 queue,对 string 还是有点戒心。开始看模块,起码知道模块讲什么,怎么用吧。bfs依然是我最犀利的武器,而递归也进步了不少,看来脑子开始开窍了。DP怎么了,我知道难,难就不做了吗?不是还有一些jj出的题目是只有我一个人过的吗?

yy是一辈子的事

Sunday, August 14th, 2005

yy,对于我而言,指思考、幻想,又不仅仅如此。yy是种探索精神,想到别人没想到的东西,做大家都能做却都没有做的东西,这能给我带来很大的满足感。只要还有idea,就还有活力,我就还能战斗,哈哈^_^

没有信心,没有士气

Tuesday, August 9th, 2005

尽力了,但还是光头。。。

发现自己这段时间真的受了比较大的打击,人好down,做题都兴奋不起来,好容易就会放弃。

今晚好唔开心,想什么都不干,觉得好无聊。唔开心的时候就会想起她。虽然她不可能是让我变成王子的那个人,但她还是能够给我带来能量的。想想就够了,好快,我又从崩溃的边缘回来了。\^^/

不许哭

Monday, August 8th, 2005

今天真的很失败,30几人的比赛,29人提交过,25人AC过,但是我,无提交。。。

虽然我3个钟头都在努力,但最终都不能摆脱光头的命运。没有办法啦,一题都唔识,sample都过不了,交什么交。

在最后的15min,有崩溃的感觉。我并不是这么容易就放弃的人,但越是这样越是心酸,干脆就不做了。

晚上,题目已经转到了题库,可以继续提交。当然了,成绩就只算比赛时候的。我好不容易敲了个能够过sample的程序,就在那里交啊交,就是不过。想哭。。。发现这种感觉是如此的似曾相识。记得上次我是对自己说:“不许哭,等我**了之后,我答应让你痛痛快快的哭一场。”

对,不许哭。

熬过了一个星期

Sunday, August 7th, 2005

其实就唔是我懒罗,实在太忙,太累。

发现自己真是太差劲,问题太多。当然,在这个星期里,我的进步也是好明显的。不想讲太多细节,费事被人PK。

all in all: 我没有放弃,我一直在努力,因为我相信,这会成为我美好的回忆。