欢迎光临
我们一直在努力

经验分享 | 钟知闲IOI2017参赛总结及OI生涯采访!

本文为IOI2017信息学国家队成员钟知闲发布的赛后总结及OI学习生涯分享!

这次IOI的规则和往年一样,分为两试,每试五小时三题,每题可以多次提交。不过从题型上来说,今年的题型并不像近几年的题那么传统,这一点我在练习赛时也有所意识:练习赛的4题,只有1题是传统题,其余3题则包含了交互题、通信题、提交答案题。

第一试的三题是nowruz,wiring,train,其中nowruz是提交答案题,另外两题是传统题。

第一试我的考场发挥就出了很大问题。首先我看完三题以后,根据往年经验,认为其中一定有简单题,可以很快过掉。于是我把nowruz放一边,先思考wiring的做法,然而一时并没有什么想法。随后我思考train的做法,由于数据范围是n*m复杂度可过的,我猜了一些性质以后设计了一个不会证明正确性的n*m复杂度的DP,经过优化常数之后得到了49分(所有部分分加起来),最后一个subtask答案错误。我想当然地认为算法是对的,是程序实现上的问题,于是花费大量时间调试程序无果,于是过了半场时间我仅有49分。

回头思考wiring,首先写了一个朴素程序提交,过了第一个subtask。然后我在朴素程序上加了个输出方案,通过随机生成较小数据观察方案,不久后发现了DP转移的规律,并且时间可以优化成线性。在我推出正确DP以后还剩1/3场的时间,本来完全能过掉wiring这题的,但我连犯了好几个错误:首先我推的DP方程里有一个数是常量被我误当成变量,于是要写斜率优化,当时感觉可能很难写,而直接用决策单调性的分治法或许很容易写。尽管我没有证明决策单调性是否正确,但我还是花了很长时间编写及调试决策单调性的程序,调到很迟才发现做法是错的。

这时候时间不多,看提交答案题nowruz还没交,赶紧给nowruz的每个测试点随机生成了一个解,得到60分。最后半小时决定打wiring的斜率优化做法,但由于时间不够,最后没有调出来,因此wiring最终仅得30分。

后来和另外几名国家队选手交流,不仅发现wiring被我做复杂了,还发现train我的做法是错的,但由于数据弱多过了一些subtask。当然前面的subtask不难设计出针对性算法解决。

第一试我一共139分,排名40,是一个很糟糕的成绩。wiring这题有大量选手都得到了满分,然而我却因为自己的失误而损失了70分,很痛心。仔细想想,这场我花了太多时间在调自己无法证明的算法上,而明明有靠谱的算法可以写。如果直接就写靠谱算法,不仅能拿到wiring的满分,还能省出时间做nowruz得到更多分。这个成绩我也没有太大的希望拿金牌了,很失落。如果真的是水平不够而没拿到金牌我还能接受,但会做的题却因为这种不应该犯的错而丢了,这就难以接受了。

第二试的三题是prize,simurgh,books,其中prize和simurgh是交互题,books是传统题。

这次我看完三题之后,先开始搞books,通过猜测性质并提交验证,在开场1小时的时候用贪心算法得到50分。拿到分以后开始攻交互题。

prize看完以后注意到题目中一个有用的性质,想到了用分治找出所有候选点验证的算法思路,但细节还是花了好一段时间才处理好,开场不到2小时得到了97分,我的程序在极端数据上询问次数比满分要求多一点。感觉为了几分继续花时间搞很不值得,得到97分就放弃了。

simurgh是一道有关生成树的交互题,经过一些尝试我仍然没能找到高效的算法,只会每次找一个环并确定环上的边是否属于生成树,这样实现得到了51分。之后我试图做出针对完全图的特殊数据,但没有成功。

三题都拿到保底分之后,我决定专攻books。之前的贪心通过了s=0的所有数据,但无法通过s>0的数据,因此我手工模拟了若干组s>0的数据之后发现了问题,意识到需要借助环之间的连通性来解决问题。之后我设计了一个n^2复杂度(且复杂度不满)的DP,拿到70分,最后一个subtask超时。随后我发现这个问题可能可以转成最小树形图来解决,但朱刘算法的复杂度也不能通过最后一个subtask。同时我尝试找出更多的问题性质,依然无果,最后这题70分收场。

第二试我一共218分,排名13。有十余人通过了books,在后来的讨论中我也发现最小树形图也不是正确思路,这题可以转成最短路来解决。当然我的水平差不多就是这个位置了。

两天总分357,排名25,以倒数第二名的成绩拿到了金牌。第一试损失的70分实在太遗憾了,如果多得70分排名就比较靠前了。当然尽管发挥不佳,最后也拿到了金牌,还是挺幸运的吧。

总结这次IOI,和前几年相比的最大特点是非传统题变多了,6道题有3道非传统题,对一些中国选手(尤其是我)不太适应。以及今年难度增大,没有那种送100分的题,选手总体得分偏低,分数线也偏低。值得一提的是提交答案题上次出现已经是5年前的事情了(IOI2012),今年的出现还是让人有些意外。这次IOI对不少选手来说考场策略更为重要,比如往年IOI一般每天有一道容易拿到100分的题,过掉这题以后剩下两题就可以每题花两个多小时研究,但今年IOI如果想先过掉一个题,可能要花很长时间才过掉,甚至还过不掉(比如我尝试过一试的train花了半场结果失败),留给其它题的时间就很少了。以及提交答案题主要考察近似算法,通过大量时间的尝试可以逐步提高得分,但考场上花太多时间会占用其它题的时间;而其它题做太久又会导致没时间尝试提交答案题,所以平衡传统题和提交答案题的时间分配也是不少选手需要考虑的。

以及传统题也和国内比赛有区别,IOI的传统题主要靠分析结论,如果深陷错误结论会浪费大量时间,得到关键结论以后实现并不难。比如一试的wiring我一开始以为n=m时最优解是将第i个红点和第i个蓝点匹配,因而之后基于这个结论的一系列思考全部是错的,所幸不久后发现了这个问题,但推出正解后又陷入了另一错误结论,即决策单调性,调这个错误做法导致我最后时间不够了。IOI允许多次提交的机制对解决结论题有不小的帮助,如二试的books我一开始猜测了一些错误结论,通过提交的反馈发现了结论的问题,最后得到了正确的70分程序。

我这次IOI没取得理想成绩的主要原因是一试考场策略出现问题,花费太多时间在错误算法上。如果我一试采用合适的策略,先每道题拿到保底分而不是鲁莽地认为有一道简单题要先过掉,之后不花大量时间在调试自己都无法证明的错误算法,而是直奔wiring的正确算法,得分就是稳定的,很可能就是另外一种结果了。二试我在拿到三题的保底分之后心态就好了很多,后面books多争取了20分最终惊险得到金牌。然而一试的糟糕成绩依旧是我一个永远的遗憾。

以及就是实力问题,除了一试wiring没看出斜率优化只要用前缀最值即可解决以外,一试的nowruz随机BFS能得到高分,但我没往这个方向尝试;二试的books有十余人满分,我没分析出正解因而没有得到最后30分。

今年中国队是近七年来成绩最差的一次,仅有2个金牌。外国选手的实力不可小觑,今年日本队前5名占了3名,尤其是Yuta Takaya通过了5个题,以极大的优势获得第一名。往年中国队经常都是总分第一,然而今年日本队总分超过了中国队,这也是我们需要反思的地方。相比于IOI的结论题,国内OI模板题和需要复杂算法/数据结构知识的题较多。尽管国内OI很发达,但赛制和题型方面和国际比赛差距还是比较大,当然这几年的命题水平也在进步。总之希望以后中国IOI成绩能恢复到原来的领先地位并保持下去。

最后,尽管我OI退役了,但是在计算机领域OI只是一个开端。这次IOI让我收获了不少经验,是我人生中一项宝贵的财富。

◆ ◆ ◆

OI生涯简介

喜欢编程、数学的初衷是为了更好在游戏中通关!

从小痴迷电脑,15岁考取福州一中,初中毕业已能基本完成高考的数学卷;16岁摘取全国信息学奥赛金牌,被清华大学提前锁定;17岁入选国家队,站上国际信息学奥赛最高领奖台,实现了福建省2011年以来国际中学生五大学科(数学、物理、化学、生物、信息学)竞赛金牌零的突破……

站上国际信息学奥赛最高领奖台

钟知闲,2000年出生于福清城关,老家在三山镇钟厝村,是一位畲族少年。

父亲是个公务员,经常使用电脑处理日常工作事务。作为“跟屁虫”,钟知闲很小就与电脑结缘,并深深地被电脑的奇特世界吸引。

7岁那年,他开始迷上电脑游戏,父母不但没有因为他的“不务正业”而训斥他,而是创造各种条件催发他的兴趣。

为玩好电脑游戏,他“爱屋及乌”,通过网络乐此不疲地自学数学、物理。到初中三年级,他基本上可以做完高考的数学卷。

2015年7月,钟知闲加入福州一中信息学兴趣小组,师从陈颖老师,他戒掉游戏,专注编程。3个月后,他满分拿到福州市NOIP2015初赛的一等奖,接着又取得NOIP2015福建省赛区一等奖。

2016年7月,16岁的他,以福建省A队队员身份参加全国信息学奥林匹克竞赛

(NOI2016)摘取金牌,成功签约清华大学,参加国家信息学奥赛队集训。

各类奖牌见证了编程少年的成长

2017年1月,在全国冬令营(WC2017)上,他“杀入”国家十五人候选队,后又入选国家奥赛队,成为“资历最浅”的队员(其他三名均为高三学生)。

2017年8月,在伊朗举行的第29届国际信息学奥林匹克竞赛上,他一举夺得金牌,实现了福建省2011年以来国际中学生五大学科(数学、物理、化学、生物、信息学)竞赛金牌零的突破。

按照规定,拿到国际金奖的选手不能再参加信息学系列比赛,钟知闲只好“退役”,但这个编程少年依然在孜孜不倦地编织着梦想……

游戏“苦玩家”

兴趣是最好的老师        这个“大神”级的人物,从小就痴迷电脑。

爷爷喜欢用电脑下象棋,但只要中途离开一下,回来就找不到鼠标箭头了,而无论怎么按鼠标,都没有反应。看着爷爷一头雾水,小家伙在一旁却乐不可支。“他只负责搞破坏,从来不管修复。”父亲对调皮的钟知闲很是无可奈何。

和许多别人家的孩子一样,钟知闲最开始也沉迷于游戏。只要一看到他在电脑前坐久了, 爷爷奶奶就开始担心,怕他玩游戏,荒废学业,不停地敲着边鼓不让他玩。

好在,开明的爸爸妈妈认为现在的孩子哪能不接触电脑,与其硬堵不如巧疏,于是尝试着引导钟知闲玩一些益智游戏,从游戏中找到知识点。

“不花钱把游戏打到最好!”在这一点上,钟知闲倒还不调皮了,并且真的就跟游戏铆上了劲。

“一直迷恋的奥拉星,连中考也只是暂离9天。”奥拉星是钟知闲最喜欢的游戏。但与众不同的是,除了玩和娱乐,他还苦苦地探究隐藏在游戏背后的秘密。

“游戏是个媒人,把他牵向数学。”在探究游戏的过程中,钟知闲遇到难题,就上网请教“高手”。“高手”们告诉他得用数学知识解决问题。从此,游戏就演变成的一道道数学题,让他更加流连忘返。

同时,他竞聘成为奥拉圈圈的第一任圈主,组织各种活动,组建工作室,撰写攻略,忙得不可开交,学中玩,玩中学,相得益彰。

当然,沉迷游戏也带来了一些“麻烦”。从小学到初中,他没少受老师的批评,父亲和爷爷还好几次被老师请到学校去。无外乎一个投诉:钟知闲又不做作业了。无可奈何的爷爷跟老师商量:“学校的数学作业他都已经会了,如果再去做这些对他来说很浪费时间。老师能不能免了他的数学作业,或者出一些能难倒他的数学题。”通情达理的数学老师同意了家长的建议。

爸爸妈妈或买或借,《Visual C++2010高级编程》、《Visual C#2010从入门到精通》等大部头专业书籍,摆上了钟知闲的书桌和床头。有了兴趣,他愣是把“干蜡”嚼出“蜂蜜”的甜味。

在城关小学,小知闲已经是计算机领域的“大玩家”:8岁顺利拿到全国计算机二级考试合格证书,创下了福清最小年纪的纪录;10岁参加全国计算机三级考试,只花了5分钟就“秒杀了”上机考试,考场工作人员还以为他弃考出场了,而陪考的父亲还在汗流浃背地答题;他用flash制作的《奥数计算器》、设计的网站《地球》先后在省市小学生竞赛中获奖;课余时间帮助老师制作课件……

爸爸调侃着说:“我并不支持他玩奥拉星,觉得比较弱智。”

“不是玩,是研究奥拉学科,这是一门集数学、物理和计算机为一体的学科。”钟知闲反驳道。

生于游戏,出于数学。与其说他喜欢游戏,不如说他喜欢数学。把游戏玩成学科,个中乐趣确非一般人可以理解。

编程“小狂人”

勤奋,是通往成功的捷径。信息学其实就是高效率的编程,给你一个要求,你编好程序,无论怎么天马行空,只要在规定时间内得出正确的结果,你就能得分。100个人可以有100种编法。

“你不觉得题解出来很爽吗?”   钟知闲说,当他瞄上了哪道题,就会毫不吝惜地倾注自己的全部心血,茶饭不思、夜不成眠,竭尽全力去解开,花上几个小时、甚至几天都在所不惜。

福州一中有个在线评测网站,当时翁家翌学长出了一套入门训练题,刚入门的钟知闲就跟这些题目干上了,他花了近40天成了唯一一个全部做完的学员。

爸爸说:“进入兴趣小组后,信息学就是他的全部,除了吃饭、睡觉,他的时间都在电脑前。周末没有了,节假日没有了。风雨窗外事,寒暑人不知。吃饭时,饭菜上桌,可他依然陷在题目里而无法抽身;出门旅游,别人游玩看风景,他捧着厚厚的本子做题。记得在泰山的一家宾馆,深夜,他终于在比赛结束前3秒干掉了最后一道题,笑得前俯后仰。”对钟知闲而言,思考是运动,也是休息;思考是学习,也是休假。他在“abc”、“123”的原野里采集着各种各样的花粉……

“一天解题十几个小时是家常便饭,他在解题上有着常人都难以理解的‘任性’和‘倔强’。”爷爷这样评价。

慧眼识珠的陈颖老师把一号电脑安排给他,告诉他:这电脑的前任主人是上一届的“清华爷”张瑞喆学长。从此,他的眼里只有一个目标叫做清华大学。

“知闲做事情经常慢半拍,无论什么考试,他常常最后一波交卷。他做的题也比别人少。别人想不出来,就去看题解,他不,非要自己想办法搞,直到竭尽全力才会去扫一下提示,然后继续自己搞。”爸爸说。武功的最高境界是看似有招却无招,而学习的最高境界是什么呢?

“最好是不知道公式却能使用公式、不记算法模板而能运用算法。”钟知闲说,“我要花大量时间去证明公式、推导算法,经过证明推导的,就不要强记了,如果没有论证出来,就不敢使用,因为有可能是错的。”

长期独立思考的习惯,让他在解题时,有了更多使用非标准的“曲线救国”的办法。“中考数学最难两道题有10分,大部分人都卡死了,我也不会标准方法,但我的‘歪解’拿了9.5分,没有这些分,也考不上福州一中。信息学题目的标准算法只是相对而言,有些题的非标准算法解题更快啊!”

机房里流行一句话:暴力出奇迹。

“总之,还是要多想题,多做题。以前觉得很高端的算法,学深学透了,也变得很水很暴力,当你做得足够多,消化得足够透,那么,所有题目都是水题,所有算法都是暴力。可是我还差得很远,还不够努力……”知闲一脸的憧憬。

对于拥有超人的天赋,钟知闲并不认同:“全国像我这种人很多,比我聪明的也很多,我只有比他们努力,才可能跟他们差不多,甚至超过他们。如果一天要是有28小时就好了,我可以多学一些东西。” 钟知闲以他日复一日的勤奋,玩奥拉星玩成了圈主,搞数学搞到了接近满分,而编程编到了国际赛场。

“钢丝”飞舞者

走在钢丝绳上,对面是彼岸,下面是地狱。

通过高中学科竞赛成功的几率是微乎其微的。信息学竞赛一个赛季两年,全国数万选手须经过地区选拔、省赛区复赛、省队选拔、清华集训、全国冬令营、集训作业、集训队互测、论文答辩、国家队选拔及国际奥林匹克竞赛等一系列比赛,每一次比赛一到两场,每一场是五个小时,任何一场失利,都可能前功尽弃而从头开始。如果到了高二依然不能突出重围,那就只好回归课堂参加高考,用仅剩的10个月时间学习3年的高中课程,而此时,同学们都已进入总复习。这是一条只许成功、不可失败的钢丝绳。

但小知闲毫不犹豫地踩上了这条钢丝绳,2015年7月21日,拿到福州一中录取通知单的钟知闲申请加入学校的信息兴趣小组。“首先是自己喜欢,还有就是如果学好了,就不用上语文课、不用写作文,甚至不要高考”。

他已经积累了很多编程的知识,但对于算法,却几乎是零基础的。而许多优秀的选手,是从初中开始学习训练,有的甚至小学就开始扬名。

但是,钟知闲的热情被彻底点燃,哪怕是被一同进入兴趣小组的同学、甚至是许多初中生狂虐。

爸爸至今还觉很神奇:“奥拉星,他折腾了5年,中考那么重要,好说歹说,才让他离开9天,是怎样的一股力量,让他连游戏都戒了?”

“在福州一中,我拥有其他中学很难拥有的自由平台,有了最了不起的陈颖老师,有了亦师亦友的陈俊锟同学,有了象董克凡、张瑞喆一样的优秀学长,还有了一群一起努力奋斗的朋友……”钟知闲自豪地说。

钢丝上的钟知闲飞舞起来了——

一年时间,福州赛区初赛、NOIP福建赛区复赛、全国冬令营(WC2016)、国家队选拔同步赛(CTSC2016)、亚太信息学奥林匹克(APIO2016)、清华大学夏令营(THUSC2016)、全国信息学奥林匹克(NOI2016)…….他有惊无险地拿下了所有参加比赛的金牌(或一等奖),也实现了保送清华大学的目标。但钢丝绳上的钟知闲,依然保持着飞舞的优雅身姿。

时间进入2017年,作为国家集训队员的钟知闲在全国冬令营(WC2017)上,成功进入国家十五人候选队。

然而,这一切似乎过于顺风顺水,此后的钟知闲,状态急转直下,焦躁情绪漫延。在国家队选拔赛(CTSC2017)的第二场,他几乎放弃努力,甚至希望自己被淘汰,但残酷的比赛也摧毁了其他选手,他成功晋级为国家队正式队员。离国际奥林匹克决赛只有一个星期时,他参加了NOI2017网上模拟赛,虽然没有什么实际意义,但是第四十多名的成绩令他抓狂,“不管怎么努力,却看着成绩往下掉,怎么办?”他情绪低落,几近崩溃。陈颖老师看出问题的根源,并非他水平不够,而是心态爆棚,越想考好,越不淡定,就考得越差。她平心静气地跟知闲谈气质比成绩更重要。

爸爸妈妈跟他聊些轻松的话题,给他做好吃的,还带他去欣赏了一场盛大的钢琴音乐会……

可是钟知闲依然忐忑不安,担心自己的极差状态浇灭了梦想,他说:“福州一中已经20多年没有拿到国际信息学奥林匹克金牌了。”7月28日,第29届国际信息学奥林匹克竞赛(IOI2017)如期在伊朗开幕。

“两天的赛程,每天5个小时3道题目,每题100分。”第一天竞赛,低迷状态延续,错误的考场策略让他损失惨重。临近岸边却在钢丝绳上打了个踉跄,引得家长老师一片惊呼,然而,此时的钟知闲已经调好心态、稳住身形,在第二个竞赛日上实现逆转,最终摘取金牌。

(本次参赛的中国队4名队员,左二为钟知闲)

对于这样一份近乎完美的成绩单,钟知闲并不满意,回望一路艰辛,后怕不断,“我还不够强,如果在冬令营上少赚了那些分,如果在CTSC上少过一个点……那就没戏了。”钢丝绳上看着舞姿翩翩,实则惊心动魄,而每年能从那条钢丝绳上走到彼岸的中学生,全国也仅寥寥几个。

畲族少年钟知闲,用键盘编织梦想,用鼠标点画未来,实现从游戏玩家到信息学大神的华彩转变,以亲身经历证明:只要努力,一切皆有可能!

本文内容参考自CCF官网及福建侨乡报。

往期精选内容

关注「信息学竞赛」

看更多信息学趣闻与知识

赞(19)
分享到: 更多

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址