注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

转来自己看 恩恩  

2009-09-29 12:53:15|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转:2009年ACM-ICPC全球总决赛——瑞典(楼天城*超神)

2009-05-22 12:16

作者:楼天城

人称:楼教主(个人称呼楼主)

OJ惯用昵称:ACRush

大学:清华大学

2009年ACM-ICPC全球总决赛:以9道题目,在与第一名ac相同题目数,因罚时上森彼得森堡大学少于清华大学,屈居第二

抵达瑞典的当天晚上,我们就体会到了北欧的高纬度特色,晚上十点钟时天空仍然是亮的,据当地人说,到了夏至日前后,每天太阳只落山3个小时左右。

         瑞典之旅的前两天以游玩为主,练习赛(试机)安排在第三天,练习赛前,我们深刻体会到了瑞典的第二个特点——冷。赛会要求所有选手身穿ICPC的t-shirt参加比赛,并且还强制要求最外面的一件衣服是ICPC的t-shirt。Bill大叔一如既往地热情,在露天广场讲演了30分钟,不过在近似0度的室外,虽然t-shirt内套有毛衣,但是也很难抵挡刺骨的寒风。

         练习赛过程中,我们比较低调(也可以认为是低靡),最简单的题目A在最后时刻才AC(记得后一天,一名外国选手还特地关于此事对我们表示担心,我们其实是想留下一道题目来测试)。参加这么多场ACM以来,我对练习赛有如下几点体会:

(1)     练习赛的最重要的作用——试机

练习赛往往使用特别简单的题目,选手可以选择比拼手速,看看能否排在前列。记得MobileRobot成功在东京总决赛前的练习赛排在第一;也可以不着急做题目,先花一些时间适应比赛机器环境。

(2)     练习赛中可以测试Judge的习惯

比如我们发现此次Final测试中Wrong Answer的优先级比Run Time Error高一些,不知道有没有其他队伍注意到,:P。

(3)     练习赛中可以测试一些重要参数

比如今年就有两个发现,首先,提交系统中的编译指令没有添加-O2优化;其次,提交系统的C语言运行堆栈大小是8MB。

         无论是出发前,还是在瑞典,许多同学和老师都看好Proxima,谢谢大家的关心。但是直到赛前,我们的精神状态都没有调整到最好。我由于赛前参加TopCoder个人比赛投入了大量精力,略微影响了组队比赛的感觉。另外,zzy比赛前一周精神状态也不是很好,至少我能感觉得到。

         不过,赛前晚上我们休息得很好,比赛在上午10点左右拉开序幕。下面分享一下比赛的过程吧。

         13分钟,A:二分答案,然后枚举或者动态规划。1Y

         A题虽然n的范围只有8,但是如果枚举8!=40320种情况的话还是时间略微有一些紧,所以我们使用了比较稳妥的动态规划方法,这样计算量只有2^8=256。

         A成功1Y之后排在第4,当时看来起步很顺利。

         尝试了2次E,结果都是WA。

         我们都没有想到一场悲剧已经拉开序幕。E题是此次总决赛之旅的最大败笔,这个第二个开始写的题目结果是倒数第二个通过的。

         103分钟,B:枚举错误的门,通过逻辑计算判断是否满足。3Y

         这题是zzy写的,主要是由于题目很琐碎,而且我被E卡住了。在过了A后的长达100分钟左右的时间中我一直在E中苦苦挣扎,可见当时的状态真的很差。

         114分钟,F:计算几何。2Y

         这题是zzy写的,至于出错一次的原因我也不很清楚。

         121分钟,D:计算几何,判断包含4个圆的最小圆。1Y

         其实我在此次总决赛过程中,除了E题之外都挺顺利的,D题其实有很简单的算法,远比Petr提出的方法简单,至少可以从7分钟写完就可以看出来,大家自己想一下吧,:P。

         至于开D题,有一个很扯淡的原因,当时zhouyuan起身看气球的情况,发现粉色气球很多,于是他回头看了一下气球颜色和题号的对照表,便告诉我D题有很多队通过,于是我毫不犹豫就做了。结果7分钟后1Y了,志愿者送来了一只颜色很神奇的气球,太赞了!

         短暂的20分钟通过3题之后,排名已经好看了许多,好象是第3吧?但是E的阴影仍在继续,并且望不到边际。

         重写E,尝试了4次E,结果都是WA。

         其实,我们并不是面对卡题的情况而慌乱,当时我果断重写了E题,程序结构已经非常清楚了,但是仍然WA。于是,我写了一个测试程序来测试E题,但是还是找不到错误。这确实是我没有遇到过的问题,我不能想象一个能通过1000组随机数据的程序提交之后的结果会是WA。于是我直接把checker放在程序里,提交之后还是错误的。

         尝试了3次C,结果都是WA。

         C题其实就是一群公式的组合,当天zzy做这种琐碎题目的状态还是不错的。不过前几次提交他漏掉了几种情况。

         实现了J的开头,由于信心不足,没有写下去。

         这件事情是很值得一提的,J题其实不是很难,只是当时E题有些苦,所以表现出信心不足。此时比赛时间大概是200分钟,我们一共卡住了2题,并且都已经陷入其中。经验告诉我们,应该开新题了,就是很多队都通过了的H题和I题。

         209分钟,H:经典2-SAT问题。2Y

         H题算法很清楚,只要看到那个more than half就可以了。我仍然延续着除E题之外的好状态,大概前前后后用了10分钟就写完了H。至于为什么WA一次,原因已经不是很重要,当时我们的罚时已经大到不在意几次错误提交了。

         238分钟,I:模拟和数学题。1Y

         I题是挺复杂的模拟题,需要一点数学知识。由于I题比较复杂,写程序过程中我有些着急,但是越着急越影响速度。现在回想起来,写I题是很重要的阶段,如果I再出任何问题,则THU此次总决赛能否获得奖牌都很难说,可以说后果不堪设想。现在还清晰记得zhouyuan每过几分钟就要提醒我一下“别着急,还有很多时间”,他当时的冷静对队伍来说很重要。

         I题在封版前2分钟1Y,也随即拉开了Proxima反攻的序幕,不过确实有些晚了。

         246分钟,C:计算正八面体表面两点最短路径,分16中情况考虑。5Y

         当时我和zhouyuan正在讨论K的算法,当算法基本清楚之后,zzy突然大叫一声Yes通过了重要C题。C题的通过在当时看来很提升士气。于是我们马上做了如下分工,我实现K题的程序;zzy读E的题目描述和代码,由于zzy之前没有看过E题,所以让他重新读题可以有效防止ZSU类似的读错题的情况发生;zhouyuan先与zzy讨论E题,然后出K的数据。

         当时我们通过了7题,还有50分钟时间。在封版时,我们看过board,只有领先的ITMO通过了7题,其实只要过几分钟再刷一下board的话,就可以发现他们通过8题了,但真正致命的是,ITMO是没有过H的8题,也就是说可以认为他们已经通过了9题。

         实现K,由于没有用long long,WA了一次。

         写完K之后,我们其实是抱着试探的心态提交的,当时大概是265分钟,对于这个WA,大家没有表现任何沮丧,可能已经有些麻木了吧。不过当时达成共识的是,K的算法一定没有错,这种决心在最后时刻对一个队伍来说是很重要的。当时我们可以这样认为,也必须有这样的信心。

         270分钟,E:图论问题。7Y

         zzy读我E题的代码过程中,对某一个地方的细节表示质疑,其实他并没有发现错误。不过我脑海突然闪过了一个重要信息,发现我预处理过程中有一个地方少考虑了一种情况,修改只有提交就Yes了。

         E题的算法,其实在第一次提交的时候就已经是基本正确的了。但是至于测试程序还有checker都不能发现错误的原因是,checker和主程序使用了相同的预处理过程,而这个预处理过程写错了,而且重写前后这段处理犯了相同的错误。贯穿全场的悲剧终于结束了,但我们当时已经无力回天了。估计一下,E大概占用了120分钟时间,回想两年前同样失手与E题。

         276分钟,K:字符串问题,可以转化为动态规划和最短路问题。2Y

         K题是一道很不错的算法题,起初我们认为这题是NP-Hard的,于是想写一个BFS,不过由于E题的悲剧就忘记了。后来因祸得福,想到了正确的动态规划方法,不过当时心中还不完全确定它是正确的。不过当时zhouyuan给出了一个需要3^34步的数据,我先没有想long long的范围是否足够就改了后提交了。提交之后,我起身去厕所。5分钟后返回时,他们告知我K题过了,当时还有19分钟。

         在实现复杂的I题的时候(230分钟左右),我们肯定都没有想到最终能够达到9题之多,而且最后还有19分钟剩余。

         用随机算法尝试J,没有通过

         虽然只有19分钟,我们并没有放弃比赛,无奈之下我使用了随机算法尝试J题,不过奇迹没有发生。J题其实不是很难,算法的关键部分我们都想到了,只是由于前面E和C两题卡得实在太惨了,实在没有时间写了,如果能够多出15分钟应该足够了,或者说,对于世界冠军队来说,35分钟足够通过J题。

         记得比赛结束之后,我跑去问ITMO通过了几题,在听到“NINE”的回答之后,我已经明白自己只能接受两次亚军的命运了。我们由于卡在前期,所以罚时上是没有办法和他们比拼的。今年显示排名的方法很刺激,THU的那条bar很坚挺,不过还是没能笑到最后。

         最终,SPB ITMO同样通过9题,以罚时优势排在第一,我们又一次位居次席。纵观整场比赛,比赛中前期我们由于E题和C题耽误了太多的时间,其它题目总体情况都比较顺利。对于E题的严重失误,我应该承担主要责任,在这里向Proxima和所有关心我们的同学深表歉意。

         赛后碰到复旦的吴永辉老师,他安慰我说,“这也许就是宿命”。其实,无论是赛前还是现在,我都不承认宿命的说法。其实我们完全有能力改变结果,即使在最后一刻。不过,吴永辉老师确实很了解当时我们的心情,如果最终没有做出9题,比如结果是8题排在第4,可能内心中都不会有如此的遗憾。通过9题是ACM总决赛以来之最,至少我们是“历届ACM总决赛过题最多的队伍之一”(一共有3支队伍做到过9题,除了今年的ITMO和THU之外,只有2003年巅峰时期的tomek领军的Warsaw University也通过了9题)。直到现在我们仍然难以接受通过9题而不能夺冠的事实。确实ITMO在中期的状态太好了,引用邬老师赛前的话“夺冠需要一些运气”。

         记得晚餐时碰到了Petr,他见面就直接伸出两个手指,并表示我们的ACM成绩已经完全一样了(Petr曾经在2003年和2005年两次获得ACM总决赛亚军)。我们的总决赛经历惊人得相似,包括两次总决赛都相隔2年,甚至连第一次都被Warsaw University击败都一样。

         2009-ACM/ICPC瑞典总决赛之后,我的ICPC生涯已经彻底结束了。在网络上,许多同学经常问我如下一个问题,其实这个问题都很难有固定的答案,我只是根据自己的经历列举一下自己的体会。

         ACM团队比赛与TopCoder个人赛事相比,对个人能力提出哪些特别的要求?

         首先,我个人认为虽然ACM比赛由3人组成,但是至少应该有1名选手具有很强的个人能力,比较理想情况应该有2名选手能够做到独当一面。

         其次,3名选手对相互之间的代码风格要非常了解。在这一点上与TopCoder中的Challenge能力有些相似,相比之下ACM对此要求还高一些。

         再次,ACM比赛使用在线评测,要求选手能够对于提交的时机有正确的把握。究竟是选择早提交以提高速度,还是谨慎提交以减少罚时,一直是众多队伍需要权衡的重要问题。

         比赛结束后回到清华的几天中,我一直在思考一个问题,Tsinghua(THU)和ITMO等欧洲传统强队最大的差距是什么?

         对此问题,我想直截了当地指出THU问题的所在。THU与ITMO等欧洲传统强队的最大差距是:THU从参加ACM的那一时刻起就没有作夺取世界冠军的准备。

         问题要回到在THU眼中ACM的地位,关于这个问题,大家都有自己不同的看法。我觉得ACM在THU则更像是一个社团活动,或者一种娱乐项目,这一点与SJTU相比简直是天壤之别。我并不认为不同看法之间有任何优劣,只是认为这种对待ACM的态度已经严重影响了我们的成绩,虽然比赛成绩在THU的这种态度下没有任何意义。

         我内心并不反对THU的这种观点。在比赛中,我们充分享受了比赛中的乐趣,同学之间进行了很好的沟通。通过比赛,我得以认识来自全国各地的同学,与他们交流各方面经验。

         但是从另一方面讲,我们没有耕耘,就很难收获世界冠军,虽然世界冠军对THU来说却确实没有什么特别的意义。

         从选手的综合实力上讲,THU与ITMO等欧洲传统强队相比,其实占据了一定的优势,很难有其他学校能够每年录取15名左右的顶尖OI选手。这些OI选手在入学时各方面能力上都优于欧洲强队。但是,他们从入校之后再没有接受过正式的相关知识的学习与训练,大部分选手的最佳状态就是刚刚进入大学的时刻。

         从平时学习和训练上讲,THU与ITMO等欧洲传统强队相比,是截然不同的角度。邬老师在平时沟通中,更像是社团主席,引导我们享受比赛中的乐趣,和选手之间沟通方面都做得很好。但是THU没有像andrewzta,Petr这样的“金牌”教练,有他们的帮助能更好地做到知己知彼,平时THU训练大多都是学生自发组织的,于是THU大多选手好像连“知己”都做不到。亚洲分区比赛中,THU依靠选手深厚的OI功底掩盖了这种平时积淀的差距,而总决赛中却暴露无遗。

         从赛前的训练上讲,THU与ITMO等欧洲传统强队相比,做得远远不够。记得前面提到过:直到赛前,我们的精神状态都没有调整到最好。其实直到出发前3天,我们才勉强能做到每天做一次模拟比赛,不过从社团活动的角度说已经做得很不错了。

         这一年,我很高兴看到OI选手中出现了ahyangyi,yuhch123,Loner等各方面极为出色的新人,他们的加盟,极大增强了清华ACM团队的实力。

         不过,比如明年,即使中国队伍占据主场之利,THU想获得世界冠军可能还需要一些重要的准备。

         首先,从我个人参加ACM已经有4年时间了,与2005年THU的ACM情况相比,这些年来,学校对于ACM的重视程度有了大幅的提高,收益已经体现在了各个方面。但如果想真正登上最高领奖台,还需要思想和态度上有充足的准备,虽然现在看来,这种态度转变在THU是否有意义还值得商榷。

         其次,从赛前训练角度上看,队伍的状态对成绩影响很大。今年虽然THU有机会和Waterloo等名校合练,但是比赛的密度和强度与欧洲各队相比都相差一个档次(其实,今年的校内PK的强度是很高的)。这一点我们应该向SJTU学习。

         最后,在总决赛这种级别的比赛中,“夺冠需要一些运气”,多积攒RP吧,J。同时也预祝所有中国学校总决赛好运。

  评论这张
 
阅读(142)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017