?信息学竞赛之设计获胜策略?????一个好的取胜之道是制定在竞赛中指导你行动的策略。无论是在好的情况下还是在坏的情况下，它将帮助你决定你的行动。用这种方法你可以在竞赛中将时间花费在解决编程问题上而不是试图决定下一步该干什么…这有点像预先计算好你面对各种情况的反应。
?????心理上的准备也很重要。
竞赛中的策略
首先通读所有的题目；草拟出算法，复杂度，数量，数据结构，微妙的细节，…
集体讨论所有可能的算法——然后选择最“笨”但却可行的算法。（注：请注意这一点，对参赛选手来说获奖就是唯一目的）
进行计算！（空间和时间复杂度，并且加上实际期望和最坏情况下的数量）
试图证明该算法错误（？？原文是Trytobreakthealgorithm）——使用特殊的（退化的）测试数据。
将问题排序：根据你所需付出的努力，将最“短”（从原文理解是指解决问题费时最短）的问题排在前面。（从“短”到“长”的次序为：以前做过的，容易的，不熟悉的，困难的）
编写程序解决一个问题——对每一道题而言，一次一道题
确定算法
构造特殊情况的测试数据
写出数据结构
编写并测试输入子程序（编写额外的子程序来显示数据输入的正确性）
编写并测试输出子程序
逐步细化：通过写注释来刻划程序的逻辑轮廓
一个部分一个部分地填充并调试代码
完成代码使其正常运转，并验证代码的正确性（使用一般情况的测试数据）
试图证明代码错误（？？原文是Trytobreakthecode）——使用特殊情况的测试数据来验证代码正确性
逐渐优化——但足够了即可，并且保存所有的版本（使用困难情况的（即运行时间长的）测试数据来计算出实际运行时间）
时间安排策略和“故障控制”方案
???制定一个计划决定在各种（可预测的！）故障发生时的行动；想象你可能遇到的问题并计算出你所希望做出的反应。核心问题是：“你何时花费更多的时间在调试程序上，你何时放弃并继续做下一题？”。考虑以下问题：
你已经花费了多长时间来调试它？
你可能有什么样的BUG（BUG是指程序中的错误）
你的算法有错吗？
你的数据结构需要改变吗？
你是否对什么地方可能会出错有一些头绪？
你何时返回到一个你先前放弃的问题？
你何时花费较多的时间优化一个程序，你何时放弃当前优化工作而切换去作其他事？
在你上交你的答案之前列出一个校验表：
（Codefreezefiveminutesbeforeendofcontest）
将所有的声明关闭。
将调试输出关闭。
确认输入输出文件名正确。
确认输入输出格式正确。
重新编译并再测试一次。
将文件以正确的文件名复制到正确的位置（软盘）。
提示和技巧
如果可以就用暴力法（即穷举法）解决（注：居然将这条作为技巧，可见竞赛的目的就是获奖，为此要“不择手段”。）
提示：注意限制（在问题陈述中指明）
如果可以给你带来方便的话就浪费内存（假如你能侥幸逃脱处罚的话）
不要删除你额外的调试输出，将它注释起来
逐渐地优化，足够了即可
保留所有的工作版本
从编码到调试：
使用有意义的变量名
不要重复使用变量
逐步细化
在写代码之前先写注释
有可能的话尽量避免使用指针
避免使用麻烦的动态内存：静态地分配所有的东西。
尽量不要使用浮点数；如果你不得不使用，在所有使用的地方设置允许的误差（绝对不要测试两个浮点数相等）
对注释的注释：
不要写得太长，简洁的注解就可以了
解释复杂的功能：++i;/increasethevalueofiby1/这样的注释是毫无意义的。
解释代码中的技巧
注释要好像是写给某个了解该问题但并不了解程序代码的聪明人看的
对任何你不得不考虑的东西加以注释
在任何你看到了以后会问“他到底干什么用”的地方加注释（Anythingyoulookedatevenoncesaying,"nowwhatdoesthatdoagain?"）
总是注释数组的索引次序
记录你每一次竞赛的情况：成功之处、犯的错误，以及何处你可以做得更好；利用这些记录来改进你的策略。
复杂度
基础和阶符号
???复杂度分析的基本原理围绕着符号“大O”，例如：O(N).这意味着算法的执行速度或内存占用将会随着问题规模的增倍而增倍。一个有着O(N2)的算法在问题的规模增倍时其运行时间将会减慢4倍（或者消耗4倍的空间）。常数时间或空间消耗的算法用O(1)表示。这个概念同时适用于时间和空间；这里我们将集中讨论时间。
一种推算一个程序的O()运行时间的方法是检查它的循环。嵌套最深的（因而也是最慢的）循环支配着运行时间，同时它也是在讨论O()符号时唯一考虑的循环。有一个单重循环和一个单层嵌套循环（假设每个循环每次执行N次）的程序的复杂度的阶是O(N2)，尽管程序中同时有一个O(N)循环。
当然，递归也像循环一样计算，并且递归程序可以有像O(bN)，O(N!)，甚至O(NN)的阶。
经验法则
在分析一个算法以计算出对于一个给定的数据集它可能要运行多长时间的时候，第一条经验法则是：现代（1999）计算机每秒可以进行10M次操作。对于一个有五秒钟时间限制的程序，大约可以处理50M次操作。真正优化的好的程序或许可以处理2倍甚至4倍于这个数目的操作。复杂的算法或许只能处理这个数目的一半。
640K确实是苛刻的内存限制。幸运的是，1999-2000赛季将是这个限制的最后一次起作用。
210约等于103
如果有k重嵌套的循环，每重大约循环N次，该程序的复杂度为O(Nk)。
如果你的程序有l层递归，每层递归有b个递归调用，该程序复杂度为O(bl)。
当你在处理有关排列组合之类的算法时，记住N个元素的排列有N!个，N个元素的组合或N个元素组成的集合的幂集的有2n个。
对N个元素排序的最少时间是O(NlogN)。
进行数学计算！
例子：
一个简单的重复N次的循环复杂度为O(N)：
1sum=0
2fori=1ton
3sum=sum+i
一个双重嵌套循环的复杂度通常为O(N2)：
#fillarrayawithNelements
1fori=1ton-1
2forj=i+1ton
3if(a[i]>a[j])
swap(a[i],a[j])
???注意，虽然这个循环执行了N×(N+1)/2次if语句，但他的复杂度仍然是O(N2)，因为N加倍后执行时间增加了四倍。
解决方案的范例
产生器vs.过滤器
???
预先计算
???
分解（编程竞赛中最困难的事）
???
对称
???许多问题中存在着对称（例如，无论你按哪一个方向，一对点之间的距离通常是相同的）。对称可以是2路的（？？原文是2-way），4路的，8路的或是更多的。尽量利用对称以减少运行时间。
???例如，对于4路对称，你只需解决问题的四分之一，就可以写下4个结果，这四个结果和你所解决的一个结果是对称的（注意自对称的解答，他当然只应该被输出一次或两次）。
正向vs.逆向
???令人惊讶地，许多竞赛题用逆向法解决比正面突破要好得多。以逆序处理数据或构造一种基于某种非明显的方式或顺序检索数据的突破策略时，要特别小心。
简化
???某些问题可以被改述为一个有点不同的其他问题，这样你解决了新问题，就已经有了原始问题的答案或者容易找出原始问题的答案；当然，你只需解决两者之中较容易的那个。另外，像归纳法一样，你可以对一个较小的问题的解答作一些小小的改变以得到原问题的完整答案。
CraftingWinningSolutions
Agoodwaytogetacompetitiveedgeistowritedownagameplanforwhatyou''regoingtodoinacontestround.Thiswillhelpyouscriptoutyouractions,intermsofwhattodobothwhenthingsgorightandwhenthingsgowrong.Thiswayyoucanspendyourthinkingtimeintheroundfiguringoutprogrammingproblemsandnottryingtofigureoutwhattheheckyoushoulddonext...it''ssortoflikeprecomputingyourreactionstomostsituations.
Mentalpreparationisalsoimportant.
GamePlanForAContestRound
ReadthroughALLtheproblemsFIRST;sketchnoteswithalgorithm,complexity,thenumbers,datastructs,trickydetails,...
Brainstormmanypossiblealgorithms-thenpickthestupidestthatworks!
DOTHEMATH!(space&timecomplexity,andpluginactualexpectedandworstcasenumbers)
Trytobreakthealgorithm-usespecial(degenerate?)testcases
Ordertheproblems:shortestjobfirst,intermsofyoureffort(shortesttolongest:doneitbefore,easy,unfamiliar,hard)
Codingaproblem-Foreach,oneatatime:
Finalizealgorithm
Createtestdatafortrickycases
Writedatastructures
Codetheinputroutineandtestit(writeextraoutputroutinestoshowdata?)
Codetheoutputroutineandtestit
Stepwiserefinement:writecommentsoutliningtheprogramlogic
Fillincodeanddebugonesectionatatime
Getitworking&verifycorrectness(usetrivialtestcases)
Trytobreakthecode-usespecialcasesforcodecorrectness
Optimizeprogressively-onlyasmuchasneeded,andkeepallversions(usehardtestcasestofigureoutactualruntime)
Timemanagementstrategyand"damagecontrol"scenarios
Haveaplanforwhattodowhenvarious(foreseeable!)thingsgowrong;imagineproblemsyoumighthaveandfigureouthowyouwanttoreact.Thecentralquestionis:"Whendoyouspendmoretimedebuggingaprogram,andwhendoyoucutyourlossesandmoveon?".Considertheseissues:
Howlonghaveyouspentdebuggingitalready?
Whattypeofbugdoyouseemtohave?
Isyouralgorithmwrong?
Doyoudatastructuresneedtobechanged?
Doyouhaveanyclueaboutwhat''sgoingwrong?
Ashortamount(20mins)ofdebuggingisbetterthanswitchingtoanythingelse;butyoumightbeabletosolveanotherfromscratchin45mins.
Whendoyougobacktoaproblemyou''veabandonedpreviously?
Whendoyouspendmoretimeoptimizingaprogram,andwhendoyouswitch?
Considerfromhereout-forgetprioreffort,focusonthefuture:howcanyougetthemostpointsinthenexthourwithwhatyouhave?
Haveachecklisttousebeforeturninginyoursolutions:
Codefreezefiveminutesbeforeendofcontest?
Turnassertsoff.
Turnoffdebuggingoutput.
Tips&Tricks
Bruteforceitwhenyoucan
KISS:Simpleissmart!
Hint:focusonlimits(specifiedinproblemstatement)
Wastememorywhenitmakesyourlifeeasier(ifyoucangetawaywithit)
Don''tdeleteyourextradebuggingoutput,commentitout
Optimizeprogressively,andonlyasmuchasneeded
Keepallworkingversions!
Codetodebug:
whitespaceisgood,
usemeaningfulvariablenames,
don''treusevariables,
stepwiserefinement,
COMMENTBEFORECODE.
Avoidpointersifyoucan
Avoiddynamicmemoryliketheplague:staticallyallocateeverything.
Trynottousefloatingpoint;ifyouhaveto,puttolerancesineverywhere(nevertestequality)
Commentsoncomments:
Notlongprose,justbriefnotes
Explainhigh-levelfunctionality:++i;/increasethevalueofiby/isworsethanuseless
Explaincodetrickery
Delimit&documentfunctionalsections
Asiftosomeoneintelligentwhoknowstheproblem,butnotthecode
Anythingyouhadtothinkabout
Anythingyoulookedatevenoncesaying,"nowwhatdoesthatdoagain?"
Alwayscommentorderofarrayindices
Keepalogofyourperformanceineachcontest:successes,mistakes,andwhatyoucouldhavedonebetter;usethistorewriteandimproveyourgameplan!
Complexity
Basicsandordernotation
Thefundamentalbasisofcomplexityanalysisrevolvesaroundthenotionof``bigoh''''notation,forinstance:O(N).Thismeansthatthealgorithm''sexecutionspeedormemoryusagewilldoublewhentheproblemsizedoubles.AnalgorithmofO(N2)willrunaboutfourtimesslower(oruse4xmorespace)whentheproblemsizedoubles.Constant-timeorspacealgorithmsaredenotedO(1).Thisconceptappliestotimeandspaceboth;herewewillconcentratediscussionontime.
OnededucestheO()runtimeofaprogrambyexaminingitsloops.Themostnested(andhenceslowest)loopdominatestheruntimeandistheonlyonementionedwhendiscussingO()notation.Aprogramwithasingleloopandanestedloop(presumablyloopsthatexecuteNtimeseach)isO(N2),eventhoughthereisalsoaO(N)looppresent.
Ofcourse,recursionalsocountsasaloopandrecursiveprogramscanhaveorderslikeO(bN),O(N!),orevenO(NN).
Rulesofthumb
Whenanalyzinganalgorithmtofigureouthowlongitmightrunforagivendataset,thefirstruleofthumbis:modern(2004)computerscandealwith100Mactionspersecond.Inafivesecondtimelimitprogram,about500Mactionscanbehandled.Reallywelloptimizedprogramsmightbeabletodoubleorevenquadruplethatnumber.Challengingalgorithmsmightonlybeabletohandlehalfthatmuch.Currentcontestsusuallyhaveatimelimitof1secondforlargedatasets.
16MBmaximummemoryuse
210~approx~103
IfyouhaveknestedloopsrunningaboutNiterationseach,theprogramhasO(Nk)complexity.
Ifyourprogramisrecursivewithbrecursivecallsperlevelandhasllevels,theprogramO(bl)complexity.
BearinmindthatthereareN!permutationsand2nsubsetsorcombinationsofNelementswhendealingwiththosekindsofalgorithms.
ThebesttimesforsortingNelementsareO(NlogN).
DOTHEMATH!Pluginthenumbers.
Examples
AsingleloopwithNiterationsisO(N):?1??sum?=?0?2??for?i?=?1?to?n?3????sum?=?sum?+?i
AdoublenestedloopisoftenO(N2):#?fill?array?a?with?N?elements1?for?i?=?1?to?n-12???for?j?=?i?+?1?to?n3?????if?(a[i]?>?a[j])?????????swap?(a[i],?a[j])NotethateventhoughthisloopexecutesNx(N+1)/2iterationsoftheifstatement,itisO(N2)sincedoublingNquadruplestheexecutiontimes.
Considerthiswellbalancedbinarytreewithfourlevels:AnalgorithmthattraversesageneralbinarytreewillhavecomplexityO(2N).
SolutionParadigms
Generatingvs.Filtering
Programsthatgeneratelotsofpossibleanswersandthenchoosetheonesthatarecorrect(imaginean8-queensolver)arefilters.Thosethathoneinexactlyonthecorrectanswerwithoutanyfalsestartsaregenerators.Generally,filtersareeasier(faster)tocodeandrunslower.Dothemathtoseeifafilterisgoodenoughorifyouneedtotryandcreateagenerator.
Precomputation
Sometimesitishelpfultogeneratetablesorotherdatastructuresthatenablethefastestpossiblelookupofaresult.Thisiscalledprecomputation(inwhichonetradesspacefortime).Onemighteithercompileprecomputeddataintoaprogram,calculateitwhentheprogramstarts,orjustrememberresultsasyoucomputethem.Aprogramthatmusttranslatelettersfromuppertolowercasewhentheyareinuppercasecandoaveryfasttablelookupthatrequiresnoconditionals,forexample.Contestproblemsoftenuseprimenumbers-manytimesitispracticaltogeneratealonglistofprimesforuseelsewhereinaprogram.
Decomposition(TheHardestThingAtProgrammingContests)
Whiletherearefewerthan20basicalgorithmsusedincontestproblems,thechallengeofcombinationproblemsthatrequireacombinationoftwoalgorithmsforsolutionisdaunting.Trytoseparatethecuesfromdifferentpartsoftheproblemsothatyoucancombineonealgorithmwithalooporwithanotheralgorithmtosolvedifferentpartsoftheproblemindependently.Notethatsometimesyoucanusethesamealgorithmtwiceondifferent(independent!)partsofyourdatatosignificantlyimproveyourrunningtime.
Symmetries
Manyproblemshavesymmetries(e.g.,distancebetweenapairofpointsisoftenthesameeitherwayyoutraversethepoints).Symmetriescanbe2-way,4-way,8-way,andmore.Trytoexploitsymmetriestoreduceexecutiontime.
Forinstance,with4-waysymmetry,yousolveonlyonefourthoftheproblemandthenwritedownthefoursolutionsthatsharesymmetrywiththesingleanswer(lookoutforself-symmetricsolutionswhichshouldonlybeoutputonceortwice,ofcourse).
Forwardvs.Backward
Surprisingly,manycontestproblemsworkfarbetterwhensolvedbackwardsthanwhenusingafrontalattack.Beonthelookoutforprocessingdatainreverseorderorbuildinganattackthatlooksatthedatainsomeorderorfashionotherthantheobvious.
Simplification
Someproblemscanberephrasedintoasomewhatdifferentproblemsuchthatifyousolvethenewproblem,youeitheralreadyhaveorcaneasilyfindthesolutiontotheoriginalone;ofcourse,youshouldsolvetheeasierofthetwoonly.Alternatively,likeinduction,forsomeproblemsonecanmakeasmallchangetothesolutionofaslightlysmallerproblemtofindthefullanswer.
信息学资料——学习提示之设计获胜策略
深入研读、温故知新坚持、专注、投入、自制、自学勤于思考、练习、总结第6页共10页
|
|
