Rank Name Solved Time Total att/solv
1 machinator 8 823 21/8
2 Shengchou 8 1118 15/8
3 Luminer 7 639 18/7
4 Arc_of_Dream 7 824 14/7
5 CZYZ-NO.1 7 865 15/7
6 LeGenD.N 7 1194 18/7
7 N.Z.L 7 1202 16/7
8 Let_me_see 7 1276 39/7
9 Archers 7 1460 14/7
10 BUAA_ATM_ICBC 6 802 18/6

由于World Finals的时间推迟了,让我们有了一次参加上海复旦大学举办的全国邀请赛作为onsite热身的机会。最后七题第四名,前面是清华和两队上交,后面有好多好多牛哄哄的中学生,今天上UVa一看,台大在online比赛十题圆满了orz。这次比赛暴出了我们队很多问题,希望World Finals时能够解决。

周五中午出发,第一次乘坐传说中时速350公里的沪杭高铁。高铁很赞的是每排座位都有交流电源,于是在火车上拿出本本玩touhou。酒店checkin以后,第一件事情就是搞定上网,结果发现DHCP失败,于是电话前台

- 怎么上网?
- 你看电脑右下角有个两个电脑的图案……blabla……
(脑中想像了一下……这不是瘟到死么,还是XP……)
- 你直接告诉我怎么设ip吧
- #@~*&)-
(于是觉得不靠谱,挂了)

于是自己打开wireshark,抓ARP包,然后设置静态ip,再猜了一个dns搞定上网。can哥和moon姐也如法炮制。晚上还在酒店做了一把CF。

周六下午试机赛,主办方大概是疏忽了,没有提前告知大家队伍号,所有队伍只能进场以后根据牌子找自己的位置。我们分头找了三圈,就木有找到写有我们队名的牌子,只好求助现场工作人员。结果被领到一个座位前,被告知我们的牌子还没做好啊,囧,自己找得到就神了啊。后来更悲剧的是发现我们队名不叫ArcOfDream啊,叫什么Arc_of_Dream啊,这种队名除了于指导我真的想像不出还有谁会取啊,坑爹吶。试机发现judge没有开-O2优化,test可用,TL基本都是10s,本机上man page可以用,相当赞。无聊cat /proc/cupinfo看一下震惊了啊,以后ACM是不是要流行多线程了……试机出来后发现了vls和hhanger,传说他们是用google latitude跟着我的头像找到比赛现场的。之后没去开幕式,而是同vls和hhanger到食堂玩三国杀。晚上同vls一起去pt了Fire的bg。

周日正赛,题目装订的灰常漂漂。比赛一开始,欧阳搞定登录,敲vimrc,然后他很快就把G1y(7)秒了。之后我上去写E,但是没有考虑相邻的game是要换发的,而sample给的M=Y体现不了这个bug,于是WA了一次。很快发现了这个bug,这时候欧阳和moondy讨论后准备试试A,而我先下来理清一下思路,之后上机写E2y(40)。然后发现有队伍过ADJ,欧阳先用Java写了A,提交后WA。我想J,完全没有想法,重新看题,结果发现欧阳把题目里最重要的一句话看漏了。欧阳想到A一个可能的问题,基本重写了一遍,但跑出来发现没区别,于是打印到一边看,然后才发现原来A居然是case序号输出错了,改过之后A2y(91)。A过了以后我继续写完J,提交后J1y(96)。这时候看到有队伍过H,欧阳打算上去写,其实是完全算错了复杂度,以TLE结束。然后我上去写B,欧阳准备写D,moondy想I。B很简单,写完再测了几个数据后提交B1y(129)。欧阳写D,提交后WA,然后发现确实有问题,最后应该是算法不对,这题规模很小,于是我上去重写了两重循环,改过之后D2y(175)。之后欧阳和moondy一起搞I,第一次提交WA,检查发现初始化边未清空,改过之后才发现,之前就有一个测试数据没过,确认没有别的问题以后提交I2y(206)。之后想C没有结果,水H都是TLE,F没有理睬。

赛后询问wy教主C的算法,才发现我们想的方向不对。我们一直在往分治,两两合并想,完全没有往析取范式,多个合并上想。我们最后度过了90+min的垃圾时间,其实这个时间应该有人去看看F题的题目的。这两个都不是最致命的,比赛的时候犯了很多低级的,头脑发热的,要死多少遍都够的错误。平时我们训练的时候可能就太过懒散,甚至有点重量不重质。离World Finals只有不到两周的时间了,临时学习什么算法,或想短时间提高coding,熟悉库函数都是天方夜谭。但现在这种表现,不好好调整是不行的,要在World Finals上有个对得起自己的发挥。

晚上高铁回杭,行李里多了一件google的衣服,一件MS的衣服,一个alibaba的鼠标和一个google的旅行包。

52 Responses to “ACM Shanghai National – 上海热身,暴露问题 by watashi@ArcOfDream”
  1. richardzrc says:

    LZ好 是ZOJ的11年Final 队员么?

      • richardzrc says:

        LZ 想请教下,鄙人写递归算法总是会经常出错,特别是回溯法的时候,有时候递归出口逻辑漏掉了或错了,有时候参数设计问题,对此非常苦恼,回溯法经常要调试很久,是不是因为连的少的原因啊~~~

        • watashi says:

          我觉得是因为思路不够清晰吧,多练,写的时候多想,熟悉了应该就好了

          • richardzrc says:

            另外LZ对于DP算法,有什么好的建议么?鄙人目前只能做一些简单的DP,把他往模式问题上靠,例如状态空间要么是矩阵链c[i][j],要么是汽车装配f1[j]这样的~~~~~

  2. cuipanda says:

    恭喜

  3. rsq says:

    V5V5~ 求膜拜哈

  4. rsq says:

    恭喜恭喜啦~~  想膜拜一下大牛们

  5. Yiner says:

    留名 留名呀~!

  6.  
Leave a Reply