[我的ACM之路] 走向成熟

又一年过去,ywy研三了,逐渐繁忙的毕业设计和就业压力使他关心集训队的时间减少,计划中的选拔赛一拖再拖,最终只好取消了,集训队来者不拒。这一年,zyy研二、wl和ywq毕业,不过lj考研成功,使集训队补充了强悍的新鲜血液。这一年Larva进入集训队,并且固执的他们要求一起组队参赛,ywy最终还是没有说服他们分开……

由于学工办不同意集训冲掉军训,于是集训被安排在了8月份。大家还是开心得做着题,讨论着算法。jackie为集训队供献了一个代码交流平台,不过由于时间关系,集训结束之前,这个平台的功能还仅限于统计各人的题量。由于Larva三人都是用Java的,所以集训题库选择了POJ的两卷。那时候我开始学着用C++,因为Java实在太恶心了,Collections Framework和STL没法比。

集训结束之前,ywy安排了4场个人赛,用于做分队的参考。前三场都是简单题,我的成绩基本和当年leojay一样的,第一场2个多小时切掉所有题,后面几场,因为ywy限制了提交次数,我用完了限制,虽然没做完,但仍然排在第一。最后一场比较挫,做到一半POJ挂掉了,我们只好把代码先交到ywy那里,等POJ恢复了验证。由连着比赛压力比较大,我最后一场发挥失常……

新的ICPC赛季,我、jackie和lj组队,参加成都和Coimbatore的比赛。前一年上海和韩国的比赛时间不理想,由于国内的题目难度普遍高于国外,所以选择国内的赛场做为热身是不错的选择,而上海的时间在韩国之后,失去了热身的效果。而成都的时间在Coimbatore之前,这个安排很合理,但是,人算不如天算……

10月份去成都,切掉两道题,貌似做出3道就能排前5,而我们反应比较慢,只落了一个铜牌……

接下来去印度,去之前我们充分总结了成都的经验,并且突击了一下,我在POJ的排名跃升到历史最高点——23位。本以为去印度的强队不多,可以拿个好成绩回来,却没想到主办方的表现实在差强人意。上手一道大数的题目,我在比赛开始之前就敲完了,然后提交,Judge一小时没有工作,一小时之后,判了一个RTE给我,百思不得其解,然后同样的代码再交一次,CE,顿时没有想法了,后来改了一下输入方法,AC了。事后想想,一开始的RTE,如果是输入方式造成的,那Judge的数据格式应该有问题,而CE则肯定是Judge不懂Java=.=。另一道题,在比赛开始后不久也敲完了,等了一个多小时之后,得到一个WA,改了之后AC了。Judge一小时不判题,造成了我们队巨大的时间劣势,最后只排名20位左右,非常地郁闷。

从印度回来之后,jackie退役了,lj研二,接下了ywy教练的位子。集训队里参加过比赛的,只剩下我和Larva三人,下一年的参赛形势瞬间变得严峻起来……

那一年的程序设计联赛,ywy把裁判的工作交给了我、jackie和lj,而联赛则变成了Larva分奖品的舞台。为联赛出题是一件很有意思的事情,要让题目难度有层次,所考察的算法覆盖面广,题意看上去能吸引人。按照ywy的说法,一套题目能成为好题目,那么在比赛中每个队伍都至少AC一题,并且至少有一道题没有队AC。如果在比赛中有一支队伍AC了全部的题目,那命题人就比较坍台了。找一道没有人做得出的题目很简单,比如复杂的模拟题,或者有很深背景的论文题,基本都可以拦住所有的队。然后找一道所有人都能做出的题就不是这么容易了。联赛到现在已经是第4届了,从来都没有一道题能被所有的人做出,而在大陆的所有ACM赛场上也没出现过有一道题被所有队做出的情况。估计按这个形势,A+B是趋势=.=

最终Larva的某人(忘了是谁)拿了联赛冠军,成功抢到了一个DVD刻录机,比我当年第一名的Combo好多了,唉,感叹时代的进步……

[我的ACM之路] 奋发图强

经历了完美的大一之后,新一年的集训队选拔开始了。6月底的时候,ywy组织了选拔赛,所有想进ACM队的人,不论资历,都要参加。我本来以为可以在选拔赛拿个好名次的,没想到题目很难,当时只做出了一道,Joseph问题,其它的题目都没什么想法,不过后来ywy貌似没公开题目,我也没去问。那次比赛排在了2X名,还好ywy让我进了集训队。

集训的生活很爽的,一天8小时有空调,想想同一时间,其它的同学在军训,真是幸福。那次集训冲掉了军训,使得后一年有很多小青年慕名而来,却没想到军训免不掉,非常尴尬。

那一年leojay和ywy退役了,leojay没考研,直接毕业走了,集训的时候来过几次,后来就没怎么看到过了,我和他的唯一一次较量是在一年前的选拔赛上,不过没看到过他敲代码,比较遗憾。ywy做了教练,一直负责ACM训练到他毕业,看过他写代码,不过不是在比赛中……剩下来最牛的应该是zyy了,为此集训的时候我专业坐在了他旁边,吸取一点高人的精华。当时zyy在读研一,据说是要做项目,集训后期来的比较少。集训的题库是当时UVA最新的两卷(具体哪两卷忘了),由于zyy要做项目,所以集训就变成了我和wl飙题,整个集训30多天,我做了50几题,虽然不多,但是收获很大。每天很多人在一起,有什么问题随时都可以讨论,别人犯了什么错误可以立即吸取经验。那时候的我还停留在搜索和图论基础算法上,看到zyy的某个双向广搜就仰慕不已了。

集训结束,9月底的时候,收到ywy的邮件,我被安排和jackie、zyy一队,去韩国比赛。ywy的意图是想煅练新人,我和jackie都是第一次参赛,这种组合有点冒险,但是效果很好。

在去韩国之前,第二届程序设计联赛秋季赛举行,很不幸的是那次有两题的题意没看懂,最后排名比较差。

然后就去了韩国比赛,比赛成绩非常理想,ICPC第10名,SHU近几年的最好成绩了。那次比赛的B题数据错了,我由于漏看了一句话,没注意到是数据错,反而加了判断之后在比赛时间内AC了,不过也浪费了很多时间。另外C题是简单的DFS,我抢过来用DP做,一直没调成功,后来zyy用DFS重写了一遍就AC了,这期间也浪费了比较多的时间。后来一直做出4题,如果C直接让zyy做的话,说不定能做出更多的题,不过这个成绩还是让ywy非常满意。

从韩国回来之后,过一个多月又去参加了上海参区的比赛。成绩非常不理想=.=,只AC了一题。那一题是一个记数问题,yl调了很久才AC的。另外有一题贪心,一直WA到了比赛结束。后来我重新做过那套题目,发现还有2题是可以做的,只是当时没时间也没发现。这引出了一个问题:当比赛中有一道题一直WA,怎么处理?比较客观的方法是设定一个时限,超过时限没AC就换题,不过这个在比赛中很难完全遵守,做题目的时候总有种心理,要把这题做出来,再换题。以至于换题的过程比较缓慢。06年上海赛区,larva在比赛结束后和我说,ACRush是这么处理的,一道题目WA三次就换,不管离正确答案有多接近。当然每一个队都有自己的做法,只要能在比赛中AC更多的题,每个做法都是好的。

在交大比完赛回来之后,我收到了三门课不及格的试读警告,在大一一门未挂,还能混的奖学金的我,瞬间变成了成绩倒数的小混混。不过总结一下,在韩国拿了好成绩,所以其它事情上RP比较差,比如联赛没看懂题、上海赛区没排上名次、连挂三门,根据RP守衡定律,我也认了……

又一个ICPC年结束了,那一年SJTU拿了冠军……

大二的剩下时间里,还有两次联赛,一次第一,一次第二,不过由于秋季赛的成绩太差,总分没超过ywq,只能饮恨拿了联赛第二,郁闷……

大二期间一直持续在POJ做题,暑假之前已经冲进了第一版(记得是这样,或者是离第一版很接近)。

如果说大一是RP好,那么大二的成功有一部分应该归结为实力。想对于大一什么都不懂来说,大二的话至少对整个算法体系有所了解,对今后的发展有了一定计划。

[我的ACM之路] 初生牛犊

在进大学以前,奥林匹克这个词对我来说,一直是只有神才能参与的运动,诸如各类数学、物理、化学竞赛,我从来都是敬而远之。但是出于天生的好胜心,我也参加过一些比赛,当然都是二流的,不值得一提。

高中毕业的那个暑假,在编程方面,我也只懂一点VB和Pascal。那时候我意识到,需要学一点什么,否则跟不上时代的发展。于是看了Java和C#,这两个语言很相似,从初学者的角度来说基本没什么不同。暑假两个月很短,对Java也只能粗通皮毛而已。

刚进大学一个月左右,在寝室楼门口看到一张告示,说是有一个程序设计竞赛,可以使用Java。当时对Java非常有热情,也对竞赛很有好奇心,于是就报了名。那时候还只是Java 1.4,io很麻烦,我基本不懂怎么从控制台输入,心想比赛之前裁判可能会教一下新人,于是这件事也就没放在心上。

比赛那天,带了两本Java的书就上路了,其中一本里面有讲到标准输入,是一个很烦的方法,手工从System.in读入字符再处理的。好在那个方法可以正常运行,要不然我的处女赛就要以0分结束了。

当时的比赛设在行健楼6楼机房,进去之后随便找了一台机器坐下,等裁判讲关于输入的事情。裁判说了一大堆比赛规则和PC^2使用之类的东西,就是只字不提Java的输入,然后我就开始慌了,翻书敲代码。然后得知我是那场比赛中唯一一个用Java的,寒啊……那段输入的代码敲完之后,看到热身的题是A+B,发现还要再写一个分割输入的方法,于是继续郁闷地写。写到一半的时候,裁判跑来和我说,你有没有交过热身题,我说没有,他说最好交一下,测试一下PC^2,我不好意思说我不还没搞定输入,就把当时可以正常运行的代码交上去,结果自然是WA。

等到分割方法基本写完的时候,正式比赛开始了。一共10道题,在现在看来都是简单题,那时候以为都是难题,就一道一道往下做,不知道能做掉几题,也不知道其它选手能做掉几题。比赛一共4小时,过了2个多小时的时候,裁判跑出来说,已经有人全部做完了。当时那个寒啊,这么牛的人,神啊……比赛中还有一个小细节,有一道题要求输出YES或者NO,我懒,写了Yes或者No,以为裁判会手工判,这样的输出在正规比赛肯定是WA的,但是裁判给了我一个Output Format Error,还特地跑出来和大家说了一下,输出格式一定要完全按照题目中描述的,一点都不能错。这是当时比较感谢裁判的一点,要不然那道题我怎么也不会过了。

比赛结束,一共切掉4题,本来以为是比较差的成绩,然后瞄了一眼排名,发现自己大约能进前10,寒啊……然后裁判说有什么事再等通知,大家可以回去了。

那次比赛之后1个月左右。收到了裁判的电话,说是要去延长开会,也不知道是什么事,就过去了。在那里见到了当时的大牛们。刚到开会地点的时候,看到了裁判,也就是ywy,出于尊敬叫了一声“老师”,然后想想不太对,这么年轻的老师?后来xwm老师介绍的时候,才知道ywy也是学生,还要代表学校参赛,也是一个牛人。在那里也认识了leojay,就是那次比赛切完全部题的人,估计是当时SHU最出名的ACMer了吧,在ZOJ上排在第一版。还有很多牛人,只见了一面,基本不记得名字。在那次开会中,我第一次知道ACM/ICPC这个名词,而那次比赛实际上是集训队的选拔赛,本来选拔赛应该是放在6月份,而03年刚好非典,选拔赛被拖到了9份底。那次开会决定派我跟一支队去北京当替补,刚进大学就有免费旅游的机会,非常幸福^_^。会议结束之后,我问了leojay哪里可以做题目,他向我介绍了ZOJ,于是后来的一段时间里我经常去ZOJ做题。

又过了约一个月,我跟着hl、wl、ywq去北京比赛。在场外看比赛的确是一件比较无聊的事情,特别是所关注的队伍迟迟不能升气球。那次比赛中的最后一题,是一个大数乘法,应该是当时最简单的一道题了吧,我在那里想如果我能上场该多好,第一次出赛就能拿个铜牌回来。当时他们3个多小时才过了那题,比较尴尬。

那次去北京一周左右,我就荒废了一周的高数课,正好是积分的开头,导致后来高数基本没好好学,这和ACM无关,暂且不提。

那一年的ACM赛事就这么结束了,我又回到了正常的学习生活之中。

后来我一直在ZOJ上做题,ZOJ不支持Java,这点我非常不爽。当时我C++基本不会,string的操作都要翻半天书,而且发现status里面排在前列的都是Pascal的提交,于是拿起Pascal的书,开始复习……这段时间算是走了个弯路,花了很多时间在语言的学习上面,算法一点都没有进步,直到我发现了有一个叫POJ的网站。

在发现POJ支持Java之后,我就坚定不移地去POJ做题。那段时光是非常快乐的,当时因为寝室不能上网,做题只能等到周末回家。于是在家的2天时间,成了我题量上升的主要机会。每次周五上完课,冲回家上POJ的期待,都是非常美好的。

纪念一下在POJ的首次提交:

72241 FinalLaugh 1000 Compile Error Java 430B 2003-12-06 17:18:02

后来在1月份左右的时候,zz举办了一次程序设计比赛,类型和ACM/ICPC相同,三个人一台机器,而且要求必须有女生。只是zz当时不了解ACM的计分规则,所以用了OI的计分规则,也就是过一个Case给一定的分数。我当时找了同班的一个牛人spacey,和一个女生,去参赛。成绩非常理想,顺利拿了第一名。大家开开心心地回去了……

大一快结束的5月份,zz成功举办了SHU历史上第一届程序设计联赛,并且在他的努力下,程序设计联赛一直举办到现在,为SHU ACM的氛围提供了良好的支持。感谢zz。在那次比赛中,我也顺利得拿到第一,幸运女神貌似总是站在我这一边,整个大一的经历基本可以算是神话了。

10.21上海赛区预选赛小结

由于事先被通知说本校的队伍不能参加本校的比赛,于是这场比赛我就成了看客。

一共8道题:

balls,我没想到可以用二分匹配解,更不知道最小路径覆盖为何物=.=,后来google一下,才知道解法,惭愧惭愧。

communication,有点复杂的立体几何题,实在不高兴自己推了,跳过=.=

even or odd,一看数据规模,就知道要用至多O(n)的解法,然后根据八数码问题的解法,猜想可能和置换群有关,然后就做出来了。不过这题被卡了MLE,我用C和C++多个版本的代码提交,不是WA就是MLE,很郁闷。

firing,线段树,不过题目里li、ri和m的关系很奇妙,看了半天没看懂具体内容,跳过=.=

lazy,简单题,POJ上有类似的题目,从大的开始乘,小的开始除,保证不会除不尽。

msn,先要用线段树计算在线时间,然后贪心求最优解,不过貌似要用最优匹配,但是我用贪心做出来的解和数据一样^_^

travel,完全不知道解法……

walk,镜面反射问题,貌似POJ上也有类似的题,反正我也做不出=.=

总体而言,正常比赛的情况下,做出4题是正常的,比赛结果也是如此,除去相同的学校,做出4题的学校应该能晋级。

不过服务器的问题一直困扰着所有的人……

其实OpenJudge(因为设想要开源,所以把Online改成了Open)的设计理念是很好的,它把数据库、用户界面、判题程序分开,只要数据库不崩溃,其它两部分的问题就可以用机器换性能的方法解决。但是这次时间仓促,比赛用的域名是一周前才刚刚申请到的,而路由的部分是其它部门管理的,所以用多台服务器做用户界面有点困难,而这也就成了所有问题的起因=.=

在网络赛中最重要的是减少每个用户的流量,一个用户少用了流量,就可以把这部分流量分配给其它用户。于是便想到了Ajax,只需要下载一些关键数据就可以完成客户端的刷新。不过貌似gwt编译出来的文件,有比较大的性能问题。比赛刚开始的时候,服务器完全失去响应,当然这也是Ajax的弊端,用户需要先下载至少50K的数据,才能打开初始页面。而服务器端的Java程序,不知道是什么问题,不能应付大量的数据库查询,而当时数据库里几乎还没有数据,令人费解。而且那个Ajax程序的统计也有问题,在Statistics页面里,C/C++/Java的提交数量之和>Total的数量,很神奇的现象=.=

比赛就在一片骂声之中过了2个多小时,这时候Larva小组奇迹般地用php重写了用户界面,一下子扭转了局面。最初是Status,后来又补上了Ranklist和Submit,php的性能比Java高出不少,从此Ajax就被冷落了。我也就是在这时候开始交C,反反复复的MLE和WA,无语=.=然后几个牛校就开始争相爬头,最后有5个学校完成所有题目,令人仰慕……

虽然一开始出了一些问题,但是Larva的反应速度还是可圈可点的,逃脱了和THU相提并论的下场=.=……

接下去就要看西安那边的状况了,大家拭目以待吧……

8/14 ZOJ 比赛小结

12:50 到场,和xhz讨论了一下策略,这次比赛只有3小时,预计题量在6道左右,而且名称为“Kill in Seconds”,想必难度不大,于是约定我从头、xhz从尾开始看,先看内容短的,看到简单题就丢给我做。

比赛开始后,xhz很快发现1007非常简单,他叙述了一下题意之后,我立刻开始敲代码,由于容器选择不合理,浪费了一点时间,在13分钟时1Y。然后xhz和我说了一下1008的题意,讨论下来觉得题意不明确,暂时放着。然后看到1003很短,看了一下题目,最优解问题,数据规模10000,肯定是贪心,很快讨论出了算法,可惜第一次少打了个“=”,贡献了一次WA,32分钟时2Y。过这题的时候,xhz已经看完N道了,只能用一台机器真是不爽T_T。接下去很快又过了1004,49分钟时1Y。

接下去开始敲1005,由于牵涉到对称,即除2和+1 -1的问题,我就头大了,代码调了蛮长时间才过sample,但是交了几次都是WA,没想通哪里错了,然后让xhz开始写1001,一道模拟题,除了坐标设定要仔细看之外,没什么难点。后来我把1005中判断的代码重写,糊里糊涂得就过了,2小时4分钟6Y。然后xhz继续写1001,由于重名变量问题一直没过sample,调了很久才发现,然后1Y。这时候已经是2小时37分了,剩下1002:题意不明确,当时还没有人过;1006:一道算法很简单,输入很复杂的题,20分钟内肯定写不完;1008,暂时没搞清算法。于是最后20分钟成为垃圾时间……

这次比赛前期发挥还算正常,只是出1005的速度太慢了,后来回忆时想到是if后面少加{}了,导致浪费了半个多小时,要不然可能可以写完1006。最终排名是36,还算满意。