斯坦福大學(xué)王穎 淺談ACM ICPC的題目風(fēng)格和acm比賽近幾年
斯坦福大學(xué)王穎 淺談ACM ICPC的題目風(fēng)格和acm比賽近幾年
ACM ICPC的比賽形式一般是五個小時八個題目,綜合考察選手的數(shù)學(xué)能力、算法能力、coding能力和debug能力,還有團(tuán)隊配合能力。數(shù)學(xué)方面主要強(qiáng)調(diào)組合數(shù)學(xué)、圖論和數(shù)論這三個方面的能力;而算法的覆蓋范圍很廣,涉及了大部分經(jīng)典的算法,和少量較前沿的算法。由于每道題目都需要通過所有的測試數(shù)據(jù)才能得分,并且需要精確解,這限制了Approximation algorithm在一些NP-hard的題目中的運(yùn)用,從而使得搜索和剪枝策略對于NP-hard的題目非常重要。
Final的題目和Regional題目的比較
ACM ICPC官方的正式比賽可分為World Final和Regional Contest兩種。Final的題目更加正統(tǒng)和嚴(yán)謹(jǐn),強(qiáng)調(diào)算法的綜合運(yùn)用,一個題目往往需要幾種算法的結(jié)合。從這幾年的final的題目看,final加大了題目的代碼量,對代碼能力的要求有所增強(qiáng)。而Regional的題目則更加靈活,同時每個賽區(qū)也有自己的出題風(fēng)格。歐洲賽區(qū)的題目以高質(zhì)量出名,對算法和數(shù)學(xué)的強(qiáng)調(diào)甚至超過了World Final;美國的賽區(qū)較多模擬題,強(qiáng)調(diào)代碼量。而亞洲則介于兩者之間,同時由于每年都有一些新的賽區(qū),所以并沒有很固定的模式。
下面淺談一下近幾年ACM ICPC的題目的覆蓋面。一些常規(guī)的算法和題型沒什么好講的,下面主要側(cè)重一些新穎的知識點(diǎn)或題型,或是一些較前沿的內(nèi)容。
數(shù)學(xué)的新題型
除了一些基本的組合數(shù)學(xué)和組合數(shù)論的問題,近年來概率和Combinatorial Game Theory的題目逐漸增多。很多有趣的題目都是以Markov Process為背景,需要用到一些相關(guān)的知識。
去年國內(nèi)杭州賽區(qū)的一個很有趣的題目是,給出一個字符集(比如{A,B,C})和一個字符串T(比如ACBBCAC),現(xiàn)在從一個空串S開始,每次等概率的添加A,B,C中的一個字符,直到T是S的一個子串。問得到的字符串S的長度的期望。這是一個典型的Markov Process,其解可以用生成函數(shù)很優(yōu)美的算出來。一個更有趣的版本是,假如還有另一個字串R,當(dāng)S中出現(xiàn)T或者R就終止,問終止在T和R的概率各是多少。這個問題在Graham, Knuth, 和Patashnik合著的Concrete Mathematics里面有詳細(xì)的分析,并有著一個優(yōu)美的結(jié)論。
Game theory方面,主要是經(jīng)典的combinatorial game theory而比較少Zero-sum game和Nash equilibrium的內(nèi)容。以前甚少選手知道的Sprague-Grundy Value現(xiàn)在已幾乎成了必備的知識。雖然大部分題目都是two-person perfect information impartial game,基本都可以用Sprague-Grundy Theorem解決,但也出現(xiàn)過misere play的情況。還有一些題目則是通過找規(guī)律和歸納解決。
Graph theory方面,上海賽區(qū)在多年前就出了一道Chordal graph recognition的題目,使得許多選手投入弦圖和區(qū)間圖的學(xué)習(xí),并了解到完美圖理論;IPSC有一年出了consecutive ones problem,從而引起了選手們對PQ樹和平面圖判定的關(guān)注。
除此之外,還有一些零散的non-trivial的題目,甚至是一些非常involved的題目。如劉汝佳給達(dá)卡賽區(qū)出的一道unbreakable tiling的題目。其中我非常喜歡的一個題目是四年前東北歐賽區(qū)的一個floodlight problem:平面上給出n個點(diǎn)代表n盞燈,每個燈可以照亮圓心角為2*∏/n的一個扇形區(qū)域。問怎樣控制這些燈的角度,使得可以照亮整個平面。
還有一些數(shù)學(xué)題則考驗創(chuàng)造能力。比如有一題:給出n,要求找出一個n*n的方陣,其中每個元素都是1到n之間的整數(shù),并且兩兩不等,同時使得每行、每列還有兩個對角線的和兩兩不等。這題的構(gòu)造頗為繁瑣,最簡單的方法是直接隨機(jī)生成再判定是否具有這個性質(zhì)。
近年來幾乎每年的final都有一道考察選手微積分能力的題目。而微分方程類題目較少。
大型線性方程組、復(fù)雜的矩陣代數(shù)、和特征值求解方面的題目較少。
算法的新題型
算法方面的增強(qiáng)主要體現(xiàn)在新的數(shù)據(jù)結(jié)構(gòu)不斷被選手所熟悉,和一些新領(lǐng)域的題目出現(xiàn)在ACM ICPC中。
數(shù)據(jù)結(jié)構(gòu)方面,一些特殊性質(zhì)的平衡樹逐漸被大家掌握,如splay tree,leftist tree等等。Interval tree則被廣泛用于計數(shù)。字符串方面,較容易實(shí)現(xiàn)的后綴樹組也逐漸被接受。
一些算法:網(wǎng)絡(luò)流方面,不少選手開始掌握push-relabel算法而放棄了經(jīng)典的ford-fulkerson算法;劉汝佳的書廣為傳閱后,不少選手又掌握了fractional programming和dinkelbach算法。目前能熟練實(shí)現(xiàn)linear programming的選手較少,但可以預(yù)計過一段時間這也會成為必備的技能。
計算幾何一直是ACM ICPC里面的難題。不僅編程困難,更由于精度問題導(dǎo)致非常難做對。計算幾何往往是在比賽時被放棄的題目。即使算法并不非常難,選手也不敢隨意去做。
一些零散的經(jīng)典內(nèi)容也被拿出來考察,如stable marriage,fft等。
總結(jié)和一些預(yù)計
基本上,實(shí)現(xiàn)起來不算太復(fù)雜的多項式時間復(fù)雜度的算法都可以出成一道ACM ICPC的題目。而出題者知識面的不停增長,也使得越來越多這樣的算法被包括。另一方面,隨著算法的發(fā)展,一些原本沒有簡單算法的題目也出現(xiàn)了新的解法,這樣的題目也被加入到ACM ICPC中。ACM ICPC經(jīng)過多年的積累有著大量的題目,其覆蓋面也是非常之廣。
斯坦福大學(xué)王穎 淺談ACM ICPC的題目風(fēng)格和acm比賽近幾年
可以預(yù)見一些新的優(yōu)秀的算法將陸續(xù)出現(xiàn)在ACM ICPC中。比如由于任意圖匹配的Edmonds-Carp算法實(shí)現(xiàn)起來非常繁瑣,使得ICPC中一直不出現(xiàn)任意圖匹配的題目(即使有也是規(guī)模非常?。?。而Vijay Vazirani的論文<