[我的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相提并论的下场=.=……

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

Pick's Theorem

今天做到某题(POJ 2954),题意是求一个顶点坐标均为整数的三角型内整数点的个数,不含三角型边上的整数点。

Pick's Theorem,大意是:任何平面上顶点坐标均为整数的简单多边形,满足以下公式:

A = I + B / 2 - 1

A是多边形的面积,I是多边形内的整数点的个数,B是多边形边上整数点的个数。

Pick's Theorem可以推广到多维的情况,见:Ehrhart polynomials

理论和题目配合得相当完美……汗啊……

TopCoder Marathon Match 4

题目改编自己经典游戏Battleship,原版的游戏是给出一个n*m的方格阵,里面有k条船,每条船的宽度都是1但长度不一,方向要么横着(纵坐标相同)要么竖着(横坐标相同),玩家每回合选择一个点丢炸弹,系统返回炸到与否。这道题目改了一些条件:给出一个n*n的方格阵,每次可以丢x个炸弹,系统返回炸到了哪些船和每条船炸到几个点,但不告之是哪些炸弹炸到的。要求程序在尽可能短的回合内,炸完所有的船。

看到题目,最初的想法是完全随机投点,这样做的好处是:1、使自己有个分数先,0分太难看了;2、这个算法保证能在规定时间内结束,可以用来测试程序的完整性和对题目理解的正确性。迅速写完之后提交,出乎意料拿了30多分(满分100),看来完全随机的效率还不错。

然后开始改进程序,虽然系统不返回哪个炸弹炸到了船,但是只要有船被炸到,那一回合的炸弹附近必然有船,下一回合就先炸那附近的点。这么一改,得分反而下降了,郁闷=.=,分析原因,可能是下一回合选取点的优先顺序问题,因为有多种情况可以估算可能有船的点,不同的if顺序就会导致程序效率的明显差别,于是继续改。

再然后就想到了给每个点都设一个可能度的值,每一轮炸完之后,都对相应的点的可能度进行评估,然后选出可能度最高的几个点进入下一轮。评估的条件有,如果一个点炸到了船,则它周围的四个点可能度提升;如果两个点炸到了船并且它们在一条直线上距离小于那条船的长度,则它们所在直线上相应点的可能度提升;如果一个点没有炸到船,则它周围点的可能度下降(这一条有争议,多次试验下来效果不好)。这样一改,分数一下子上到了50多分,效果非常好。

但是最高分有90多分,怎样继续优化是一个问题。这时我的程序已经分为2部分,一部分是初始化时,点的顺序,因为最初的几回合,可以获得的信息比较少,但这几回合非常关键,怎么安排最初炸的点是要好好考虑的;另一部分是怎样利用已知信息,计算点的可能度。这2部分的优化都很伤脑筋,而我的分数一直在50分左右徘徊,很郁闷。

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,还算满意。