注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

二不小心

永做第二,学会说不,保持年轻,真心做人

 
 
 

日志

 
 

从交换生经历谈中美信息学竞赛环境体制的差异-转  

2017-08-17 09:06:06|  分类: 北京高考演义 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
大学自主招生考试,是一个比重逐渐扩大的入学渠道,大有与统招分庭抗礼的意思,而竞赛成绩几乎是所有自主招生的硬指标。关注这方面的信息,也是如坠迷雾之中,慢慢来了。这篇别人的文章,介绍了信息学竞赛的基本流程,算是基础知识收集中。
从交换生经历谈中美信息学竞赛环境体制的差异-转 - 二不小心 - 二不小心
 
从交换生经历谈中美信息学竞赛环境体制的差异

六月初结束的美国信息学奥林匹克国家队选拔赛中,我强势而稳定的拿到了第一名,并进入了IOI2017美国国家队(因此被众多OIer们戏称为“美国队长”)。考虑到我长达七年的OI生涯只剩最后一场IOI了,也不知IOI之后还有没有心情写这些内容,而且觉得同时经历过中美两国国家队选拔的情况应该极少出现,便想结合我在美国的经历谈谈中美信息学竞赛的差异,也算是给自己大学前最后一年的漂泊一个交代。

(然后就被我的拖延症推到了现在才发……)

一、人数决定的选拔制度

且不用谈信息学,中国的学科竞赛,其他所有国家相比,最大的特点就两个字,人多——无论是把竞赛当兴趣的,奔着省级奖项,谋求大学政策的,还是冲击集训队乃至国家队的,人数都远远多于其他国家。我曾开玩笑说过,如果信息学国家队不是4人而是100人,中国甚至可以与其他所有国家联合队伍对抗。

人多使得中国信息学竞赛从不缺乏高手,很大程度上造就了中国队强大而稳定的特点,但也带来了新的难题——选拔制度的设计。

从数万信息学竞赛学习者中选拔出四个人代表中国参赛绝非易事,为此中国队的选拔在我的印象中是最复杂的,真可谓是层层选拔,逐步淘汰。

试想你是一个OI高手,要想从中国参加IOI,那么你首先需要参加每年11月在各省举办的全国信息学奥林匹克分区联赛(NOIP),在联赛中获得优异成绩后(一般二等奖或以上)可参加次年二月至四月由各省组织命题的省队选拔赛(省选),把联赛成绩与省选成绩加权求和并排名决出省队(AB类名额),同时还会发放若干CD类名额,ABCD四类名额有资格参加七月举办的全国信息学奥林匹克竞赛(NOI),其中ABC类具有获奖资格,NOI参赛人数还在逐年增加,今年已经增加到了400多人。NOI现场考试选出前50名作为国家集训队,这50名集训队成员具有保送资格。

经历过这一年的选拔,你终于熬到了集训队,可是你发现,集训队不是选拔的尽头,而是国家队选拔的开始。IOINOI时间差不多,都在七八月份,显然50名集训队员决出国家队参加当年的IOI已然不可能,所以你还要参加持续将近一年的国家队选拔,以参加下一年的IOI

从集训队开始的国家队选拔分为三轮现场比赛,清华集训,冬令营(WC),和国家队选拔赛(CTSC),WC后会把清华集训和WC加权求和选出前15名作为国家候选队,五月份举办的CTSC会从15名候选队员中再取出前四成为国家队员。

所以,如果你想参加IOI2017的话,得从NOIP2015开始,每一场比赛都要认真对待,保证稳定发挥,才有可能进入IOI2017的国家队。为什么说有可能呢?这还涉及到赛制和命题的问题,我们后面会提到。

那不妨来看看美国队的选拔制度,USACO每学年举办12月,1月,2月三场月赛和四月的US Open,这四场比赛都是线上比赛。接着,按照US Open成绩为主,其他三场月赛参考的标准,教练会联系前25名选手参加一般五月底举办的USACO Camp即国家队选拔训练营。USACO Camp有六场比赛,分为两个组Holsteins(H)Guernseys(G)H组一般是第二次参加USACO Camp的或者水平较高的选手,会参加全部的比赛并从中选出国家队,而G组在其中四场比赛的时候会去听由教练组织的关于OI的讲座。

两种选拔制度相较之下如何呢?

主观来说,中国的选拔结构是要远远优于美国的,从选手训练的角度来看,从NOIPCTSC,每层选拔对知识点和思维能力的要求都层层递增,而且选拔周期长。虽然这种选拔是庞大的参赛人数导致的,但的确对于批量培养“高手”有极高的正面作用。若是选手有能力认真训练,甚至可以随着比赛难度的加强逐步提升自己的实力。今年中国队队员钟知闲就是一个例子。

再看美国队,从我自己的体验来看,四场在线比赛的难度差异不大,三道题的难度分布从NOIP到省选不等,USACO Camp难度逐天增加,在省选到NOI难度区域内徘徊,最后一天难度(或者说代码量)很大一般防止满分出现(比如我就被一道教练写了12K,500行的数据结构题狙击了)。这种选拔结构难度跨度小,周期只有一年,主要作用在于选出国家队,在指导选手平时训练中效果甚微(今年USACO试图在指导平时训练方面加大努力),这也对美国队不同的训练方式有一定影响,这个我们后文会提。

要说相比美国队,中国队选拔制度的一大弊端,便是关键比赛题目少,分值大,既无法覆盖知识点,也加大了比赛的不确定性。

中国的50名集训队是NOI两天六道题直接选出来的,5015中有40%的分值分布在仅有三道题而且一般都是反人类的冬令营中,而有12道题目的相对可做的清华集训总共才占50%,而在更为激烈的十五进四中,仅有两天六道题的CTSC足足占到总分的50%,可以说几乎是按照CTSC为第一关键词,之前成绩为第二关键词的排序,这会给选手极大的压力,使得CTSC不确定性非常大,第一天最高分二试跳水的事情时有发生。

反观美国队,USACO Camp需要结合四场在线赛成绩选前25,在人数不多的美国进Camp并不十分困难,而USACO Camp有六天18道题,几乎会覆盖IOI中所有知识点,且每一天比重相同,高水平选手能够一点一点的拉开差距,到了第五天一般国家队前三名就几乎确定了,除了在分数线边缘挣扎的四五名之外,大家考起来都没有什么压力。

 

二、挑战性而不稳定的赛制

但是关键比赛分值的设计,还不足以让中国选拔赛的不稳定性如此之大。影响更大的,除了命题外,还有赛制。

NOIPCTSC,中国队选拔一直采用的是“比赛时无反馈”的COI赛制,即比赛时不能实时提交查看评测结果,而是赛后统一评测。由于OI题是机器评分,再小的错误都有可能造成整题零分。这让COI赛制比赛中,细节错误造成的分数波动非常大,导致检查和对拍的重要性也被加大。

相信绝大多数中国选手比赛中都常常会碰到艰难的选择,是去做新题还是对拍已经写好的题,去做新题可以拿更多的分,或检查已写好的题则可以让分拿的更稳,如果选择不好会很大程度上影响成绩,甚至导致比赛心态崩盘。

掌控这种比赛,需要大量的比赛经验做支撑。选手需要对自己代码速度,准确度有细致的了解和充分的训练,才能在比赛中管理和利用好自己的时间,同时要有很强的数据生成能力和调试能力。就我而言,这些能力是长达一年将近100场模拟考试之后才逐渐成型的。由于赛制的原因,这些能力恰恰是美国OI选手最欠缺的。

再来看美国队,美国队从在线比赛到USACO Camp,采用的都是IOI赛制,即选手可以在比赛时提交评测直接获得最终评测结果。这种方式有一个好处,那便是与IOI接轨,直接选出在这种赛制下表现最好的选手。同时,可以锻炼选手掌握在IOI赛制下才能使用的比赛技巧,举个例子,今年Camp第三天第二题,我最终的做法是约75%概率正确的算法,针对10组测试数据我提交了七次终于获得满分,这在需要反馈的得分技巧在COI赛制中是不可行的。三个小时的比赛中这道题花费了我将近两个小时,如果平时我有针对IOI赛制进行充分的训练,相信这个时间能大大缩短。

美国OI选手对提交获得反馈机会的利用要远强于中国OI选手,几乎所有的美国选手在Camp中每一题的提交次数都要远多于我,抛开训练方式和实力的差异,在比赛中不吝于自己的提交确实会获得更多重要的信息,甚至对于某些题目可以拿到数据的特点乃至数据本身。

但其实,这两种赛制在指导训练的过程中都有其弱点。COI赛制会让选手依赖于对拍,IOI赛制会让选手依赖于大量提交获得反馈。但在IOI中,由于允许及时提交,对拍的作用被大大削弱,变成是一种在只某些时候必须的查错方式,而大量提交获得反馈对题目本身依赖性很大,所以大多数美国选手比赛成绩极不稳定。

从训练的角度而言,我更加推荐得分与解题用时和提交次数都相关的Codeforces(CF)Topcoder(TC)赛制,平时多做CFTC的比赛能提升综合算法竞赛能力。去年IOI世界冠军金策在这两个网站上都位于世界前列,所以他无论是COI还是IOI赛制都能稳定发挥出自己高超的水平。

这里插一句,因为CF/TC赛制中时间管理和利用的方法完全不同甚至相悖于IOI,所以一般只能用于平时训练,不能用在IOI国家队选拔上。

美国队今年也开始加强对于平时训练的指导,如果能加入CF/TC/COI赛制,应该也能让美国队选手减少对及时提交的依赖。中国计算机学会(CCF)近期似乎表示赛制将开始逐步加入IOI赛制,或许能弥补中国选手IOI赛制比赛技巧的欠缺,关于这一点,我倒是觉得比较好的做法是,NOI及以下使用COI赛制,在国家队选拔中加入部分IOI赛制,一方面让选手熟悉IOI赛制和比赛技巧,另一方面能保持在集训队之前学习中打下代码速度,准确度,调试能力等基础。

 

三、命题特点与知识树

无论是选拔制度,还是赛制,都可以设计针对性的训练,算法竞赛核心的部分还是需要命题去体现。同时,命题就是选手训练的指挥棒,命题方向很大程度上能决定选手的知识树。虽然目标都是训练和选拔IOI选手,但中美在命题上依旧有着不小的差异。

如果以IOI命题为标准,中美两国在选拔赛命题上都差的很远,可以说弊端都不小,而且有互相学习的必要。

中国的出题人主要是往届选手,一般为大学在校学生。出题人主业是学习,可以明显感觉到并没有在出题上投入足够的时间,除了真的有很妙很适合IOIIdea投题的,很多出题人,有的为了完成任务又为了保证题目难度,出一些与算法竞赛格格不入的偏难怪题,在非算法思维的地方设置知识障碍或者强行加大工作量,有的因为自己在大学中有正在研究的内容,以一己之快强行向大家灌输自己的独特见解,出的题与IOI宗旨毫不相关甚至背道而驰。典型的类型有:误差分析数学题,NOIP十合一提答题,依靠人类智慧的搜索题,造计算机题,卡常数题等。这种现象在NOI以上比赛中尤其严重,让人感觉出题人的目的不是为了选拔最优秀的选手,而是要把学生考倒以显示自己的高明,或者强迫选手来学习自己研究的内容。从另一个角度来说,中国集训队员冲击国家队选拔赛的结果,掌握在很多水平远不如集训队员甚至对OI的理解都有偏差的出题人手中。

那么美国队选拔呢,美国队选拔命题由十个左右的教练负责,教练也是以前USACO的选手,一般已经大学毕业。我与美国教练交谈过,美国教练一般平时就注意积累Idea,当需要命题时拿出几个比较有趣的Idea继续思考和转化,最终形成题目。于是美国命题难度虽然不高,涉及的知识点也都严格在不多的IOI考试大纲里(中国OI早就严重超纲了),但是几乎每个题都有自己的Idea,需要选手去转化模型,分析模型的性质。而由于美国队的命题都是教练独立思考或少数几个教练讨论的结果,且没有中国庞大的竞赛人口基数可供互相交流,美国命题中很妙的Idea往往都是中国OI中的“套路”题,USACO Camp的难题中超过一般我都在中国见过一模一样或者模型差不多的原型。同时造成大多数美国队员对OI新科技的掌握至少落后中国队三年。我在Camp期间发现他们对二维区间问题还在学习二维线段树,而在中国早就使用效率更高更灵活的可持久化数据结构+扫描线或者嵌套来解决了。

中国OI人数基数庞大,高手众多,就算选拔赛命题质量堪忧,高手一般还是能显示出自己出类拔萃的地方,除了顶尖高手稳进国家队之外,另外两三名选手必然水平也不差,造成了选拔的结果在世界上仍颇具竞争力的假象。这也使得命题方向的偏离没有得到足够的关注,在近年似乎还有抬头的趋势。连美国队教练都很好奇近年中国队选拔赛又弄出了什么糟糕的东西,还要和往年相比看看是不是更加糟糕。

中国OI命题的另一个问题在于题目类型的缺失,近年IOI的交互题比重越来越大,而中国自2006年以后,直到近年才有交互题在清华集训中出现,而某些渐渐成为命题的主流的非传统题例如通信题,则根本没有涉及。IOI中出现过几次的提交答案题在中国队选拔中经常出现,不过我觉得此提交答案非彼提交答案。我们应该学习IOI提交答案考察的思想,而不是照搬其形式,或者为了所谓的分数分布均匀强行加入比赛。IOI的提交答案主要考察观察数据和NPC问题求近似解的能力,而近年中国队选拔的提交答案都是NOIP十合一或者造计算机的类型,属于前期得分与投入时间成正比,后期有知识壁垒的类型,对IOI的提答几乎起不到锻炼作用。不过近两年清华集训加入了交互题可以看出CCF在丰富题目类型上的努力。

再看美国队,我翻了前两年Camp的题目,交互题占到四分之一以上,而且每年都有一道通信题,今年的最后一天甚至加入了并行计算,并行计算已经加入了GCJ,而且从目前来看很可能将来成为算法竞赛的一个重要部分。不过暂时没有发现美国队选拔赛中出现提交答案,可能是USACO需要补充的题目类型。

四、训练模式

虽然本质上还是人数的差异,中美OI选手训练模式确实有很大差别。

美国学生的入门多是自己看书学习语言基础,而中国学生多是老师或者学长带,这种差别实则源于训练模式的不同。中国学生的训练往往以学校为单位,OI选手的成长过程中所在学校的资源极为重要,选手们在与同学的合作与竞争中成长,所以时常会出现一个学校一个很短的时期内涌现出一大批高手的现象(例如14-16年的绍兴一中)。中国学校培养OI选手的动力往往来自优秀OI成绩对学生升学的帮助,例如进国家集训队保送清华北大,NOI奖牌也可以自主招生降分等。

在美国几乎没有专门搞OI的学校,一个国家队选手告诉我他连教练都没有,一般是自己在CodeforcesTopcoder等网站上找题做,来过一次USACO Camp之后就可以由USACO教练或者学长在线组织训练,推荐题目等。但总体而言选手相对自由,训练效率比中国低很多。

然而即使在中国,高水平的选手的训练仍然主要来自于自己上网做题,学校的训练更多是起到保持竞赛状态和熟悉赛制的作用。从美国队选手的水平可以看出,只要合理训练,网上的资源足以把自己提升到IOI金牌水平,然而对于中国非高端选手来说语言成了他们获取互联网资源的第一障碍,很多选手上高中之后仍然有英文题面阅读障碍或者不愿意阅读英文,TopCoder上很多很优秀的题目也配有很详细的题解,却无法被他们直接吸收,从这点上来看,中国以学校为单位由教练或者校内高手搜集整理英文资源给一般选手使用,是非常合理的。事实上,很多校内模拟赛,校际联合训练的题目,都来自CFTC等网站。

目前来看中国这样的模式的主要缺点有两个方面,一是部分学校之间有较强的竞争关系(例如同一个省),会影响选手们互相的交流,导致每个学校都有其知识树上的优势和弱点。二是长期学校担负起训练任务使得CCF反而在这块抓的不紧,对集训队的全部训练仅仅停留在集训队作业的100道题(还有很多人本来就做过一大半),和候选队作业的自选五道题,这对于IOI来说是远远不够的。此外,学校训练一般以集训队为目标(可以保送),所以极少会加入IOI赛制的训练,而在IOI之前针对国家队员CCF从未举办过一次完全仿真的IOI模拟赛(即5个小时有反馈赛制下解3个有部分分的问题),可想而知国家队选手IOI比赛经验的欠缺。

五、总结

总体来说,由于人数,学习动力,训练模式,和中国队OI科技的领先确实造成了中国高端选手从知识水平到人数都超过美国队的后两名,而且由于题做得多,平时比赛的成绩比美国队强一大截。不过到了IOI,高质量的命题和“套路”的极少出现,会把差距缩小,有的年份美国队有和中国队一战的可能。从训练强度的角度上来说,中国队和美国队都远远达不到把IOI当“奥林匹克”竞赛的程度,美国更多的是教练资源的缺失,而在中国其实有可能是选手在集训队之前练的够多了之后也并没有过度训练的必要,把时间放在提前学习大学内容或者接触科研和工业上,可能更有价值。

P.S交换期间大部分时间是在学校学习和参加学校课外活动,对两国的赛制了解也许不尽全面,粗浅认识,就当大家分享吧。

注:

作者简历(大概描述一下我对中美信息学竞赛的参与程度)

罗哲正,2014-2017就读安徽师范大学附属中学,2016-2017学年度在美国麻塞诸塞州(Massachusetts),纪念碑山地区学校(The Monument Mountain Regional High School)参加AFS国际文化交流项目。

IOI2016,2017中国国家集训队成员,IOI2016国家候选队成员,CTSC2016最终总分第六,

IOI2017清华集训集训队第一(参加的最后一场国内比赛),后因赴美参加国际文化交流项目无法继续在中国参赛,缺席2017年冬令营而不得不放弃中国队选拔转而参加美国队选拔。

USACO2016-2017全赛季,除国家队选拔训练营(USACO Camp 2017)最后一天考试之外,均获得满分第一名,最终以总分第一名成绩入选IOI2017美国国家队。

IOI2017UPDATEIOI2017金牌第三名。

专有缩写解释:

OI=Olympiad in Informatics:信息学竞赛

NOI=National Olympiad in Informatics:全国信息学奥林匹克竞赛

NOIP=NOI in provinces:全国青少年信息学奥林匹克分区联赛

WC=Winter Camp:全国青少年信息学奥林匹克冬令营

CTSC=Chinese Team Selection ContestIOI中国国家队选拔赛

COI=Chinese OI:中国信息学竞赛

USACO=USA Computing Olympiad:美国计算机奥林匹克组织

CCF=China Computer Federation:中国计算机学会

 


  评论这张
 
阅读(65)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017