荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: German (Ich), 信区: ACMICPC
标  题: 浅谈ACM ICPC的题目风格和近几年题目的发展zz
发信站: 荔园晨风BBS站 (Sun Apr  2 14:55:17 2006), 站内


浅谈ACM ICPC的题目风格和近几年题目的发展



斯坦福大学 王颖



ACM
ICPC的比赛形式一般是五个小时八个题目,综合考察选手的数学能力、算法能力、coding能
力和debug能力,还有团队配合能力。数学方面主要强调组合数学、图论和数论这三个方面
的能力;而算法的覆盖范围很广,涉及了大部分经典的算法,和少量较前沿的算法。由于每
道题目都需要通
过所有的测试数据才能得分,并且需要精确解,这限制了Approximation algorithm在一些N
P-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和Nas
h 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都有一道考察选手微积分能力的题目。而微分方程类题目较少。



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



算法的新题型



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



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



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



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



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



总结和一些预计



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



可以预见一些新的优秀的算法将陆续出现在ACM ICPC中。比如由于任意图匹配的Edmonds-Ca
rp算法实现起来非常繁琐,使得ICPC中一直不出现任意图匹配的题目(即使有也是规模非常
小)。而Vijay Vazirani的论文<<matching is as easy as matrix
inversion>>中给出了一种通用的通过矩阵求逆而求各种匹配的算法,虽然该算法实现起来
有一个难点,但相信将会被一些选手采用,从而出现一些任意图匹配的题目,甚至更困难的
exact match(该问题目前没有deterministic polynomial-time
algorithm,但用上面的方法可以得出一个概率算法)。



而一些新的领域也必将给ACM ICPC的出题者带来灵感。例如已有越来越多Bio-informatics
的题目在ICPC中出现。一些有着多项式算法的好题目,如inversion distance of signed p
ermutations,则由于其理论的复杂而尚未出现在题目中。



图论中还有数不胜数的好的题目,比如linear time求minimum cut,还有Gomory-Hu tree的
应用,这些也必将在不久的将来出现在ICPC题目中。



我认为将发生的另一个趋势是,随机算法,概率算法和近似算法会在ACM ICPC中占更大的比
可以预见一些新的优秀的算法将陆续出现在ACM ICPC中。比如由于任意图匹配的Edmonds-Ca
rp算法实现起来非常繁琐,使得ICPC中一直不出现任意图匹配的题目(即使有也是规模非常
小)。而Vijay Vazirani的论文<<matching is as easy as matrix
inversion>>中给出了一种通用的通过矩阵求逆而求各种匹配的算法,虽然该算法实现起来
有一个难点,但相信将会被一些选手采用,从而出现一些任意图匹配的题目,甚至更困难的
exact match(该问题目前没有deterministic polynomial-time
algorithm,但用上面的方法可以得出一个概率算法)。



而一些新的领域也必将给ACM ICPC的出题者带来灵感。例如已有越来越多Bio-informatics
的题目在ICPC中出现。一些有着多项式算法的好题目,如inversion distance of signed p
ermutations,则由于其理论的复杂而尚未出现在题目中。



图论中还有数不胜数的好的题目,比如linear time求minimum cut,还有Gomory-Hu tree的
应用,这些也必将在不久的将来出现在ICPC题目中。



我认为将发生的另一个趋势是,随机算法,概率算法和近似算法会在ACM ICPC中占更大的比
重,至于对于算法能力和代码能力考验的平衡,我个人非常喜欢数学和算法,我希望Final
的题目能向中欧赛区的题目靠拢。



ACM ICPC考察的不仅仅是对经典算法的理解和掌握,创造算法的能力同样非常重要。学那么
多算法,必须从中有所领悟,从而在赛场上有灵感去解决实际的问题。



如果大家有兴趣的话我可以找几个具体的问题详细分析,或是讨论一些具体的算法理论。同
样的我也乐意分享一些ACM赛场上的经验,和在各大算法比赛中认识的一些有趣的人,和经
历过的一些有趣的事。匆匆写完此文,疏漏之处在所难免,逻辑上也不甚连贯,希望大家见
谅。



--

※ 修改:·German 于 Apr  2 14:55:20 修改本文·[FROM: 192.168.111.223]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.223]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店