登山之道
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赛场上的经验,和在各大算法比赛中认识的一些有趣的人,和经历过的一些有趣的事。匆匆写完此文,疏漏之处在所难免,逻辑上也不甚连贯,希望大家见谅。
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
ACM中无输入结束提示时如何判断到达EOF
ACM题目的风格和近几年题目的发展
递归方程组解的渐进阶的求法——差分方程法
算法的复杂性
ACM的算法(觉得很好,有层次感)
见过的一个计划
算法书建议收藏
ACMer应具备的能力
pku1004
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © Kevin_Zhang
日历
<
2010年8月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
常用链接
我的随笔
我的评论
我参与的随笔
随笔分类
数据库(1)
ACM基础知识(9)
ARM(2)
C/C++(12)
DOS(1)
Google Map API
Heritrix(1)
IT News(22)
JAVA(3)
Jsp
Linux(9)
Lucene(1)
PHP(6)
Python
Tree
Trie树(1)
博弈
动态规划(1)
回溯
汇编
计算几何(1)
模拟(4)
排序(2)
嵌入式
数据结构(2)
数论(2)
数学(3)
搜索(2)
搜索引擎(12)
随机数
贪心(1)
图论(1)
图形学(1)
万花筒(22)
网络流
硬件(1)
随笔档案
2011年6月 (5)
2011年5月 (22)
2011年4月 (24)
2010年12月 (1)
2010年11月 (13)
2010年10月 (7)
2010年9月 (14)
2010年8月 (52)
2010年7月 (9)
文章分类
ACM题目分类(13)
C
C#
C++
DP动态规划
JAVA
LUNIX
Python
博弈
计算几何
模拟
数论(1)
搜索(1)
贪心
图论
文章档案
2010年8月 (4)
2010年7月 (22)
程序的灵魂--算法
沙场秋点兵,壮士凯歌还
北大POJ
他山之石,可以攻玉
围观强人
搜索
最新评论
1. re: Lucene入门级笔记五 -- 分词器,使用中文分词器,扩展词库,停用词
54544554
--回家看回家看
2. re: 水
评论内容较长,点击标题查看
--Jason Huang
3. re: 10项技能让前端开发者价值百万!
评论内容较长,点击标题查看
--BURKERosie25
4. re: (转载)ACM经历总结[未登录]
谢谢
--xingyezhi
5. re: 世界头号营销大师们的营销素质
大道至简,殊途同归,值得借鉴。
--Kevin_Zhang
阅读排行榜
1. Java动态数组的用法详解(12179)
2. Lucene入门级笔记五 -- 分词器,使用中文分词器,扩展词库,停用词(3463)
3. 用scanf输入字符串空格不识别??(2047)
4. php java交互 php/java bridge (1914)
5. Java split分割字符串的用法详解(1777)