設(shè)計(jì)獲勝策略

設(shè)計(jì)獲勝略設(shè)計(jì)獲勝一個(gè)好的取勝之道是制定在競(jìng)賽中指導(dǎo)你行動(dòng)的策略。 無(wú)論是在好的情況下還是在壞的情況下，它將幫助你決定你的行動(dòng)。用這種方法你可以在競(jìng)賽中將時(shí)間花費(fèi)在解決編程問(wèn)題上而不是試圖決定下一步該干什么…這有點(diǎn)像預(yù)先計(jì)算好你面對(duì)各種情況的反應(yīng)。心理上的準(zhǔn)備也很重要。競(jìng)賽中的策略首先通讀所有的題目；草擬出算法，復(fù)雜度，數(shù)量，數(shù)據(jù)結(jié)構(gòu)，微妙的細(xì)節(jié)，…集體討論所有可能的算法一一然后選擇最“笨”但卻可行的算法。（注：請(qǐng)注意這一點(diǎn)，對(duì)參賽選手來(lái)說(shuō)獲獎(jiǎng)就是唯一目的）進(jìn)行計(jì)算！（空間和時(shí)間復(fù)雜度，并且加上實(shí)際期望和最壞情況下的數(shù)量）試圖證明該算法錯(cuò)誤（原文是Trytobreakthealgorithm） 使用特殊的（退化的）測(cè)試數(shù)據(jù)。將問(wèn)題排序：根據(jù)你所需付出的努力，將最“短” （從原文理解是指解決問(wèn)題費(fèi)時(shí)最短）的問(wèn)題排在前面。（從“短”到“長(zhǎng)”的次序?yàn)椋阂郧白鲞^(guò)的，容易的，不熟悉的，困難的）編寫程序解決一個(gè)問(wèn)題一一對(duì)每一道題而言，一次一道題確定算法構(gòu)造特殊情況的測(cè)試數(shù)據(jù)寫出數(shù)據(jù)結(jié)構(gòu)編寫并測(cè)試輸入子程序（編寫額外的子程序來(lái)顯示數(shù)據(jù)輸入的正確性）編寫并測(cè)試輸出子程序逐步細(xì)化：通過(guò)寫注釋來(lái)刻劃程序的邏輯輪廓一個(gè)部分一個(gè)部分地填充并調(diào)試代碼完成代碼使其正常運(yùn)轉(zhuǎn)，并驗(yàn)證代碼的正確性（使用一般情況的測(cè)試數(shù)據(jù)）試圖證明代碼錯(cuò)誤（原文是Trytobreakthecode） 使用特殊情況的測(cè)試數(shù)據(jù)來(lái)驗(yàn)證代碼正確性逐漸優(yōu)化一一但足夠了即可，并且保存所有的版本（使用困難情況的（即運(yùn)行時(shí)間長(zhǎng)的）測(cè)試數(shù)據(jù)來(lái)計(jì)算出實(shí)際運(yùn)行時(shí)間）時(shí)間安排策略和“故障控制”方案制定一個(gè)計(jì)劃決定在各種（可預(yù)測(cè)的?。┕收习l(fā)生時(shí)的行動(dòng)；想象你可能遇到的問(wèn)題并計(jì)算出你所希望做出的反應(yīng)。核心問(wèn)題是： “你何時(shí)花費(fèi)更多的時(shí)間在調(diào)試程序上，你何時(shí)放棄并繼續(xù)做下一題”。考慮以下問(wèn)題：你已經(jīng)花費(fèi)了多長(zhǎng)時(shí)間來(lái)調(diào)試它你可能有彳+么樣的BUG（BU系指程序中的錯(cuò)誤）你的算法有錯(cuò)嗎你的數(shù)據(jù)結(jié)構(gòu)需要改變嗎你是否對(duì)什么地方可能會(huì)出錯(cuò)有一些頭緒花費(fèi)較短的時(shí)間（20分鐘）在調(diào)試上比切換去做其他別的事要好；但是你或許能夠在45分鐘內(nèi)解決另一個(gè)問(wèn)題（原文是Ashortamount(20mins)ofdebuggingisbetterthanswitchingtoanythingelse;butyoumightbeabletosolveanotherfromscratchin45mins. ）你何時(shí)返回到一個(gè)你先前放棄的問(wèn)題你何時(shí)花費(fèi)較多的時(shí)間優(yōu)化一個(gè)程序， 你何時(shí)放棄當(dāng)前優(yōu)化工作而切換去作其他事從這里考慮出去（原文是Considerfromhereout） 忘記先前的努力，著眼于將來(lái)：你如何才能就你目前所有的抓住下一個(gè)小時(shí)。在你上交你的答案之前列出一個(gè)校驗(yàn)表：在競(jìng)賽結(jié)束前五分鐘凍結(jié)代碼（原文是 Codefreezefiveminutesbeforeendofcontest）將所有的聲明關(guān)閉。將調(diào)試輸出關(guān)閉。確認(rèn)輸入輸出文件名正確。確認(rèn)輸入輸出格式正確。重新編譯并再測(cè)試一次。將文件以正確的文件名復(fù)制到正確的位置（軟盤）。提示和技巧如果可以就用暴力法（即窮舉法）解決（注：居然將這條作為技巧，可見(jiàn)競(jìng)賽的目的就是獲獎(jiǎng)，為此要“不擇手段”。）鍵索引順序搜索（KISS=KeyedIndexedSequentialSearch）：簡(jiǎn)單就是聰明?。ㄔ氖荎ISS:Simpleissmart!提示：注意限制（在問(wèn)題陳述中指明）如果可以給你帶來(lái)方便的話就浪費(fèi)內(nèi)存 （假如你能僥幸逃脫處罰的話）不要?jiǎng)h除你額外的調(diào)試輸出，將它注釋起來(lái)逐漸地優(yōu)化，足夠了即可保留所有的工作版本從編碼到調(diào)試：空白是好的（原文是whitespaceisgood）使用有意義的變量名不要重復(fù)使用變量逐步細(xì)化在寫代碼之前先寫注釋有可能的話盡量避免使用指針避免使用麻煩的動(dòng)態(tài)內(nèi)存：靜態(tài)地分配所有的東西。盡量不要使用浮點(diǎn)數(shù)；如果你不得不使用，在所有使用的地方設(shè)置允許的誤差（絕對(duì)不要測(cè)試兩個(gè)浮點(diǎn)數(shù)相等）對(duì)注釋的注釋：不要寫得太長(zhǎng)，簡(jiǎn)潔的注解就可以了解釋復(fù)雜的功能：++i;/*increasethevalueofiby1*/ 這樣的注釋是毫無(wú)意義的。解釋代碼中的技巧將功能模塊劃定界限并且document(原文是Delimit&documentfunctionalsections)好像是寫給某個(gè)了解該問(wèn)題但并不了解程序代碼的聰明人看的任何你不得不考慮的東西原文是Anythingyoulookedatevenoncesaying,"nowwhatdoesthatdoagain"總是注釋數(shù)組的索引次序記錄你每一次競(jìng)賽的情況：成功之處、犯的錯(cuò)誤，以及何處你可以做得更好；利用這些記錄來(lái)改進(jìn)你的策略。復(fù)雜度基礎(chǔ)和階符號(hào)復(fù)雜度分析的基本原理圍繞著符號(hào)“大 O',例如：O(N).這意味著算法的執(zhí)行速度或內(nèi)存占用將會(huì)隨著問(wèn)題規(guī)模的增倍而增倍。一個(gè)有著O(N2) 的算法在問(wèn)題的規(guī)模增倍時(shí)其運(yùn)行時(shí)間將會(huì)減慢 4倍(或者消耗4倍的空間)。常數(shù)時(shí)間或空間消耗的算法用O(1)表示。這個(gè)概念同時(shí)適用于時(shí)間和空間；這里我們將集中討論時(shí)間。一種推算一個(gè)程序的O()運(yùn)行時(shí)間的方法是檢查它的循環(huán)。嵌套最深的(因而也是最慢的)循環(huán)支配著運(yùn)行時(shí)間，同時(shí)它也是在討論 O()符號(hào)時(shí)唯一考慮的循環(huán)。有一個(gè)單重循環(huán)和一個(gè)單層嵌套循環(huán)(假設(shè)每個(gè)循環(huán)每次執(zhí)行N次)的程序的復(fù)雜度的階是O(N2),盡管程序中同時(shí)有一個(gè)O(N)循環(huán)。當(dāng)然，遞歸也像循環(huán)一樣計(jì)算，并且遞歸程序可以有像 O(bN),O(N!),甚至O(NN)的階。經(jīng)驗(yàn)法則在分析一個(gè)算法以計(jì)算出對(duì)于一個(gè)給定的數(shù)據(jù)集它可能要運(yùn)行多長(zhǎng)時(shí)間的時(shí)候，第一條經(jīng)驗(yàn)法則是：現(xiàn)代(1999)計(jì)算機(jī)每秒可以進(jìn)行10M次操作。對(duì)于一個(gè)有五秒鐘時(shí)間限制的程序，大約可以處理 50M次操作。真正優(yōu)化的好的程序或許可以處理2倍甚至4倍于這個(gè)數(shù)目的操作。復(fù)雜的算法或許只能處理這個(gè)數(shù)目的一半。640K 確實(shí)是苛刻的內(nèi)存限制。幸運(yùn)的是，1999-2000賽季將是這個(gè)限制的最后一次起作用。210約等于103如果有k重嵌套的循環(huán)，每重大約循環(huán)N次，該程序的復(fù)雜度為O(Nk)。如果你的程序有l(wèi)層遞歸，每層遞歸有b個(gè)遞歸調(diào)用，該程序復(fù)雜度為O(bl)。當(dāng)你在處理有關(guān)排列組合之類的算法時(shí)，記住N個(gè)元素的排列有N!個(gè)，N個(gè)元素的組合或N個(gè)元素組成的集合的募集的有2n個(gè)。對(duì)N個(gè)元素排序的最少時(shí)間是O(NlogN)。進(jìn)行數(shù)學(xué)計(jì)算！將所有的數(shù)據(jù)加起來(lái)。 (原文是Pluginthenumbers.)例子:一個(gè)簡(jiǎn)單的重復(fù)N次的循環(huán)復(fù)雜度為O(N):sum=0fori=1tonsum=sum+i一個(gè)雙重嵌套循環(huán)的復(fù)雜度通常為O(N2):#fillarrayawithNelementsfori=1ton-1forj=i+1tonif(a[i]>a[j])swap(a[i],a[j])注意，雖然這個(gè)循環(huán)執(zhí)行了NX(N+1)/2次if語(yǔ)句，但他的復(fù)雜度仍然是O(N2),因?yàn)镹加倍后執(zhí)行時(shí)間增加了四倍。解決方案的范例產(chǎn)生器vs.過(guò)濾器產(chǎn)生大量可能的答案然后選擇其中正確的 (比如8皇后問(wèn)題的解答)，這樣的程序叫做過(guò)濾器。那些只產(chǎn)生正確答案而不產(chǎn)生任何錯(cuò)誤節(jié)點(diǎn)的叫做產(chǎn)生器。一般來(lái)說(shuō)，過(guò)濾器較容易(較快)編程實(shí)現(xiàn)但是運(yùn)行較慢。通過(guò)數(shù)學(xué)計(jì)算來(lái)判斷一個(gè)過(guò)濾器是否足夠好或者是否你需要嘗試制作一個(gè)產(chǎn)生器。預(yù)先計(jì)算有時(shí)生成表格或其他數(shù)據(jù)結(jié)構(gòu)以便快速查找結(jié)果是很有用的。 這種方法叫做預(yù)先計(jì)算(在這里用空間換取時(shí)間)。你可以將需要預(yù)先計(jì)算的數(shù)據(jù)和程序一起編譯，在程序開始時(shí)計(jì)算；也可以干脆記住預(yù)先計(jì)算出的結(jié)果。比如說(shuō)，一個(gè)程序需要將大寫字母轉(zhuǎn)化為小寫字母，可以不需任何條件地利用一個(gè)表格進(jìn)行快速查找來(lái)實(shí)現(xiàn)。競(jìng)賽題經(jīng)常要用到素?cái)?shù)一一生成一長(zhǎng)串素?cái)?shù)在程序中某處使用通常是很實(shí)用的。分解（編程競(jìng)賽中最困難的事）雖然在競(jìng)賽中經(jīng)常使用的基本算法不超過(guò)20種，但是某些需要將兩種算法結(jié)合才能解決的組合型問(wèn)題卻是很復(fù)雜的。盡量將問(wèn)題不同部分的線索分離開來(lái)以便你可以將一個(gè)算法和一個(gè)循環(huán)或其他算法結(jié)合起來(lái)以獨(dú)立地解決問(wèn)題的不同部分。注意，有時(shí)你可以對(duì)你的數(shù)據(jù)的不同（獨(dú)立）部分重復(fù)使用相同的算法以有效地改進(jìn)程序的運(yùn)行時(shí)間。對(duì)稱許多問(wèn)題中存在著對(duì)稱（例如，無(wú)論你按哪一個(gè)方向，一對(duì)點(diǎn)之間的距離通常是相同的）。對(duì)稱可以是2路的（原文是2-way）,4路的，8路的或是更多的。盡量利用對(duì)稱以減少運(yùn)行時(shí)間。例如，對(duì)于4路對(duì)稱，你只需解決問(wèn)題的四分之一，就可以寫下4個(gè)結(jié)果，這四個(gè)結(jié)果和你所解決的一個(gè)結(jié)果是對(duì)稱的（注意自對(duì)稱的解答，他當(dāng)然只應(yīng)該被輸出一次或兩次）。正向vs.逆向令人驚訝地，許多競(jìng)賽題用逆向法解決比正面突破要好得多。以逆序處理數(shù)據(jù)或構(gòu)造一種基于某種非明顯的方式或順序檢索數(shù)據(jù)的突破策略時(shí)，要特別小心。簡(jiǎn)化某些問(wèn)題可以被改述為一個(gè)有點(diǎn)不同的其他問(wèn)題，這樣你解決了新問(wèn)題，就已經(jīng)有了原始問(wèn)題的答案或者容易找出原始問(wèn)題的答案；當(dāng)然，你只需解決兩者之中較容易的那個(gè)。另外，像歸納法一樣，你可以對(duì)一個(gè)較小的問(wèn)題的解答作一些小小的改變以得到原問(wèn)題的完整答案。TranslatedbyStarfish原文：CraftingWinningSolutionsAgoodwaytogetacompetitiveedgeistowritedownagameplanforwhatyou'regoingtodoinacontestround.Thiswillhelpyouscriptoutyouractions,intermsofwhattodobothwhenthingsgorightandwhenthingsgowrong.Thiswayyoucanspendyourthinkingtimeintheroundfiguringoutprogrammingproblemsandnottryingtofigureoutwhattheheckyoushoulddonext...it'ssortoflikeprecomputingyourreactionstomostsituations.Mentalpreparationisalsoimportant.GamePlanForAContestRoundReadthroughALLtheproblemsFIRST;sketchnoteswithalgorithm,complexity,thenumbers,datastructs,trickydetails,...Brainstormmanypossiblealgorithms-thenpickthestupidestthatworks!DOTHEMATH!(space&timecomplexity,andpluginactualexpectedandworstcasenumbers)Trytobreakthealgorithm-usespecial(degenerate)testcasesOrdertheproblems:shortestjobfirst,intermsofyoureffort(shortesttolongest:doneitbefore,easy,unfamiliar,hard)Codingaproblem-Foreach,oneatatime:FinalizealgorithmCreatetestdatafortrickycasesWritedatastructuresCodetheinputroutineandtestit(writeextraoutputroutinestoshowdata)CodetheoutputroutineandtestitStepwiserefinement:writecommentsoutliningtheprogramlogicFillincodeanddebugonesectionatatimeGet itworking&verifycorrectness(usetrivial testcases)Try tobreakthecode-usespecialcasesforcodecorrectnessOptimizeprogressively-onlyasmuchasneeded,andkeepallversions(usehardtestcasestofigureoutactualruntime)Timemanagementstrategyand"damagecontrol"scenariosHaveaplanforwhattodowhenvarious(foreseeable!)thingsgowrong;imagineproblemsyoumighthaveandfigureouthowyouwanttoreact.Thecentralquestionis:"Whendoyouspendmoretimedebuggingaprogram,andwhendoyoucutyourlossesandmoveon".Considertheseissues:HowlonghaveyouspentdebuggingitalreadyWhattypeofbugdoyouseemtohaveIsyouralgorithmwrongDoyoudatastructuresneedtobechangedDoyouhaveanyclueaboutwhat'sgoingwrongshortamount(20mins)ofdebuggingisbetterthanswitchingtoanythingelse;butyoumightbeabletosolveanotherfromscratchin45mins.Whendoyougobacktoaproblemyou'veabandonedpreviouslyWhendoyouspendmoretimeoptimizingaprogram,andwhendoyouswitchConsiderfromhereout-forgetprioreffort,focusonthefuture:howcanyougetthemostpointsinthenexthourwithwhatyouhaveHaveachecklisttousebeforeturninginyoursolutions:CodefreezefiveminutesbeforeendofcontestTurnassertsoff.Turnoffdebuggingoutput.Turnonalloptimizations.Makesureinputandoutputaretocorrectfilenames.Makesuretheinputandoutputformatsarecorrect.Recompileandtestoncemore.Copyfilestocorrectlocations(floppy)withcorrectnames.Tips&TricksBruteforceitwhenyoucanKISS:Simpleissmart!Hint:focusonlimits(specifiedinproblemstatement)Wastememorywhenitmakesyourlifeeasier(ifyoucangetawaywithit)Don'tdeleteyourextradebuggingoutput,commentitoutOptimizeprogressively,andonlyasmuchasneededKeepallworkingversions!Codetodebug:whitespaceisgood,usemeaningfulvariablenames,don'treusevariables,stepwiserefinement,COMMENTBEFORECODE.AvoidpointersifyoucanAvoiddynamicmemoryliketheplague:staticallyallocateeverything.Trynottousefloatingpoint;ifyouhaveto,puttolerancesineverywhere(nevertestequality)Commentsoncomments:Notlongprose,justbriefnotes

Explainhigh-levelfunctionality:++i;/*increasetheExplainhigh-levelfunctionality:++i;/*increasethevalueofiby*/isworsethanuselessExplaincodetrickeryDelimit&documentfunctionalsectionsAsiftosomeoneintelligentwhoknowstheproblem,butnotthecodeAnythingyouhadtothinkaboutAnythingyoulookedatevenoncesaying,"nowwhatdoesthatdoagain"AlwayscommentorderofarrayindicesKeepalogofyourperformanceineachcontest:successes,mistakes,andwhatyoucouldhavedonebetter;usethistorewriteandimproveyourgameplan!ComplexityBasicsandordernotationThefundamentalbasisofcomplexityanalysisrevolvesaroundthenotionof''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).RulesofthumbWhenanalyzinganalgorithmtofigureouthowlongitmightrunforagivendataset,thefirstruleofthumbis:modern(1999)computerscandealwith10Mactionspersecond.Inafivesecondtimelimitprogram,about50Mactionscanbehandled.Reallywelloptimizedprogramsmightbeabletodoubleorevenquadruplethatnumber.Challengingalgorithmsmightonlybeabletohandlehalfthatmuch.640Kisareallytightmemoryconstraint.Happily,the1999-2000seasonisthelasttimethisconstraintapplies.210~approx~103IfyouhaveknestedloopsrunningaboutNiterationseach,theprogramhasO(Nk)complexity.Ifyourprogramisrecursivewithbrecursivecallsperlevelandhasllevels,theprogramO(bl)complexity.BearinmindthatthereareN!permutationsand2nsubsetsorcombinationsofNelementswhendealingwiththosekindsofalgorithms.ThebesttimesforsortingNelementsareO(NlogN).DOTHEMATH!Pluginthenumbers.ExamplesAsingleloopwithNiterationsisO(N):sum=0fori=1tonsum=sum+iAdoublenestedloopisoftenO(N2):#fillarrayawithNelementsfori=1ton-1forj=i+1tonif(a[i]>a[j])swap(a[i],a[j])NotethateventhoughthisloopexecutesNx(N+1)/2iterationsoftheifstatement,itisO(N2)sincedoublingNquadruplestheexecutiontimes.SolutionParadigmsGeneratingvs.FilteringProgramsthatgeneratelotsofpossibleanswersandthenchoosetheonesthatarecorrect(imaginean8-queensolver)arefilters.Thosethathoneinexactlyonthecorrectanswerwithoutanyfalsestartsaregenerators.Generally,filtersareeasier(faster)tocodeandrunslower.Dothemathtoseeifafilterisgoodenoughorifyouneedtotryandcreateagenerator.PrecomputationSometimesitishelpfultogeneratetablesorotherdatastructuresthatenablethefastestpossiblelookupofaresult.Thisiscalledprecomputation(inwhichonetradesspacefortime).Onemighteithercompileprecomputeddataintoaprogram,calculateitwhentheprogramstarts,orjustrememberresultsasyoucomputethem.Aprogramthatmusttranslatelettersfromuppertolowercasewhentheyareinuppercasecandoaveryfasttablelookupthatrequiresnoconditionals,forexample.Contestproblemsoftenuseprimenumbers-manytimesitispracticaltogeneratealonglistofprimesforuseelsewhereinaprogram.Decomposition(TheHardestThingAtProgrammingContests)Whiletherearefewerthan20basicalgorithmsusedincontestproblems,thechallengeofcombinationproblemsthatrequireacombinationoftwoalgorithmsforsolutionisdaunting.Trytoseparatethecuesfromdifferentpartsoftheproblemsothatyoucancombineonealgorithmwithalooporwithanotheralgorithmtosolvedifferentpartsofthepro