当前位置:首页 > 芯闻号 > 充电吧
[导读]斯坦福大学王颖 浅谈ACM ICPC的题目风格和acm比赛近几年ACM ICPC的比赛形式一般是五个小时八个题目,综合考察选手的数学能力、算法能力、coding能力和debug能力,还有团队配合能力。

斯坦福大学王颖 浅谈ACM ICPC的题目风格和acm比赛近几年


ACM ICPC的比赛形式一般是五个小时八个题目,综合考察选手的数学能力、算法能力、coding能力和debug能力,还有团队配合能力。数学方面主要强调组合数学、图论和数论这三个方面的能力;而算法的覆盖范围很广,涉及了大部分经典的算法,和少量较前沿的算法。由于每道题目都需要通过所有的测试数据才能得分,并且需要精确解,这限制了Approximation algorithm在一些NP-hard的题目中的运用,从而使得搜索和剪枝策略对于NP-hard的题目非常重要。


Final的题目和Regional题目的比较

ACM ICPC官方的正式比赛可分为World Final和Regional Contest两种。Final的题目更加正统和严谨,强调算法的综合运用,一个题目往往需要几种算法的结合。从这几年的final的题目看,final加大了题目的代码量,对代码能力的要求有所增强。而Regional的题目则更加灵活,同时每个赛区也有自己的出题风格。欧洲赛区的题目以高质量出名,对算法和数学的强调甚至超过了World Final;美国的赛区较多模拟题,强调代码量。而亚洲则介于两者之间,同时由于每年都有一些新的赛区,所以并没有很固定的模式。


下面浅谈一下近几年ACM ICPC的题目的覆盖面。一些常规的算法和题型没什么好讲的,下面主要侧重一些新颖的知识点或题型,或是一些较前沿的内容。


数学的新题型

除了一些基本的组合数学和组合数论的问题,近年来概率和Combinatorial Game Theory的题目逐渐增多。很多有趣的题目都是以Markov Process为背景,需要用到一些相关的知识。

去年国内杭州赛区的一个很有趣的题目是,给出一个字符集(比如{A,B,C})和一个字符串T(比如ACBBCAC),现在从一个空串S开始,每次等概率的添加A,B,C中的一个字符,直到T是S的一个子串。问得到的字符串S的长度的期望。这是一个典型的Markov Process,其解可以用生成函数很优美的算出来。一个更有趣的版本是,假如还有另一个字串R,当S中出现T或者R就终止,问终止在T和R的概率各是多少。这个问题在Graham, Knuth, 和Patashnik合著的Concrete Mathematics里面有详细的分析,并有着一个优美的结论。


Game theory方面,主要是经典的combinatorial game theory而比较少Zero-sum game和Nash equilibrium的内容。以前甚少选手知道的Sprague-Grundy Value现在已几乎成了必备的知识。虽然大部分题目都是two-person perfect information impartial game,基本都可以用Sprague-Grundy Theorem解决,但也出现过misere play的情况。还有一些题目则是通过找规律和归纳解决。


Graph theory方面,上海赛区在多年前就出了一道Chordal graph recognition的题目,使得许多选手投入弦图和区间图的学习,并了解到完美图理论;IPSC有一年出了consecutive ones problem,从而引起了选手们对PQ树和平面图判定的关注。

除此之外,还有一些零散的non-trivial的题目,甚至是一些非常involved的题目。如刘汝佳给达卡赛区出的一道unbreakable tiling的题目。其中我非常喜欢的一个题目是四年前东北欧赛区的一个floodlight problem:平面上给出n个点代表n盏灯,每个灯可以照亮圆心角为2*∏/n的一个扇形区域。问怎样控制这些灯的角度,使得可以照亮整个平面。

还有一些数学题则考验创造能力。比如有一题:给出n,要求找出一个n*n的方阵,其中每个元素都是1到n之间的整数,并且两两不等,同时使得每行、每列还有两个对角线的和两两不等。这题的构造颇为繁琐,最简单的方法是直接随机生成再判定是否具有这个性质。



近年来几乎每年的final都有一道考察选手微积分能力的题目。而微分方程类题目较少。


大型线性方程组、复杂的矩阵代数、和特征值求解方面的题目较少。


算法的新题型
算法方面的增强主要体现在新的数据结构不断被选手所熟悉,和一些新领域的题目出现在ACM ICPC中。



数据结构方面,一些特殊性质的平衡树逐渐被大家掌握,如splay tree,leftist tree等等。Interval tree则被广泛用于计数。字符串方面,较容易实现的后缀树组也逐渐被接受。


一些算法:网络流方面,不少选手开始掌握push-relabel算法而放弃了经典的ford-fulkerson算法;刘汝佳的书广为传阅后,不少选手又掌握了fractional programming和dinkelbach算法。目前能熟练实现linear programming的选手较少,但可以预计过一段时间这也会成为必备的技能。


计算几何一直是ACM ICPC里面的难题。不仅编程困难,更由于精度问题导致非常难做对。计算几何往往是在比赛时被放弃的题目。即使算法并不非常难,选手也不敢随意去做。


一些零散的经典内容也被拿出来考察,如stable marriage,fft等。



总结和一些预计

基本上,实现起来不算太复杂的多项式时间复杂度的算法都可以出成一道ACM ICPC的题目。而出题者知识面的不停增长,也使得越来越多这样的算法被包括。另一方面,随着算法的发展,一些原本没有简单算法的题目也出现了新的解法,这样的题目也被加入到ACM ICPC中。ACM ICPC经过多年的积累有着大量的题目,其覆盖面也是非常之广。



斯坦福大学王颖 浅谈ACM ICPC的题目风格和acm比赛近几年
可以预见一些新的优秀的算法将陆续出现在ACM ICPC中。比如由于任意图匹配的Edmonds-Carp算法实现起来非常繁琐,使得ICPC中一直不出现任意图匹配的题目(即使有也是规模非常小)。而Vijay Vazirani的论文<

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭
关闭