上海赛区流水帐

acm-icpc第一次写这样的小结,结果变成了这样的流水帐,希望还好吧。小学的时候被灌输一个概念,日记作文之类的都要避免写成流水帐,记不清具体是什么原因,也许是写流水帐比较省力,没啥技术含量,老师阅读起来也平淡无奇吧。不过现在的我看起来还是比较喜欢流水帐的 :-)

(下面涉及一些人名称号以及一些符号缩写等可能只有一部分人知道是什么意思,如果你不太明白,就跳过吧)

虽然我之前来过上海几次了,不过这次住的“大众国际会议中心”确实比较偏远,从轨道交通3号线转到轨道交通9号线坐到“”下,这里出租车也比较少,黑车比较多,行走的是漆黑的几乎无人区的夜路,尤其是快到宾馆的那一截,yz居然提议这段路可以步行过去 8-O

这段时间上海移动似乎有点问题,手机信号极其不好,GRPS连接很容易失败,这几天我还遇到过“仅限紧急呼叫”、“无服务”、“未注册的SIM卡”这样的异常情况,上海的同学也表示最近打电话中途容易莫名其妙断掉。

来的时候圆阿姨发短信来催稿了,关于MSTC月刊,我主讲的Word小课堂的内容,这时候怎么可能写 8-O 于是用“消失中”回复,圆阿姨似乎有点不高兴的样子,暂时无视了。

宾馆提供了免费的网络,但是一个双人间只有一根网线,用的是和紫金港校区类似的华为的验证,只是验证页面的用户名和密码都被自动填好了,可以直接连上互联网。这根网线被范叔占用了。我找到了一个免费的未加密的无线网,看起来是一台DLink路由器提供的,询问得知不是宾馆提供的,不太敢用,扫描了一下发现有8台机器也连上了那个无线路由,其中几台还用了Apache for Windows提供了HTTP服务。范叔的无线共享也没有弄好,于是就凑合用这个无线了,实际测试速度大约比hsys的网络慢2-3倍,而且DNS服务几乎不可用,改用其他的DNS就好多了。

24日上午的开幕式,在东华大学的图文信息中心,进入的时候要进行体温检查。领导迟到了1个多小时,之间一直在循环大声播放东华大学的洗脑宣传片,移动信号也是极其弱,早知道把防噪声耳塞带来了 :oops: 东华大学很大牌的样子,领导讲话还有人翻译,不过由于迟到导致时间紧张的原因,只有一部分的讲话才有翻译。东华大学的大牌还体现在开幕式会场的每个座位都发了一瓶水,这次要使用东华大学的未命名评测系统,还有和正式赛使用相同裁判的网上的同步赛等。

开幕式和提问结束后就是漫长而无聊的热身赛了,由于领导迟到耽误,我们入场的时候比赛已经开始了,也就不期待如何秒杀题目了。第一印象是熟悉的Ubuntu,和网络预赛一样的东华专有评测系统,以及质量很好的各种颜色的pp气球。B题就是把输入输出,我写了很短的C程序完成这个任务,发现评测系统会判断程序结束状态,必须正常返回0,否则会被判成Runtime Error。

赛场用的键盘是方正的某种超薄键盘,我们队都感觉怪怪的不好用,用起来很容易按错。这个键盘右边还有一排功能键,我依次按过来,前几个键似乎都没有用的样子,最后一个键按下去就立即出现关机动画了 8-O 遭到队友的bs之后,只好再打开,发现之前说的热身赛的时候会使用还原卡有问题,修改过的配置都还在。比赛用的开题密码是装在信封里面的,每个队都一样,但是每个队自己的登录密码并没有发,找到了旁边的一个志愿者mm来,她试了两次就输入对了密码,原来是table10(当时还不知道大小写)。这样重新登录之后提交历史和提问历史都没有了,好不人道啊。

然后发现A的范围很小,于是用netbeans写了一个C++程序暴力过掉了,赛场提供的netbeans 6.5果然要比6.7要弱一些。只剩下C了,hexing翻了一些数论书也没有明确的线索。我们商量了一下没有什么结果,因为是热身赛,我就yy了一个看起来可能比纯暴力好一点的暴力算法去写,果然是TLE。然后人肉试验了一些小数据,发现x1+x2+x3不是b就是2b,于是批量进一步验证,结果中间hexing把判断质数的函数写错了 8-O ,Debug后确认了这样的规律,三个气球之后就开始试试别的东西了,我用Java写了B,发现netbeans没有提示文档,还有返回结果可能是PE,并且问问题的功能形同虚设,什么问题都是”Sorry, no response”。让人气恼的是交题有30秒限制,就是每当按一次Submit按钮,不管成功或者因为30秒间隔没有到而失败,都会重新开始30秒计时。这个评测系统在交题的一瞬间会把程序在本地编译,据说有一条原因是“如果你想把裁判机搞挂,你自己的机器要先挂”,编译的时候CPU占用率很高,通过GNOME面板上面的系统监视框可以大约知道什么时候过了30秒。顺便提一下这里的打印,必须要在那个评测系统客户端打印,打印的页边距比较宽,字体是单一非等宽字体,没有页码和时间戳。

觉得差不多了,我就开始扫荡送来的食品,撕开火腿肠比较不容易,再之后就拿着相机到处拍了。在yukkuri那里又按了一下关机键,惨无人道地迅速关机了,据说还有一个问题没有回答,于是又被bs了。不过我想大概也会是No response的吧 :roll: 重启后同样遇到密码问题,本来要让志愿者来输密码的,我自作主张地猜了几个,原来是table2。hsys扫了一遍Ranklist,发现许多之前测试这个评测系统的痕迹。

有许多队伍已经走了,于是在yukkuri旁边的一台机器上玩国际象棋,还是能轻松虐掉电脑啊 8-) 又和jack玩了几局双人贪吃蛇。然后就回到自己队伍的位置了,这时候在尝试用二分图匹配的方法剪枝去处理A,但是一直WA。我就参与了调试,构造了一个case,立即发现问题,然后瞬间改好,就过了。

又无聊了一段时间,早知道和LAF学去草坪上睡觉就好了。热身赛的5个小时结束了,我想带出来一个气球却被一位志愿者mm收走了 :-( 去吃饭,在食堂看到很多人手里拿着气球…… 吃完饭就去超市买东西,然后就回宾馆了。

回去就睡着了,之间发生了清醒的奇怪的事情,晚上的时候完全清醒过来,连上网灌灌水,圆阿姨又来短信催稿了,这时候更不可能去写了 8-O ,准备一下要带的东西,就又睡了。

第二次比赛,远远没有刚结束的第一次那样紧张了。这一次也不需要冷笑话来缓解紧张气氛,冷静地进场,排队上厕所,开始比赛。

我是从前面开始看题的,第一题看到那个图就想先跳过去了,开始看第二题,感觉是矩阵乘法之类的,但是似乎还有其他问题。就在我还在纠结于如何暴力打出第二题的一些小数据时候,EZ已经对后面的F有想法了,写了一个简单暴力的版本,果然TLE。这时候我还在想B和时不时地喝水和去厕所,hexing说A很简单,最多只有65536种状态,于是我就看了一遍A,果然很容易,就开始写。写完了却没有过Sample :-| 动用了静态调试和动态调式,怀疑错许多地方,许久才发现交换两位的地方写错了,看起来还是有一丝紧张,应该是:

idx ^ ((1 << (i - 1)) + (1 << (j - 1)));

在代码中却是:

idx ^ ((idx & (1 << (i - 1))) + (idx & (1 << (j - 1))));

这是因为后者的右边在判断两个位置是否可以交换中用到,复制粘贴相似代码后没有改过来。改完测了一下初始化打表时间,没有问题(这道题可以把表打全,不止前3步,也是瞬间完成的),交上去就1Y了,不过这时候已经是比赛开始一个小时了。

EZ发现H、I、J都可以做,尤其是H,只要敲好两个模块就可以过了(事后想想, 8-O ),于是hexing去敲模块(打字快一些)。我又看了看C,EZ说C要分长字符串和短字符串两类讨论,短的直接暴力算,我认为分类讨论两种都是正确的算法一定是没前途的,就开始yy这一题,比较有想法(现在觉得也是很有前途的,不是二分结果Hash方法,但是没有OJ可以提供验证 :-| ),觉得如果有时间的话一定可以完成C的。hexing抄完了模板,过了Sample,交上去却WA了,这时候换EZ写J,我和hexing讨论B,我想到了集训时的某个需要对100取模的题,moondy说可以算循环节,觉得这一题也可以这样做,不过我也怀疑O(P)的复杂度行不行,问了B题有多少测试数据,果然回复又是Sorry。鉴于手上有一份我写的矩阵乘法的Java版本模板,于是这道题决定是我来写(我们队只有我用Java)。J交上去也WA了,hexing去改H,这时候我在想是先写B呢,还是先写C(自认为已经有比较成熟的想法)呢,最后想想还是先写B吧。改过若干次的H交上去也还是不对,我们决定放弃H,去看看F是不是可以优化,EZ认为J他一定可以发现错误改好的,我就来写B,期间EZ改了几次J,这道题也过了。Java的模板比较长,我写完B交上去WA了,这时候一定是没有时间写C的了,就在想B会错在哪呢,顺便又用set<int>尝试了一下F,EZ对STL容器不熟悉的样子,先是RTE,后来又是TLE,这道题大概也是要放弃了(后来看解体报告知道是剪枝搜索,想想和预赛的A在某种程度上是一样的)。我和hexing讨论发现B中余数循环节不一定立即开始,于是我去改程序使它支持这种情况,让hexing去想一些case,这个时候时间已经不多了,没有想到case。自认为修改好的我过了Sample交上去又是WA :-? ,hexing怀疑了一些地方,都不是真正错的地方。最后几分钟,又有些奇奇怪怪的紧张了,代码中的变量命名并不友好,再加上被怀疑得我自己也思绪混乱了 :-| 以至于最后到了时间也没改好,实际上最后一分钟我已经意识到问题的所在了,但是没有想好修改方法,结束后两分钟内就改好了,不过显然没有地方交了 :oops:

结束后就俩气球,想应该是有铜牌了吧。在来上海之前,我的预期是银牌左右,比赛刚结束的时候有一点失落。

从这次比赛看,我觉得暴露的最大问题就是太慢了,特别体现在调试的时候,发现定位问题的速度。还有一个问题就是选坑能力,不过这也是一个没有答案的问题,大家都可能乐哉乐哉地跳错坑…… 如果不去做F和H的话,B肯定可以能过了,C也可能过,如果进度异常顺利的话,还有时间去看看E (旁白:想得轻松 -.-)

当然我觉得也是有一些好的地方的,尤其是由刚结束的宁波赛区获得来的经验,比如独立读题,就是有些题目有的地方废话很多,会有潜在的多种解释,在时间不紧张的情况下,不要由室友介绍题目大意,免得被灌输错误理解。再有就是毅然放弃一些题,比如这次的F、H。除了这些,还有一些我从一年前就觉得不错的地方,比如独立解题,如果一个人确信可以搞定某道题的话,就不需要分散队友的时间。不盲目跟风,如果确信可以做某一道题的话,才不管其他队的情况呢。遗憾的是这些是充满变化的,“确信”本身就是一个含糊不清的词。

东华大学的洗脑宣传片,抢气球的mm和奇怪的键盘都给我留下不太好的印象,参观无兴趣,结束后我就直奔复旦大学而去了。yz邪恶地说车票不能报销,我就决定步行到地铁站。随机问到的三名志愿者都不知道如何到复旦大学,于是就问了如何的到地铁站,沿途又问路了好几次,这里有一些人回答得很有问题,尤其是东华大学正门口的门卫 8-O 。步行途中遇到一好心人骑着摩托车带了我一段路程,又走了一截,总算到了松江大学城站。

碰巧在车站看到一位北师大大四(后来了解到)参赛mm,她也要去复旦,于是一同前往,路途不短,我们就聊了聊。她们队前一个小时就过了前两道题,后面很遗憾的一直没有过新的题,不过她们还要去哈尔滨赛区,我想那里应该是很有机会的吧。她似乎对杭州很熟悉的样子,抱怨上海公交很贵(北京人都这样),很奇怪她说要到复旦本部,应该和我的路线是一样的,却要最后转1号线,我是要走3号线的,结果询问她同学发现她去的校区原来是另一个 8-O 9号线到终点就要分别了,只好wave了。

然后我径自去复旦,期间和同学短信通信似乎有10分钟的延迟,从大柏树站下车之后还要坐两站公交,公交车站发现没有零钱,就近买了一个手抓饼,然后坐133路车到了复旦。呆了一段时间想到yz说第二天早上9点离开宾馆,就决定回去。回去的途中Fire打电话来说有骨灰级人物要bg,路途太远,只好错过了 :cry: 从地铁站那里几乎打不到一辆正规的出租车回宾馆,不过还是遇到了一辆,司机连续闯过俩红灯,速度地把我送回去了。回到宾馆后被yz告知是明天早上11点走,表示愤怒。不过发现居然有银牌,又感觉好一些。

连上网看了一份据说hhgg弄到的精简版解题报告,有些地方恍然大悟。惊奇地发现RVPN是可以用的,速度还有200KB/s左右,下载了一份大富翁4,这也是可以轻松虐电脑的 :roll: 不过似乎没有几个人对这个游戏特别感兴趣,于是睡觉了。第二天早上7点有些清醒,想想早餐也没有特别吸引人的地方,而且比较困,就睡到10点了,爬起来收拾一下就准备离开宾馆了。即将离开宾馆的时候我们队去享受了一下宾馆门口的秋千,荡的幅度大一些我就有点受不了了,接着hexing也受不了,只有秋千达人EZ还在荡,不过我们抓拍到了一些有趣的照片 :-P

之后发生的事情就比较平淡了,中午吃饭后和范叔玩了几局frozen-bubble,接着就顺利回来了。

希望还有比赛的各队都能取得如愿的成绩 :-) 回来后别忘了bg :-D 。而我,就期待为数不多的下一年吧。

5 thoughts on “上海赛区流水帐

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>