久久精品成人免费看,国产香蕉久久精品综合网,97精品伊人久久大香线蕉app

ACM題目的風(fēng)格和近幾年題目的發(fā)展

Posted on 2010-08-21 21:47 Kevin_Zhang 閱讀(279) 評論(0) 編輯收藏引用所屬分類: ACM基礎(chǔ)知識

ACM /ICPC的比賽形式一般是五個小時八個題目，綜合考察選手的數(shù)學(xué)能力、算法能力、coding能力和debug能力，還有團隊配合能力。數(shù)學(xué)方面主要強調(diào)組合數(shù)學(xué)、圖論和數(shù)論這三個方面的能力；而算法的覆蓋范圍很廣，涉及了大部分經(jīng)典的算法，和少量較前沿的算法。由于每道題目都需要通過所有的測試數(shù)據(jù)才能得分，并且需要精確解，這限制了Approximation algorithm在一些NP-hard的題目中的運用，從而使得搜索和剪枝策略對于NP-hard的題目非常重要。

Final的題目和Regional題目的比較

ACM ICPC官方的正式比賽可分為World Final和Regional Contest兩種。Final的題目更加正統(tǒng)和嚴(yán)謹(jǐn)，強調(diào)算法的綜合運用，一個題目往往需要幾種算法的結(jié)合。從這幾年的final的題目看，final加大了題目的代碼量，對代碼能力的要求有所增強。而Regional的題目則更加靈活，同時每個賽區(qū)也有自己的出題風(fēng)格。歐洲賽區(qū)的題目以高質(zhì)量出名，對算法和數(shù)學(xué)的強調(diào)甚至超過了World Final；美國的賽區(qū)較多模擬題，強調(diào)代碼量。而亞洲則介于兩者之間，同時由于每年都有一些新的賽區(qū)，所以并沒有很固定的模式。

下面淺談一下近幾年ACM ICPC的題目的覆蓋面。一些常規(guī)的算法和題型沒什么好講的，下面主要側(cè)重一些新穎的知識點或題型，或是一些較前沿的內(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里面有詳細的分析，并有著一個優(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的題目。如劉汝佳給達卡賽區(qū)出的一道unbreakable tiling的題目。其中我非常喜歡的一個題目是四年前東北歐賽區(qū)的一個floodlight problem：平面上給出n個點代表n盞燈，每個燈可以照亮圓心角為2*∏/n的一個扇形區(qū)域。問怎樣控制這些燈的角度，使得可以照亮整個平面。

還有一些數(shù)學(xué)題則考驗創(chuàng)造能力。比如有一題：給出n，要求找出一個n*n的方陣，其中每個元素都是1到n之間的整數(shù)，并且兩兩不等，同時使得每行、每列還有兩個對角線的和兩兩不等。這題的構(gòu)造頗為繁瑣，最簡單的方法是直接隨機生成再判定是否具有這個性質(zhì)。

近年來幾乎每年的final都有一道考察選手微積分能力的題目。而微分方程類題目較少。

大型線性方程組、復(fù)雜的矩陣代數(shù)、和特征值求解方面的題目較少。

算法的新題型

算法方面的增強主要體現(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ù)。字符串方面，較容易實現(xiàn)的后綴樹組也逐漸被接受。

一些算法：網(wǎng)絡(luò)流方面，不少選手開始掌握push-relabel算法而放棄了經(jīng)典的ford-fulkerson算法；劉汝佳的書廣為傳閱后，不少選手又掌握了fractional programming和dinkelbach算法。目前能熟練實現(xiàn)linear programming的選手較少，但可以預(yù)計過一段時間這也會成為必備的技能。

計算幾何一直是ACM ICPC里面的難題。不僅編程困難，更由于精度問題導(dǎo)致非常難做對。計算幾何往往是在比賽時被放棄的題目。即使算法并不非常難，選手也不敢隨意去做。

一些零散的經(jīng)典內(nèi)容也被拿出來考察，如stable marriage，fft等。

總結(jié)和一些預(yù)計

基本上，實現(xiàn)起來不算太復(fù)雜的多項式時間復(fù)雜度的算法都可以出成一道ACM ICPC的題目。而出題者知識面的不停增長，也使得越來越多這樣的算法被包括。另一方面，隨著算法的發(fā)展，一些原本沒有簡單算法的題目也出現(xiàn)了新的解法，這樣的題目也被加入到ACM ICPC中。ACM ICPC經(jīng)過多年的積累有著大量的題目，其覆蓋面也是非常之廣。

可以預(yù)見一些新的優(yōu)秀的算法將陸續(xù)出現(xiàn)在ACM ICPC中。比如由于任意圖匹配的Edmonds-Carp算法實現(xiàn)起來非常繁瑣，使得ICPC中一直不出現(xiàn)任意圖匹配的題目（即使有也是規(guī)模非常小）。而Vijay Vazirani的論文<<matching is as easy as matrix inversion>>中給出了一種通用的通過矩陣求逆而求各種匹配的算法，雖然該算法實現(xiàn)起來有一個難點，但相信將會被一些選手采用，從而出現(xiàn)一些任意圖匹配的題目，甚至更困難的exact match（該問題目前沒有deterministic polynomial-time algorithm，但用上面的方法可以得出一個概率算法）。

而一些新的領(lǐng)域也必將給ACM ICPC的出題者帶來靈感。例如已有越來越多Bio-informatics的題目在ICPC中出現(xiàn)。一些有著多項式算法的好題目，如inversion distance of signed permutations，則由于其理論的復(fù)雜而尚未出現(xiàn)在題目中。

圖論中還有數(shù)不勝數(shù)的好的題目，比如linear time求minimum cut，還有Gomory-Hu tree的應(yīng)用，這些也必將在不久的將來出現(xiàn)在ICPC題目中。

我認(rèn)為將發(fā)生的另一個趨勢是，隨機算法，概率算法和近似算法會在ACM ICPC中占更大的比重，至于對于算法能力和代碼能力考驗的平衡，我個人非常喜歡數(shù)學(xué)和算法，我希望Final的題目能向中歐賽區(qū)的題目靠攏。

ACM ICPC考察的不僅僅是對經(jīng)典算法的理解和掌握，創(chuàng)造算法的能力同樣非常重要。學(xué)那么多算法，必須從中有所領(lǐng)悟，才能在賽場上有靈感去解決實際的問題。

如果大家有興趣的話我可以找?guī)讉€具體的問題詳細分析，或是討論一些具體的算法理論。同樣的我也樂意分享一些ACM賽場上的經(jīng)驗，和在各大算法比賽中認(rèn)識的一些有趣的人，和經(jīng)歷過的一些有趣的事。匆匆寫完此文，疏漏之處在所難免，邏輯上也不甚連貫，希望大家見諒。

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: ACM中無輸入結(jié)束提示時如何判斷到達EOF ACM題目的風(fēng)格和近幾年題目的發(fā)展遞歸方程組解的漸進階的求法——差分方程法算法的復(fù)雜性 ACM的算法（覺得很好，有層次感) 見過的一個計劃算法書建議收藏 ACMer應(yīng)具備的能力 pku1004

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

登山之道

ACM題目的風(fēng)格和近幾年題目的發(fā)展

日歷

常用鏈接

隨筆分類

隨筆檔案

文章分類

文章檔案

程序的靈魂--算法

沙場秋點兵，壯士凱歌還

他山之石，可以攻玉

圍觀強人

搜索

最新評論

閱讀排行榜