Skip to content

Tag Archives: Harbin

ACM/ICPC – Asia Harbin 2008 小结

10月8日晚的火车,三十多个小时的旅途,去往一座遥远陌生的北方城市,哈尔滨。 上火车后,惊喜地发现,我们硬卧车厢的走廊窗口下竟然有两相和三相的电源插座!可以无顾忌地使用电脑,似乎会给旅途增添不少趣味和意义。火车上,我把觉得比较有用的论文看了一遍,又对照着CD看了几章《听音乐》。 我在重要的比赛或考试之前容易滋生紧张情绪,这也是NOI2007的败笔之一。不过这次不同,一路上有队友相伴,本应枯燥的车厢里,充满欢声笑语。 灿哥通过神奇方式买到的火车票十张全是上铺,不过大家发现这种新式车厢的上铺非常舒服。更何况,在某人的下铺处有一只天真无邪可爱动人如假包换的小萝莉……这个话题不展开了,请自行YY。 T_T同学出了一些猥琐的迷题(e.g. 一只公牛和一只母牛同时踩坏了别人家的田,为何公牛主人赔偿三分之一而母牛主人赔偿三分之二?),令大家都很惊讶的,某位dd同学几乎每次都反应很快地第一个说出答案。好吧……在此我申明三点:第一,那些迷题没有一个是我之前听过的;第二,之所以我每次都能最先得出答案,我的唯一解释就是:我的思维敏捷、智商高;第三,我很天真哒,我的话讲完啦。 火车上的每顿饭都去餐车吃,虽然贵且不好吃,但毕竟是能找到的最佳选择了。这时T_T同学的母亲在德州站送上来的三只扒鸡正如雪中送炭,众饕餮很快就将那些可怜的无毛二足动物杀得片甲不留,对其二足尤不留情^_^。 火车到站时间是10日早晨5时许,一群几乎都没来过东北的人立即领教了寒风的威力。一干人等饥寒交迫地奔赴某盖头gg事先选定的车站门口的KFC,却发现人满为患无处容身。我通过手机上的Google Map搜索到了最近的另一家KFC,大家便打车前往。BTW,发现哈尔滨的GPRS网络很棒,明显感觉到比杭州的快,然而不知为何某只很拉风的iPhone在哈尔滨却无论怎样都连不上GPRS…… KFC的早餐让大家都找回了久违的饱腹感,充电完成的一干人等玩起了由gdb引进的多人纸牌游戏“盖棉被”。如果仅描述规则的话,听起来真是一个挺傻气且低技术含量的游戏:若干人轮流出牌,同时循环报数1至13;若某人打出的牌和说出的数字恰相同,所有人都需要尽量快地将手掌盖向牌堆,盖在最上面的手掌(也即反应最慢的)需要拿走所有的牌;手中无牌者胜。不过大家都玩得不亦乐乎,情不自禁高声大叫,引来了KFC MM礼貌的制止。在KFC的经历,让大家明白了一个深刻的道理(做小学生作文状):南北风俗不一样!好吧,看不懂的请略过或自行YY -___-。 打车来到哈尔滨工程大学……门口的八一宾馆报到,然后在志愿者MM的带领下入住十五元一天的学生宿舍-___-,还好后来在我们强烈要求下换成八一宾馆的标准间了^_^,偶和可爱的xgy队长gg一间哦~ 10日一天都没什么安排,继续盖几圈棉被以后,一堆无聊人士围坐一圈玩起了同样低技术含量的梭哈,用另一副牌当筹码。赌博的结果是有的人(可怜的xgy gg,cmft)输到倾家荡产,有的人(就是我啦^_^,嘻嘻)成了大资本家,我赢了比翻倍还要多哦~ 午饭选在某忘记了名字的火锅店,灿哥中途从机场赶来加入。相信大家都吃饱了,而且我自己认为吃得还不错,只是某人点了过多的丸子浪费不少…… 下午和晚上,除了必要的赛前准备,大家仍然把时间用在了打牌与谈天之类娱乐放松的项目上。期间七个人玩两副牌的接龙还是挺好玩的。顺便炫耀下,在哈尔滨玩的很多盘接龙的分数都记录了下来,在幸运与实力的双重照耀下,dd同学是总积分的最后赢家~oh yeah~ 期间值得一提的事情是,我们目睹了某欧阳极囧的脸红过程,并拍下了真相。欲知详情,请私下交流或自行YY……关键字:罩杯-___-。 10日晚上一直玩到午夜才睡。 11日上午貌似仍然是谈天玩牌。哈工程“大学生美食广场”午饭后,Genesis+gdb的猥琐男们在哈工程的长椅上懒洋洋地晒太阳,顺便开展猥琐的分手现场偷窥行动以及路过MM打分行动,期间小耗子乱入-___-。 下午试机,觉得电脑上的NetBeans还算好用,决定第二天比赛就用它了。试机期间,主办方的组织让人不能满意:每队三个人只有一份题目且不说,最不能忍受的是judge故障连连。我默默祈祷正式比赛时最好不要出现judge问题。 11日晚上,大家没有过分的娱乐,早早回到了各自的房间里养精蓄锐。我看了lrj“习题指导”和北大出版社《简明数论》两本书中的重要章节,听了贝交第五全曲,九点半安然入睡。 12日早晨六点半,醒来后的我感到前所未有的精神焕发,觉得这应该就是所谓的最佳比赛状态了。早餐中,灿哥给我们讲了若干“坚持到最后一分钟翻盘”的传奇故事。我相信听者没人想到,那天的比赛中,我们中的一支队伍会创造另一个传奇,一个毫不逊色,且注定被一遍遍讲述的传奇。 开赛半小时前进入场地,我们的装备大致如下:德芙巧克力一盒、红牛饮料若干罐、圣经一本(和合本+NIV对照)、牛津高阶词典一本、以及常用参考书一堆。 比赛开始了,共有十题,从A到J。按照一贯的读题分配:T_T看ABC,xgy看DEFG,我看HIJ。 我分到的题目都比较长,H大致看懂了,断定绝不是前期能写的题;I题意很简单,给定一个顶点的度序列,问是否存在对应的无向简单图,我觉得这应该是的经典问题,但却完全没看过类似的问题或算法;J的题意也不难理解,但可以看出,相当有大自然题的潜质。 大家把题都看的差不多了以后,互相两两交流了一下题意,没发现明显可做的题目。这时看到大屏幕上已经有四个队过题了,过的都是I。我意识到,I肯定不是难题,便专心yy之。期间xgy和我都怀疑是否只判断一下度的奇偶性就可以了,不过很快找到了反例。仿佛灵光一闪,我脑中突然出现了一个贪心构造的方法,讨论后,大家都没思路证明其正确性,却也找不到反例,于是我便上去敲了代码并提交之。 这时看到有牛队过了A,T_T给我讲了题意后,我写出前N层和的表达式给了他,他完善了一下二分答案的细节,便上去写了。写完后发现,按照我给的表达式计算的话,虽然输入不会超过六十四位整数,然而计算的中间过程完全可能会溢出,一时没有找到解决之道,只好由xgy把这个C++程序翻译成Java用BigInteger来写,交上去以后很快返回了Yes。这时已经拖了不知多久的I终于返回了,还好是个Yes。拿到两个气球的我们排名并不乐观。 在此之前,xgy给我讲了他对F的想法,我在他的基础上很快推出了完整的充要条件,但我俩都不太确定该怎么实现比较好。T_T听见后表示,如果充要条件是这样的话,那么他完全能写,因为写过很类似的题目。于是他上去用DP/递推的方式写了个程序,很快Yes了。三道题都1Y的我们第一次冲进了前十名。 写F期间,我和xgy在讨论G题,这道题的文字叙述得挺模糊的,不过通过仔细阅读加合理推测,我们很快发现原来就是一个有向无环图上的博弈问题,拓扑排序一遍再DP就行了,我上去写了以后也1Y了。当我们第4题的AC反映在大屏幕上的时候,我发现,在比赛时间过去约一半时,我们是全场第一个AC 4题的队伍,排名第一。旁边堪称全明星的清华IronGods队也只有三个气球。 这是我第一次感到情绪波动的时候,在此之前,我一直都保持着平和淡定的情绪,精神非常集中,头脑非常清醒,基本上处于巅峰状态,思考和敲题的效率都很高。然而此刻,看着大屏幕上飘扬在最上方的team53(我们的队伍编号),我出现了不应该有的过分激动以及过分自信。现在,我(多少有些羞愧地)承认,在那一瞬间,我想到了斯德哥尔摩。暂时领先造成的情绪波动直接影响到了我后半程的发挥,这也是我个人本次比赛得到的最重要的教训。 C题大概是早就得出了二分图最优匹配的算法,T_T上去写,似乎是用了令我难以置信的短暂时间就敲完了。交上去以后,返回了我们的第一个WA。我提醒T_T是否注意到船到达port以后不能再出来的条件,他意识到忽视了这一点,很快改好了,没想到仍然是WA。于是T_T打印了代码让xgy和我看。给代码查错应该是最需要集中精力的活,而我在看那份代码时却完全做不到这点,草草地、甚至一目十行地在看,怎么看都觉得没错误。很无奈的我们便想,是不是题目比较阴险必须用64位整数才可以过呢?其实赛后来看,这绝对是不必要的想法。因为当时至少有十多支队伍过了C,不少队伍都是作为第四道题过的C,且其中不乏1Y。这可以推断出,WA不大可能源于出题人的阴险,而是应该源于我们自身的问题。不过,当时的情况是,改了long long,依然WA。这期间,4题甚至5题的队伍越来越多,我们的rank一直在跌,前景非常不容乐观。看来我的缺点就是这样……处于顺境的时候容易被冲昏头脑,只有适当的逆境才能达到冷静。我再次看T_T的代码,不漏过一个字符的认真看,终于发现了程序中的低级bug。——只是注释掉了一行代码,程序就AC了。那个错误的根本原因是T_T在写那一小段时稍微有点想错了,而我从局外的角度看这段代码时,本应很快意识到这个几近愚蠢的错误,然而由于第一遍的不专心,我直到若干次WA之后第二遍阅读代码时才发现了它,这题做得不好,我至少应该承担一半的责任。 还好,虽然C题罚时比较多,在我们前四道题全部1Y的基础上,终于五题的我们名次还不错。接下来可做的题只有B和D。前者是数论题,我已经推导出了一个结果,有算法了;后者是纯粹的高斯消元而已;二者的共同点是都需要用到大数,最好是用Java来写。嗯……应该是我们队的另一个缺陷吧,我们没有人能把Java写得跟C++一样熟,所以必须用Java写的题在敲代码的速度上是吃亏的,甚至有些有关语言特性的东西还需要在赛场上试一试才知道。我们三人中写Java最熟练的xgy队长觉得B似乎更容易实现,于是便上去写。花费了比通常要多的时间,但却是严格地按照我给定的算法写出来的,没想到交上去以后WA了,只好打印出来交给我们查错,而他自己接着写D。——我想在这时我们的缺陷就完全暴露出来了:剩下两道可以写的题都需要用Java写,而赛前的训练中用Java写过题的竟只有xgy一人。这导致此时能写D的仍然只有xgy,而自己写的B还没能AC的xgy恐怕无法专心全力去写D,T_T和我在下面对着打印出来的B的Java代码YY其bug……T_T和我一致认为那Java代码十分“诡异”,表达算法时显得很不直白,但分析的结果也无法找到错误。我建议把那代码改成不那么诡异的形式再试试,大家同意了,便放下D来改B的代码。终于改出了比较清晰易懂的代码以后,测试的结果却似乎与刚才“诡异”的程序并无区别……(期间我还忍不住下手帮着写了几行,现在回忆时发现,赛场上的那几行其实是我平生第一次写Java代码- -。。。)貌似又是在我的撺掇下,把那个改完以后完全看不到区别的程序提交了,结果又是WA。这时进入比赛的最后一小时已经有一段时间了,封了board,各个队伍的排名已经不再实时公布,但从现场升起的气球情况来看,貌似已经有七题的队伍了,如果我们再不抓紧时间搞出第六题,能否拿到金牌相当未知……这时xgy继续写不知道有多大希望的D,而T_T和我做了一个相当正确的决定:我们从题意开始,对推导的过程完整地讨论地检查了一遍。期间,T_T的一句话启发了我,我发现原来是我在一开始的数学推导中少考虑了一种情况,难怪一直WA到死……我谢罪。。。还好把那种情况的代码加到程序里并不困难,加上以后就AC了,在比赛还剩十多分钟的时候,我们终于六题。 看到屏幕上的Yes的时候,我们全都激动地站了起来振臂欢呼。这是出现了一个喜剧性的小插曲,比赛的志愿者MM给我们送气球时弄错了:应该给我们的是B题对应的浅紫色气球,她却拿来了J题对应的深紫色气球。据说当时观众席上立刻一片哗然,没人想到会有队伍在比赛中把最不可做的J给做出来。周维民教授(ICPC中国区秘书长)也马上带着一堆摄影记者走过来对着我们不住地拍照。(嗯,以上文字有野史的风范,若有不确切之处请一笑而过^_^。。。) 最后几分钟的时间里xgy在敲D,不过花在这题上的时间和精力的确是比较少,加之我们不知道高斯消元在无需考虑精度的情况下会有比标准的做法好写很多的实现,所以直到最后也没能写完。至于旁边我们的Sirius凭借最后一分钟提交的D题冲至第五的神迹,我们也只有深深膜拜了。。。Orz 金牌到手的我们无忧无虑,下午我玩了会儿牌,听了会儿音乐,晚上代表队伍上台领奖(非常感谢队里的两位gg给我这个荣耀的时刻)。 接下来的时间里,Genesis与Sirius们都兴高采烈,发挥失误获得银牌的三个gdb则无法避免地淡淡失落。不过大家都知道团结勤奋的gdb实力还是相当强的,相信你们下次在成都的比赛中会弥补这次的遗憾! 其实我发现……比赛结束以后的事情我大都不太清楚了,因为颁奖结束的那天晚上起我就全身心地沉迷在一本奇书里。包括在归途火车上也一直是捧着电脑在进行一千多页的脑力激荡与思维历险……嗯,接下来我会抽空慢慢写点关于GEB的读后感的,虽然一下子很难整理出繁复的思绪。。。 哦……这次的哈尔滨之行Sirius与gdb各自也有非常精彩的小结,请原谅这篇略有些虎头蛇尾的文章吧,这五千多字已经写得我要吐血啦。。。有什么脱误遗漏错愕指出请指出,我一定修改。 好了,下一站杭州,在自己家门口比赛,相信通过对哈尔滨之行的总结,我们会越发完美。Genesis加油!