Contest Team ICPC Rank Rank
2007・长春 Terminal 11th(S) 13
2007・北京 Terminal 12th(S) 19
2008・北京 Zodiac 3rd(G) 5
2008・胡志明 Zodiac Champion 1
2009・合肥 yukkuri 3rd(G) 6
2009・上海 yukkuri 3rd(G) 5
2010・杭州 ArcOfDream* 3rd* 5
2010・福州 ArcOfDream 3rd(G) 5
2010・河内 ArcOfDream Champion 1

icpc-2010-hanoi-dhqghn

从杭州到福州再到河内,一路折腾,而且严重睡眠不足。回来以后发现还有各种事,于是这篇小结足足拖了一周才赶工赶出来……

福州=>河内 胡志明&河内

ArcOfDream+hhanger四个人一起从杭州飞广州,到广州之后受到了moon爸爸和moon妈妈的盛情招待。然后与杭州飞来的can哥会和,飞往河内。吃了以前来越南的教训,提前安排好了接送服务送到酒店。这次的酒店很赞,比我上次到胡志明的要好,酒店很多设施似乎是中国进口的,印有中英文。

河内和胡志明作为越南最大的两个城市还是有很多很像的地方的,满街的摩托车,拥挤的道路,漫天的电线和狭窄的房屋。到河内第一天我们就去了越南的西湖,发现ArcOfDream今年去的杭州、福州和河内三个地方,都是有西湖的地方,不会沙姆沙伊赫(شرم الشيخ)也有西湖吧……传说gogogo的sls和vls四年前曾再次手拉手环湖一周,——(下文省略百余字)——

河内似乎也没什么好玩的,不过能看到很多有中文对联的庙?祠?比赛以后大家去了个民俗博物馆,当然比在胡志明去的战争纪念馆好很多- -||| 河内的物件似乎比胡志明靠谱很多。顺便四年前1RMB = 2000VND,两年前1RMB = 2500VND,今年再去1RMB = 3000VND……

2008年我+hhanger+Fire组成的Zodiac在胡志明拿了冠军,2009年没有越南赛区,所以今年可以算ZJU的卫冕之征。不过2008年的题目相当不靠谱,除了几道秒杀外,都是一些规模超大数据超水的题,有大自然计算几何,Fire用模块直接水过。最后没有人过的两道题,一个是论文结论题Nim积,一个是1000*1000的默比乌环上的连连看。顺带一题,当年我们队唯一一个20min的罚时是我贡献的 >_<

两次来越南,都是被丢在一个都是外国队伍的酒店里。在胡志明的时候,压根没去过主办学校,只在一个类似人民大会堂的地方参加了试机、比赛、颁奖。不过这次在河内却被抓去主办学校参加了开幕式,而且还有坑爹的Campus View和各种浪费人生的等待。

意料之内的不靠谱

原定的试机时间是4:30,可实际上一直到6:30才开始,我们就在外面干等了两小时,连个坐的地方也没带我们去,而且还不管饭。开完教练会的hhanger带回了主办方的礼品——越南语版的OpenOffice.org,T_T,肉牛满面。越南似乎一直是一个队一个队叫号进去的,而总裁判经常用越南语广播各种听不懂的东西,偶而几句越式英语还是各种听不懂。没有pc^2的用户名和密码,于是我们直接试team23/team23,居然登录了,比赛一开始我们就直接提交了4个Clarification,分别是问厕所、board、打印方面的问题,提交的id是2, 3, 5, 7……

结果这些问题都没得到有意义解答。厕所的问题我们直接问了几个场地工作人员,得到各种千奇百怪的搞笑回答。关于打印和board得到的结果是,嗯,这个明天会有的,靠,那试机试毛啊。题目依旧是一份越南语加一份英语。然后我们向裁判长表达了希望拿到三份英文题目的愿望,他给我们的回复是回去问主办方,不过我基本可以这个回答是在敷衍+忽悠我们。事实上这个问题我两年前就问过一次了。

然后集合准备回酒店,结果又要等,而且主办方“盛情难却”,hhanger又收下一份厚重的OOo,虽然最后除了我带回一份,其余都送酒店了。中间发生一件很点点点的事,我们突然想起来忘记把字典留在现场了,结果欧阳问我说我们周围也没有人留字典啊,我反问到他们要字典做什么,他们有越南语版的题目,于是我们两人跑会去把字典留到了比赛场地。回到酒店已经不早了,在酒店填饱了肚子就洗洗睡了。

正赛流水

比赛当天,那天杀的schedule让我们5:30就得起床,结果到了比赛现场还是和前一天一样干等半天。进入比赛场地后,周围都在用电脑,而且打开电脑发现昨天试机的东西都还在,可惜我们没有像xdq他们一样在试机的时候把计算几何模块敲好。不过这个时候大家都在机器上敲东西,所以我们也先敲了一些计算几何的模块,不过比赛中完全没有用到。题目如我所想,依然是一份越南语加一份英语,而且没有用信封包装就直接发了,估计偷看也问题不大,不过我们没这么做。

比赛开始,撕开那份英语的题目把ABC发给moondy,把IJK留给欧阳,我看DEFG。D题,就是要求一个长度为1w的串和200个长度为500的串的LCS,我知道LCS有O(nlgn)的算法,不过没实现过,先丢着。E题,题目就是给100个矩形,每个矩形在单位时间内会在LRUD方向扩展单位长度,问最找出现overlap的时间。F题,定义Signature为一个number里比前后两个digit都要大的digit的个数,问X到Y间所有number的signature sum。G题,定义G(i)为将2 * i表示为两个质数和的方法数,题目要求\sum_{i=2}^n{G(i)}, n ≤ 500000。我比较早看了G题,算法也很简单,不过因为参考往年各种不靠谱,暂时还把握不了整场比赛的难度,所以没有马上写。

果然,A是一个字符串匹配的大水题,属于strstr轻松过的那种,moondy让欧阳去写,A1y(5)。B我表示什么也不知道,也被moondy瞬间过了,B1y(10)。C似乎他们两只讨论了一下暴力是否够快,然后用暴力写了确实够快,也C1y(23)。写C的中间我上去写了G,发现脑残了一下,改过以后G1y(25)。然后moondy yy了J就是二分图最优匹配,让我确认一下,我看题目就是裸的最小权覆盖么,于是让moondy去敲km模块,我写完main函数后,J1y(44)。然后让欧阳用我yy的二分方法写E,之后E1y(69)。I题就是个裸的LCA,欧阳上去写,中间debug的过程我上去写了一下F,最后欧阳调好I,提交I1y(106)

赛前说打印会有的,确实有了,但是在dev-cpp里一打就直接卡死了……后来我们都扔到notepad里打印了。送打印的速度在可接受范围内,不过有次把team7?的打印也误送给我们了……果断叫住志愿者。但是点开传说中的board链接一直是出错页面,只能看看大屏幕上的滚动投影,自己电脑上几个小时以后才能看到board。board还不是实时的,很久很久才更新一次,整场比赛下来,我看过的board也最多只有五六个版本。我们7题的时候,罚时282,而此时排在第一的南洋理工已经9题,罚时490,神速啊,我们前面还有8题罚时468的国立台大和8题罚时511的HKUST。

F题比成都的A可差远了,比大妈题ZOJ2599更是差远了,不过写起来统计的地方还是有些细节需要注意,写完用暴力对拍,发现一个错误,改过拍过之后提交,F1y(127)。H题很早就有队伍过了,题目就是要求n的最小倍数,满足(123456789)+0*的形式,其实参考很久很久以前上海Regional的网络预赛就非常old还naive了,我在集训中还见到过几次同类型的题目。moondy一开始用了优先队列写,结果WA了,发现确实比较有误,不能保证求出来的是最小的。moondy打算沿着最初的思路改,我觉得很麻烦,于是我简单得多的办法重写以后,H2y(154)。H成为我们全场比赛唯一一道没有1y的题,moondy成为今年唯一一个20min罚时的贡献者。D题我一开始和moondy讨论了一个200 * 500^2 * lg(10000)的算法,而后来欧阳想出了通过空间换时间把复杂度降到200 * 500^2的算法,实现起来也很容易,比较顺利的,D1y(158)。比较意外的是全场最后只有我们过了D。

其实我们当时不知道自己已经提前两小时锁定冠军的,甚至我们都以为自己不是第一个10题的。现场气球的发放相当坑爹,首先是比赛开始好久没送气球,然后一次给我们送了全场仅有的4个气球,hhanger为此霸气的场面拍下了照片(题图)。另一点是我们比赛时没太注意到的,那就是气球的颜色是随机给的随机给的随机给的。虽然board上还有越南语的颜色Đỏ, Vàng, Trắng, Hồng…但实际是随便发的,据说比赛开始我们和NTU拿到了八个不同颜色的气球。再加上三个队伍是围着圆桌做的,根本分不清气球是谁的,所以不但不知道过了什么题,题数也无从得知。我们还以为NTU早过了D已经10题了。结果后来我们一刷board才发现我们是第一个10题的。然后搞K,K就是序列操作加广义的LIS,后面那个比较简单,前面那个比较吐血,知道splay可以搞,但是很麻烦,块链可能可以搞,但也很麻烦,于是欧阳先写了一个O(m^2)的算法水,果断TLE了,看来数据还是有点靠谱的。临近比赛一个小时的时候看到的最后board还是只有我们10题,当时其实可以确定是冠军了。最后一个小时我一直在写D的块链版,写到最后还是RE/TLE。

小结

能够在河内夺冠,实现ZJU的越南卫冕,当然还是开心的。不过就比赛收获而言,其实河内要远不及福州。就含金量来说,河内的冠军未必比得上一个国内的第三。河内的比赛要说唯一的收获就是体验了一下在不靠谱的陌生环境下比赛,对队伍实力提高而言帮助有限(好吧,我还在怨念东京……)。ArcOfDream依然有很多待解决的问题,需要在World Finals前静下心来处理,无论个人还是全队,都要抓紧修炼,太天真太懒惰或是指望吃老本迟早要尝苦头的。

今年的ArcOfDream和两年前的Zodiac在Regional上取得了完全一样的成绩,我们期待在World Finals上能再接再厉,争取新的突破。两年前Zodiac在瑞典拿得第二的时候我没有选择退役,并在去年出于各种考虑主动选择了不组一队,而无论如何这次的World Finals都将成为我的告别赛,希望能给自己四年的ICPC之旅画上一个圆满的句号。

31 Responses to “ICPC Hanoi Regional – 河内夺冠,越南卫冕 by watashi@ArcOfDream”
  1. autu says:

    Oh, thank you very much! Your solution is quite surprise to me. The problem is not too hard as I thought.

  2. autu says:

    Could you help me to explain your solution for problem D M-Drugs? Really sorry that I cannot understand Chinese.

    • watashi says:

      Excuse me, I cannot find the problem description, could you please provide one?

    • watashi says:

      The problem is to calculate 200 times the longest common subsequence of a fixed 10000 long string and a given 500 long string.
      First of all, we preprocess the 10000 long string to get a table `P` telling where the first specified char after the specified position is (just the same as what string::find(ch, pos) does, but with O(1) amortized complexity).
      Then, for each 500 long string `T`, we used O(500^2) dynamic programming to find its longest common subsequence with the fixed 10000 long string `S`, where state dp[i = cur_postion_of_T][j = cur_lcs_length] = min_postion_of_S = P[min{dp[k][j - 1] | k < i}][S[i]].

  3. autu says:

    Could you help me to explain your solution for problem D M-drugs? I am sorry that I really cannot understand Chinese.

  4. daizhenyang says:

    求D题做法

  5. wywcgs says:

    才发现您老也去过2007长春……疯狂仰慕啊

  6. jleex says:

    加油加油!!画个圆满句号!!

  7. Navi says:

    -.- 这么好的东西你们居然不要… 只要学越南语不就可以了

  8. Navi says:

    OOo是个什么东西……

  9. C8Luka says:

    ym大神。。。我发现你鸟。。。这次竟然这么给力啊。。。祝贺祝贺啊

  10. VegetableB says:

    D为啥不是KMP一下就是200*500^2?

  11. vout says:

    ym world final第二!

  12. quest says:

    can you post the solutions ?

  13. quest says:

    congratz dude, keep it up :)

  14. hhanger says:

    ym史哥,其实我自己也拿了一份OOo回来= =

  15.  
Leave a Reply