C++博客 :: 首页 :: 新随笔 ::  ::  :: 管理

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

Posted on 2010-08-21 21:47 Kevin_Zhang 阅读(269) 评论(0)  编辑 收藏 引用 所属分类: 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中。比如由于任意图匹配的Edmonds-Carp算法实现起来非常繁琐，使得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 permutations，则由于其理论的复杂而尚未出现在题目中。
图论中还有数不胜数的好的题目，比如linear time求minimum cut，还有Gomory-Hu tree的应用，这些也必将在不久的将来出现在ICPC题目中。
我认为将发生的另一个趋势是，随机算法，概率算法和近似算法会在ACM ICPC中占更大的比重，至于对于算法能力和代码能力考验的平衡，我个人非常喜欢数学和算法，我希望Final的题目能向中欧赛区的题目靠拢。
ACM ICPC考察的不仅仅是对经典算法的理解和掌握，创造算法的能力同样非常重要。学那么多算法，必须从中有所领悟，才能在赛场上有灵感去解决实际的问题。
如果大家有兴趣的话我可以找几个具体的问题详细分析，或是讨论一些具体的算法理论。同样的我也乐意分享一些ACM赛场上的经验，和在各大算法比赛中认识的一些有趣的人，和经历过的一些有趣的事。匆匆写完此文，疏漏之处在所难免，逻辑上也不甚连贯，希望大家见谅。 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理