浅谈设计获胜策略分析

1、. .9/9设计获胜策略设计获胜策略 一个好的取胜之道是制定在竞赛中指导你行动的策略。无论是在好的情况下还是在坏的情况下，它将帮助你决定你的行动。用这种方法你可以在竞赛中将时间花费在解决编程问题上而不是试图决定下一步该干什么这有点像预先计算好你面对各种情况的反应。 心理上的准备也很重要。 竞赛中的策略 首先通读所有的题目；草拟出算法，复杂度，数量，数据结构，微妙的细节， 集体讨论所有可能的算法 然后选择最“笨”但却可行的算法。（注：请注意这一点，对参赛选手来说获奖就是唯一目的） 进行计算！（空间和时间复杂度，并且加上实际期望和最坏情况下的数量） 试图证明该算法错误（？原文是Try to bre

2、ak the algorithm） 使用特殊的（退化的）测试数据。 将问题排序：根据你所需付出的努力，将最“短”（从原文理解是指解决问题费时最短）的问题排在前面。（从“短”到“长”的次序为：以前做过的，容易的，不熟悉的，困难的） 编写程序解决一个问题 对每一道题而言，一次一道题 确定算法 构造特殊情况的测试数据 写出数据结构 编写并测试输入子程序（编写额外的子程序来显示数据输入的正确性） 编写并测试输出子程序 逐步细化：通过写注释来刻划程序的逻辑轮廓 一个部分一个部分地填充并调试代码 完成代码使其正常运转，并验证代码的正确性（使用一般情况的测试数据） 试图证明代码错误（？原文是Try to b

3、reak the code）使用特殊情况的测试数据来验证代码正确性 逐渐优化但足够了即可，并且保存所有的版本（使用困难情况的（即运行时间长的）测试数据来计算出实际运行时间） 时间安排策略和“故障控制”方案 制定一个计划决定在各种（可预测的！）故障发生时的行动；想象你可能遇到的问题并计算出你所希望做出的反应。核心问题是：“你何时花费更多的时间在调试程序上，你何时放弃并继续做下一题？”。考虑以下问题： 你已经花费了多长时间来调试它？ 你可能有什么样的BUG（BUG是指程序中的错误）？ 你的算法有错吗？ 你的数据结构需要改变吗？ 你是否对什么地方可能会出错有一些头绪？ 花费较短的时间（20分钟）在调

4、试上比切换去做其他别的事要好；但是你或许能够在45分钟解决另一个问题（？原文是A short amount (20 mins) of debugging is better than switching to anything else; but you might be able to solve another from scratch in 45 mins.） 你何时返回到一个你先前放弃的问题？ 你何时花费较多的时间优化一个程序，你何时放弃当前优化工作而切换去作其他事？ 从这里考虑出去（？原文是Consider from here out）忘记先前的努力，着眼于将来：你如何才能就你目前所

5、有的抓住下一个小时。 在你上交你的答案之前列出一个校验表： 在竞赛结束前五分钟冻结代码？（？原文是Code freeze five minutes before end of contest?） 将所有的声明关闭。 将调试输出关闭。 确认输入输出文件名正确。 确认输入输出格式正确。 重新编译并再测试一次。 将文件以正确的文件名复制到正确的位置（软盘）。 提示和技巧 如果可以就用暴力法（即穷举法）解决 （注：居然将这条作为技巧，可见竞赛的目的就是获奖，为此要“不择手段”。） 键索引顺序搜索（KISS= Keyed Indexed Sequential Search）：简单就是聪明！（？原文是KI

6、SS: Simple is smart!） 提示：注意限制（在问题述中指明） 如果可以给你带来方便的话就浪费存（假如你能侥幸逃脱处罚的话） 不要删除你额外的调试输出，将它注释起来 逐渐地优化，足够了即可 保留所有的工作版本 从编码到调试： 空白是好的（？原文是whitespace is good） 使用有意义的变量名 不要重复使用变量 逐步细化 在写代码之前先写注释 有可能的话尽量避免使用指针 避免使用麻烦的动态存：静态地分配所有的东西。 尽量不要使用浮点数；如果你不得不使用，在所有使用的地方设置允许的误差（绝对不要测试两个浮点数相等） 对注释的注释： 不要写得太长，简洁的注解就可以了 解释复

7、杂的功能：+i; /* increase the value of i by 1*/ 这样的注释是毫无意义的。 解释代码中的技巧 将功能模块划定界限并且document （？原文是Delimit & document functional sections） 好像是写给某个了解该问题但并不了解程序代码的聪明人看的 任何你不得不考虑的东西 ？原文是Anything you looked at even once saying, now what does that do again? 总是注释数组的索引次序 记录你每一次竞赛的情况：成功之处、犯的错误，以与何处你可以做得更好；利用这些记录来改进你

8、的策略。 复杂度 基础和阶符号 复杂度分析的基本原理围绕着符号“大O”，例如：O(N).这意味着算法的执行速度或存占用将会随着问题规模的增倍而增倍。一个有着O(N 2)的算法在问题的规模增倍时其运行时间将会减慢4倍（或者消耗4倍的空间）。常数时间或空间消耗的算法用O(1)表示。这个概念同时适用于时间和空间；这里我们将集中讨论时间。 一种推算一个程序的O( ) 运行时间的方法是检查它的循环。嵌套最深的（因而也是最慢的）循环支配着运行时间，同时它也是在讨论O( ) 符号时唯一考虑的循环。有一个单重循环和一个单层嵌套循环（假设每个循环每次执行N次）的程序的复杂度的阶是O(N 2)，尽管程序中同时有一

9、个O(N)循环。 当然，递归也像循环一样计算，并且递归程序可以有像O(b N)， O(N!)， 甚至O(N N)的阶。 经验法则 在分析一个算法以计算出对于一个给定的数据集它可能要运行多长时间的时候，第一条经验法则是：现代（1999）计算机每秒可以进行10M次操作。对于一个有五秒钟时间限制的程序，大约可以处理50M次操作。真正优化的好的程序或许可以处理2倍甚至4倍于这个数目的操作。复杂的算法或许只能处理这个数目的一半。 640K确实是苛刻的存限制。幸运的是，1999-2000赛季将是这个限制的最后一次起作用。 210 约等于10 3 如果有k重嵌套的循环，每重大约循环N次，该程序的复杂度为O(

10、N k)。 如果你的程序有l层递归，每层递归有b个递归调用，该程序复杂度为O(b l)。 当你在处理有关排列组合之类的算法时，记住N个元素的排列有N!个，N个元素的组合或N个元素组成的集合的幂集的有2 n个。 对N个元素排序的最少时间是O(NlogN)。 进行数学计算！将所有的数据加起来。（？原文是Plug in the numbers.） 例子： 一个简单的重复N次的循环复杂度为O(N)： 1 sum=0 2 fori=1ton 3 sum=sum+i 一个双重嵌套循环的复杂度通常为O(N 2)： #fill array a with N elements 1 fori=1ton-1 2 f

11、orj=i+1ton 3 if(aiaj) swap(ai,aj) 注意，虽然这个循环执行了N(N+1)/2 次if语句，但他的复杂度仍然是O(N 2)，因为N加倍后执行时间增加了四倍。 解决方案的例 产生器 vs. 过滤器 产生大量可能的答案然后选择其中正确的（比如8皇后问题的解答），这样的程序叫做过滤器。那些只产生正确答案而不产生任何错误节点的叫做产生器。一般来说，过滤器较容易（较快）编程实现但是运行较慢。通过数学计算来判断一个过滤器是否足够好或者是否你需要尝试制作一个产生器。 预先计算 有时生成表格或其他数据结构以便快速查找结果是很有用的。这种方法叫做预先计算（在这里用空间换取时间）。你

12、可以将需要预先计算的数据和程序一起编译，在程序开始时计算；也可以干脆记住预先计算出的结果。比如说，一个程序需要将大写字母转化为小写字母，可以不需任何条件地利用一个表格进行快速查找来实现。竞赛题经常要用到素数生成一长串素数在程序中某处使用通常是很实用的。 分解（编程竞赛中最困难的事） 虽然在竞赛中经常使用的基本算法不超过20种，但是某些需要将两种算法结合才能解决的组合型问题却是很复杂的。尽量将问题不同部分的线索分离开来以便你可以将一个算法和一个循环或其他算法结合起来以独立地解决问题的不同部分。注意，有时你可以对你的数据的不同（独立）部分重复使用一样的算法以有效地改进程序的运行时间。 对称 许多问

13、题中存在着对称（例如，无论你按哪一个方向，一对点之间的距离通常是一样的）。对称可以是2路的（？原文是2-way），4路的，8路的或是更多的。尽量利用对称以减少运行时间。 例如，对于4路对称，你只需解决问题的四分之一，就可以写下4个结果，这四个结果和你所解决的一个结果是对称的（注意自对称的解答，他当然只应该被输出一次或两次）。 正向 vs. 逆向 令人惊讶地，许多竞赛题用逆向法解决比正面突破要好得多。以逆序处理数据或构造一种基于某种非明显的方式或顺序检索数据的突破策略时，要特别小心。 简化 某些问题可以被改述为一个有点不同的其他问题，这样你解决了新问题，就已经有了原始问题的答案或者容易找出原始问

14、题的答案；当然，你只需解决两者之中较容易的那个。另外，像归纳法一样，你可以对一个较小的问题的解答作一些小小的改变以得到原问题的完整答案。 Receipted from ace.delos./usacogate/ Translated by Starfish 原文： Crafting Winning Solutions A good way to get a competitive edge is to write down a game plan for what youre going to do in a contest round. This will help you script o

15、ut your actions, in terms of what to do both when things go right and when things go wrong. This way you can spend your thinking time in the round figuring out programming problems and not trying to figure out what the heck you should do next. its sort of like precomputing your reactions to most sit

16、uations. Mental preparation is also important. Game Plan For A Contest Round Read through ALL the problems FIRST; sketch notes with algorithm, complexity, the numbers, data structs, tricky details, . Brainstorm many possible algorithms - then pick the stupidest that works! DO THE MATH! (space & time

17、 complexity, and plug in actual expected and worst case numbers) Try to break the algorithm - use special (degenerate?) test cases Order the problems: shortest job first, in terms of your effort (shortest to longest: done it before, easy, unfamiliar, hard) Coding a problem - For each, one at a time:

18、 Finalize algorithm Create test data for tricky cases Write data structures Code the input routine and test it (write extra output routines to show data?) Code the output routine and test it Stepwise refinement: write comments outlining the program logic Fill in code and debug one section at a time

19、Get it working & verify correctness (use trivial test cases) Try to break the code - use special cases for code correctness Optimize progressively - only as much as needed, and keep all versions (use hard test cases to figure out actual runtime) Time management strategy and damage control scenarios

20、Have a plan for what to do when various (foreseeable!) things go wrong; imagine problems you might have and figure out how you want to react. The central question is: When do you spend more time debugging a program, and when do you cut your losses and move on?. Consider these issues: How long have y

21、ou spent debugging it already? What type of bug do you seem to have? Is your algorithm wrong? Do you data structures need to be changed? Do you have any clue about whats going wrong? A short amount (20 mins) of debugging is better than switching to anything else; but you might be able to solve anoth

22、er from scratch in 45 mins. When do you go back to a problem youve abandoned previously? When do you spend more time optimizing a program, and when do you switch? Consider from here out - forget prior effort, focus on the future: how can you get the most points in the next hour with what you have? H

23、ave a checklist to use before turning in your solutions: Code freeze five minutes before end of contest? Turn asserts off. Turn off debugging output. Turn on all optimizations. Make sure input and output are to correct filenames. Make sure the input and output formats are correct. Recompile and test

24、 once more. Copy files to correct locations (floppy?) with correct names. Tips & Tricks Brute force it when you can KISS: Simple is smart! Hint: focus on limits (specified in problem statement) Waste memory when it makes your life easier (if you can get away with it) Dont delete your extra debugging

25、 output, comment it out Optimize progressively, and only as much as needed Keep all working versions! Code to debug: whitespace is good, use meaningful variable names, dont reuse variables, stepwise refinement, COMMENT BEFORE CODE. Avoid pointers if you can Avoid dynamic memory like the plague: stat

26、ically allocate everything. Try not to use floating point; if you have to, put tolerances in everywhere (never test equality) Comments on comments: Not long prose, just brief notes Explain high-level functionality: +i; /* increase the value of i by */ is worse than useless Explain code trickery Deli

27、mit & document functional sections As if to someone intelligent who knows the problem, but not the code Anything you had to think about Anything you looked at even once saying, now what does that do again? Always comment order of array indices Keep a log of your performance in each contest: successe

28、s, mistakes, and what you could have done better; use this to rewrite and improve your game plan! Complexity Basics and order notation The fundamental basis of complexity analysis revolves around the notion of big oh notation, for instance: O(N). This means that the algorithms execution speed or mem

29、ory usage will double when the problem size doubles. An algorithm of O(N 2) will run about four times slower (or use 4x more space) when the problem size doubles. Constant-time or space algorithms are denoted O(1). This concept applies to time and space both; here we will concentrate discussion on t

30、ime. One deduces the O( ) run time of a program by examining its loops. The most nested (and hence slowest) loop dominates the run time and is the only one mentioned when discussing O( ) notation. A program with a single loop and a nested loop (presumably loops that execute N times each) is O(N 2),

31、even though there is also a O(N) loop present. Of course, recursion also counts as a loop and recursive programs can have orders like O(b N), O(N!), or even O(N N). Rules of thumb When analyzing an algorithm to figure out how long it might run for a given dataset, the first rule of thumb is: modern

32、(1999) computers can deal with 10M actions per second. In a five second time limit program, about 50M actions can be handled. Really well optimized programs might be able to double or even quadruple that number. Challenging algorithms might only be able to handle half that much. 640K is a really tig

33、ht memory constraint. Happily, the 1999-2000 season is the last time this constraint applies. 210 approx 10 3 If you have k nested loops running about N iterations each, the program has O(N k) complexity. If your program is recursive with b recursive calls per level and has l levels, the program O(b

34、 l) complexity. Bear in mind that there are N! permutations and 2 n subsets or combinations of N elements when dealing with those kinds of algorithms. The best times for sorting N elements are O(N log N). DO THE MATH! Plug in the numbers. Examples A single loop with N iterations is O(N): 1 sum=0 2 f

35、ori=1ton 3 sum=sum+i A double nested loop is often O(N 2): #fill array a with N elements 1 fori=1ton-1 2 forj=i+1ton 3 if(aiaj) swap(ai,aj) Note that even though this loop executes N x (N+1) / 2 iterations of the if statement, it is O(N 2) since doubling N quadruples the execution times. Solution Pa

36、radigms Generating vs. Filtering Programs that generate lots of possible answers and then choose the ones that are correct (imagine an 8-queen solver) are filters. Those that hone in exactly on the correct answer without any false starts are generators. Generally, filters are easier (faster) to code

37、 and run slower. Do the math to see if a filter is good enough or if you need to try and create a generator. Precomputation Sometimes it is helpful to generate tables or other data structures that enable the fastest possible lookup of a result. This is called precomputation (in which one trades spac

38、e for time). One might either compile precomputed data into a program, calculate it when the program starts, or just remember results as you compute them. A program that must translate letters from upper to lower case when they are in upper case can do a very fast table lookup that requires no condi

39、tionals, for example. Contest problems often use prime numbers - many times it is practical to generate a long list of primes for use elsewhere in a program. Decomposition (The Hardest Thing At Programming Contests) While there are fewer than 20 basic algorithms used in contest problems, the challen

40、ge of combination problems that require a combination of two algorithms for solution is daunting. Try to separate the cues from different parts of the problem so that you can combine one algorithm with a loop or with another algorithm to solve different parts of the problem independently. Note that sometimes yo