ICPC 小故事

转眼间 PhD 都快结束了,本科期间的 ICPC 经历我都记不太清楚了,这里就讲讲 PhD 期间打 ICPC 的一些故事吧。不过没准啥时候会填一下本科期间的坑呢……

ICPC 2017 - 2018

来了王子屯之后,我就在想要不要整一个队玩玩。这边玩 ICPC 的人不多,本科生水平普遍不太行(当然也有几个还行的,例如我之后提到的 Lucas Salvador)。

本来我打算随便组个队的,队友不太重要。我和我的室友 lsx 提了一下这件事。他想起他的 office mate Jake Silverman 之前参加过 WF。我一听,哟,强啊,厉害啊,赶紧拉过来看看。我后来和 Jake 聊了一下,感觉挺好的。妙呀,这样我们队就有两个人了,还差一个。后来我和朋友聊起这个小哥,有朋友表示这个小哥名字怎么听起来这么不吉利啊,怎么就轻易地 silver 了啊……

后来忘了和谁聊天,他提到了 Sobhan Miryoosefi 这个小哥,拿过伊朗的 NOI 金牌。我一听,哟,强啊,厉害啊,赶紧拉过来看看。

组了这个队后,秉承着高强度努力练习的一贯态度,我们组织了高达 0 次训练。同时,我们也不忘刺探敌情。根据我们了解,GNY 赛区当年的强队基本上都是中国人,甚至……每个队里都有一个湖南人……Cornell 有个上交队(Siqiu Yao 和 Haobin Ni),Columbia 有 Peilin Zhong,基本上就是这几个队争夺出线名额了。

坐上学校的小车后,我们前往 NYC 。终于到了紧张激烈的比赛了呢,想想还有点小激动呢。作为主力,我自然当仁不让,一把抢过键盘,迅速过起题来,哈哈哈我的主场来啦。当我写了几道水题之后,我发现,怎么 judge 不出来???就是能交上去,但是一直不给评测结果……半个小时之后终于出结果了……这种情况愈演愈烈,最后可能交了之后一个小时才出结果,活生生把 ICPC 赛制玩成了 OI 赛制。

不慌,我对我代码有充足的自信!交了几道水题后,我选择休息一下,把键盘让给 Sobhan。果然这小哥不同凡响,噼里啪啦开始做起题来,不出一会就搞定了。然后又是我来掌控节奏,又写了几道水题。GNY 的题目挺水的,几乎每个题都是 NOIP 前两题难度,算是练习基本功了吧……把大部分能做的题做了之后,有个题没看到明显想法,最后还剩十几分钟无事可做,就决定写个爆搜碰碰运气,居然还能过样例(实际上样例挺强的),在最后一分钟交了上去,让我们祈祷一下吧!

……不幸的是我最后一分钟交的代码不对。后来我问 zpl 他们怎么做的,他们表示就爆搜啊。我就觉得奇怪我也是爆搜啊,结果 zpl 说:你有没有行末空格?我:???苍天啊大地啊为什么这么对我……

于是很不幸,我们队排在第三,前两名分别是 Cornell 和 Columbia,两个队连罚时都一样。我们三个队都是 8 题,但是我们队罚时比较菜……剩下的队都比较菜,第四名就只有 6 题了。至于出线名额,组委会鉴于这种特殊情况,在 GNY regional 只有一个名额的情况下,又给了一个名额,所以 Cornell 和 Columbia 都能去 WF。那就让我们祝福他们吧!

ICPC 2018 - 2019

转眼之间又过了一年。新的一年,新的学弟,自然也有新的队友。我之前的两个队友现在都没资格打了,但是我可以从学弟里面找呀。我自然是在中国人中先下手为强,首先找了 Dingli Yu。这位大名我早就听说过,都不用哟就知道很厉害了。刚好普村每年有个新生迎新饭局,我就在饭局上约了一下 ydl。ydl 爽快地答应了。他还提到新生中有个上交 ACM 班的,Xingyuan Sun,也在饭局上,于是我也去约了一下,成功把学弟拉入伙了,这顿饭吃的值 233333

今年普村也整了一个 qualifier。我感觉今年这个队比去年的队要强,因为 ydl 有丰富的经验,sxy 看起来也很能码。那么感觉今年应该是碾压呀……qualifier 开始了,我们队写写写,过了两个题的时候不妨看看其他队咋样了,然后震惊地发现,有个队过了五个题,吊打我们……我当时下巴都被吓掉了,普村什么时候有这么强的人了???去年的 qualifier 还没见着,难道是大一新生???虽然最后还是被压了一题……我不服气啊,今年的竞争就这么激烈吗……于是赛后我问了一下学校组织方,看看第一名到底是什么神仙。他们告诉我,第一名队是两个高中生,其中有一个叫 Benjamin Qi,我去看看这是哪个大爷啊。结果一看,IOI 2018 rank 1,Codeforces rating 3k+,打不过,告辞!万幸的是,这人不和我们抢名额 →_→

当然今年我们也不忘展开侦察行动。报!Cornell 今年没有特别强的队。报!Columbia 也没有。今年稳了!于是我们又过上了在考试中学习的生活……直到比赛前两天,报!Columbia 今年有个瑞士小哥很强,不仅强,还坚持刷题……妈耶中计了,大意了,没有闪……而且,Columbia 听说今年普村很强,特意取了一个队名叫做 Kington,就是要压我们一头。

GNY regional 只好强行上了。今年我们的策略是,我是主代码手,掌控键盘的男人,sxy 是副代码手,ydl 是智囊团。中间过程我忘了,总之最后我们成功被 Columbia 压了一头,题数相同,罚时太多,成功跻身八题垫底,拱手将唯一的名额让了出去。本来以为事情就此告一段落,结果后来突然收到消息,GNY regional 又加了一个名额!可能是看 GNY regional 就两个队八题不容易吧,总之突然之间就能去 WF 了哈哈哈哈哈哈哈哈哈哈!!!葡萄牙几日游 get!

然后我就开始见证两个本科小哥忙前忙后了。这里我要再次感谢 Lucas Salvador 和 Andrew Wonnacott 在这趟旅程中给我们的帮助。他们策划了一些 local trip,材料、机票、签证、报销都在帮我们弄,整了一个非常完整的 checklist,感觉是非常负责任的 coach。我印象比较深刻的一件事是,由于葡萄牙用的键盘布局和我常用的键盘不一样,Lucas 还帮我们买了一些 sticker,比赛开始前可以粘在键盘上,可以强行模拟我常用的布局。Lucas 当时就是 Microsoft 粉,他特别喜欢 Xbox,后来他毕业后去了 Xbox 工作,算是了却一个心愿。

由于葡萄牙用的是葡萄牙语,我们几个都不会,但是 Lucas 小哥是阿根廷人,母语西班牙语,而西班牙语和葡萄牙语听说挺相似的,于是 Lucas 小哥就成了我们的御用翻译。Lucas 小哥只教了我们一个词:obrigado,谢谢。此时一个王老爷子路过并且自称葡语砖家。

这次 WF 还见了好几个朋友,例如欲与我一争高下看谁能豪取 rank 1 的王老爷子,“今天我是主角”的向老师,高中学长 syj,还有 UIUC 的 zzx。说起来这次居然能遇到好些高中同门,例如有个比我高一届的 syj,我,比我低一届的上交的 lmy,还有比我低两届的北航的 hx,算得上四世同堂了……说起 lmy 还特别尴尬,我之前在赛场见过他好几次,但是每次都把他忘了……

至于比赛结果嘛,那就没啥好说的了哈哈哈哈哈哈哈哈哈哈,我们这辣鸡水平自然拿不了牌,但是开心就好。有个题是树上后缀自动机裸题,我一看就知道怎么做了。但是问题是,我忘记怎么建后缀自动机了……我用的 dfs 序来建,最后一个小时感觉这个题一定要过,于是赛场上现场写拍,强行 debug,发现不知道为什么一些节点建了两次,我也不知道为什么会这样,于是就加了一个 if 特判,如果这个点建过了那就不建了,然后就过了……说起来我们这比赛的位置倒是得天独厚,左边北大,背后清华,远处厦大,适合直播的位置 23333 最后成功拿到五题榜尾,拳打 Duke,脚踢 Columbia。(题数并列)#41 挺好的了,我是挺满意这个结果的,不过可能还是低于 ydl 的平均战绩,希望他不要在意 233333

说起来比赛完当天回宾馆玩游戏,突然发现游戏里提示附近也有游戏玩家,我就一时兴起加了一个,居然也是中国人,然后就聊起来了。他学校具体是哪个我忘了,只记得在广州(不是中山)。然后我突然记起,早上入场的时候,我和 Duke 的人坐在一起聊天(他们也是中国人队,Kangning Wang,Xiang Wang,Chenwei Wu),Duke 旁边就坐着国内某大学的。然后我就提到这回事,还真是巧了,他说他们当时就坐在 Duke 旁边……

Huawei 赞助了这次比赛,他们还整了一个挑战赛,大概就是 train 一个 binary neural network。我们队最后勇夺第三,奖品是每人一个 Mate 20,发了发了 23333 不过他们发的是欧洲插口的,我还得自己整个转接头或者再买一个美标插口。

赛前赛后我们都在 Porto 当地稍微转了转。赛前有官方组织的一次 excursion,赛后是 Lucas 带我们转了一下。我们去了 Porto 当地一家比较大的商场,主要就是去买纪念品的。商场里面吃了一个啥猪肉汉堡,味道感觉相当不错,当然点菜就交给 Lucas 了。Excursion 的话,似乎就在城里转了一下。我感觉这座小城还挺有风味的,老城区的石板路加分不少。对了我们比赛的地方叫做 Alfândega,似乎是之前的海关。

由于年代久远,我这里只剩当初发的票圈了,那就放上来吧。

Alfandega 外
我也忘了这是个啥了
火车站内侧
小石板路
路上遇到的一幢小房子,我也不知道是干啥的……好像这边很喜欢用蓝色啊……

ICPC 2019 - 2020

这应该是最戏剧性的一年了,故事太长……

这次其实我佛了,毕竟已经去过一次 WF 了。但是 anyway,我还是决定打一把。满打满算,这是我最后一次作为选手能参加 ICPC 的机会了,在此之后,我被五年 regional disqualify 了,也不能用年龄 qualify 了,如果这次还能有幸进入 WF 的话,也被两年 WF disqualify 了。另外一个原因是这次 WF 在俄罗斯,一个我没去过但是觉得十分浪漫的国家。我曾想象过听着柴一钢协看日出,云层试图遮住太阳的光芒,但当太阳冲出云层的那一刹那,阳光洒满大地,崭新的一天已然到来。如果能在 Moscow 完成我的退役之战,那将是我的一大幸事,没有遗憾了。

我打算找 Kaifeng Lyu 和 Shunyu Yao,然而,lkf 遭遇超长 check 来不了了……恰好这个时候 Lucas 说他二缺一问我想不想组一队,我当时还是更想和中国人组一队,毕竟 bibi 起来方便一些,于是就问了一下 ysy 打不打,他要是不打的话我就和 Lucas 去了(其实 Lucas 水平应该还行的)。ysy 说还打,我想了一下还是和 ysy 组一队吧。

由于我们队现在只有两个人,打了 qualifier 之后普村这边就给我们 random assign 了一位本科生小哥 Joshua Kolenbrander,然后我们就去打 GNY regional 了。Joshua 水平说实话不咋地,于是我们商量的结果就是……我来当主代码手,ysy 来统筹,Joshua 小哥就打酱油……

当然 regional 之前按照惯例我也要收集情报。NYU 有 Muge Chen,Columbia 有 Hengjie Zhang 和 Runzhou Tao,Cornell 忘了有谁了,但是听说又是一个上交队,感觉都挺有实力的……你们 Cornell 是 SJTU 美国分校吗……不过今年北美赛区的规则和以前不一样了,不再是每个 regional 决出一个,最后 wildcard 分配,而是每个 regional 选出几个,然后一起参加 North America Championship (NAC),由 NAC 统一分配名额。

GNY Regional 晋级 NAC 有四个名额,我们虽然有超高罚时,但是还是有惊无险地以第四名的身份晋级 NAC。今年的 NAC 在 Atlanta,我之前还没去过呢……NAC 组织方组织了一次 Coca Cola 工厂之旅,但是我懒得参加了……NAC 还挺正式的,也搞了个 dress rehearsal。NAC 就没这么好运了,我们队在一半时间过了五题,之后就要开新的题。然而这个时候,我开了一道题,写了半天没写出来直接 gg……ysy 表示某个题很多人过了,然后我听他给我讲了一下题目大意,我想了几分钟表示不会做就鸽了……最后结束的时候我们也只有五题……

出赛场之后和别人 bibi,发现我开的那道题是全场最不可做的一道题,另外 ysy 转述题目的时候,有一个重要的条件我没有注意到,导致这个题我就不会做了。赛后我重新思考了一下,有了这个条件之后整个题目就变得很可做了。最后看 board,我们在五题的队中排名还行,但是 NAC 一开始只打算收十几个队,但是我们排在 #23 ,所以没有晋级。

故事到这里似乎就结束了,我最后一次 ICPC 参赛就画上了这么一个句号。在此之后很长一段时间,我都没有再关注 ICPC 的事。春天的花又开了,ACM Club 又在招新,新人老人来来去去,又是一年的 qualifier,又是一年的 GNY regional,又是一年的 World-... 咦,怎么 WF 还没打?NAC 是在 2020 年春天举办的,然而 2020 年 WF 因为疫情迟迟没有举办,一直鸽到 2021 年 10 月。

八月的某一天,我突然收到了来自普村教练的一封邮件问我们是否还有兴趣打 World Final。人在家中坐,slot 天上来。似乎由于疫情原因,好些队伍没能参加。主办方向很多没晋级的队发出了邀请,我们队就是其中之一。所以这样一来,我又可以去 Moscow 参加 WF 了?博五老油条还能参加 WF,不说绝无仅有,但也相当稀少了吧……

于是我们火速回复,开始准备去 Moscow 的材料。主要需要我们准备的有:俄罗斯签证,学校允许,当然还省略了一个重要细节。俄罗斯签证是相对比较好搞的一个,WF 一般都有政府支持,签证上基本上都不会为难我们,速度也很快。另一方面,我们一开始还想能不能让学校报销机票,因为上一次就是报销了的,但是后来 bibi 了一下,这个似乎特别困难。学校当时对学生出境管得很严,他们定义了 University-sanctioned travel:

University-sanctioned travel: Any trip that meets one or more the following criteria:

  • Supported through funds disbursed by the University or a University-affilicated entity; or,
  • Regardless of funding source is:
    • related to or in support Univesrity operations;
    • undertaken as part of a faculty, researcher, or staff member's job duties;
    • for undergraduate or graduate research;
    • related to or results from an affilicate's participation in any program offered by or coordinated through the University; and/or.
    • undertaken by an enrolled undergraduate or graduate student and results in rwork that will be considered for academic credit or is otherwise related to a student's program of study.

学校当时禁止了 University-sanctioned travel 。我觉得就不用期望学校报销机票了,只要能放我们走就行,我自己出点钱也没问题。我当时的想法是这点其实可以以一种特别无赖的方式绕过,就是学校不禁止 graduate 的 personal travel,那我可以提前以 personal travel 的名义去 Moscow,到了 Moscow 之后再打 WF 就不涉及 travel 了。ysy 表示有点 concern,怕学校追究;如果学校睁一只眼闭一只眼,那么无事发生,但是学校追究起来了,那就不知道会有啥后果了。而且 Joshua 还不能这么搞,学校甚至禁止了 undergrad personal travel。但是 Joshua 看得很开,他说如果因为他而让我们不能去 Moscow 的话,他可以选择退出。这里我再讲一下 WF Moscow 的规则。WF Moscow 分为两个 division,分别叫做 championship 和 invitational。Championship 要求所有人都去 onsite,invitational 则是网络赛。如果一个队有人不去 onsite ,整个队就只能参加 invitational。所以如果我和 ysy 都去,而 Joshua 远程的话,我们队也只能打 invitational。

在某个时间点,我们需要做最后的决定是否前往 Moscow 的时候,由于我和 ysy 的 value function 不同,最后 ysy 决定不去了。去的话会冒一些 risk,有些 risk 大到我不敢写,而且 ysy 还要赶 ICLR,所以我还是可以理解的。尽管如此,我对他给出的一些理由(或者是玩笑)有些不理解……

然而我还抱有另外一丝希望。我觉得,WF 对我而言更重要的是那个气氛。如果我自费去 Moscow,参加和 championship 的活动,只不过打的是 invitational,我也能接受。于是我就自己联系了 ICPC manager,问作为 invitational 的参赛选手,我能不能也去 onsite 一趟。隔一阵之后,他们终于回复了。他们表示,我这个情况特殊,只有我一个 invitational 选手来问这个问题,他们可以给我一个 ICPC guest 的特殊身份,但是不是 invitational participant。良久之后,我突然意识才注意到,invitational 和 championship 不是同时的!invitational 发生在 9/30,但是 championship 在 10/1 才开始 register。我之前的设想基于一个假设,那就是这两个比赛同时进行,只不过排名方式不同而已。但是两者不同时进行的话,我去 Moscow 就只是一个看客了,这对我吸引力大为降低。感谢了他们好意之后,我决定还是不去了。

到这里,事情就急转直下。比赛前两三天,ysy 跟我说他有私事来不了了,教练也不知道我们到底发展成什么情况了,Joshua 本来就对此漠不关心(确实和他关系不大),而我呢?我失去了动力,甚至连 team ref doc 都没准备。比赛当天试图登录系统,无法登录,直接放弃治疗。你甚至都在 scoreboard 上找不到我们队。不过,本来我们就没有这个 slot,现在这样也不算亏了什么,只是有点可惜了。我有时候在想,如果和之前 Lucas 组队了,那么事情会有什么不同呢?