Crafting Winning Solutions 制作获奖解题方法

A good way to get a competitive edge is to write down a game plan for what you’re going to do in a contest round. This will help you script out 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… it’s sort of like precomputing your reactions to most situations.

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 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:

• 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
• 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

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 you 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 what’s going wrong?
• 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.
• When do you go back to a problem you’ve 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?

Have a checklist to use before turning in your solutions:

• Code freeze five minutes before end of contest?
• Turn asserts off.
• Turn off debugging output.

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)
• Don’t delete your extra debugging 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,
  • don’t reuse variables,
  • stepwise refinement,
  • COMMENT BEFORE CODE.
• Avoid pointers if you can
• Avoid dynamic memory like the plague: statically 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
  • Delimit & 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: successes, 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 algorithm’s execution speed or memory usage will double when the problem size doubles. An algorithm of O(N ²) 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 time.

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 ²), 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 (2004) computers can deal with 100M actions per second. In a five second time limit program, about 500M 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. Current contests usually have a time limit of 1 second for large datasets.
• 16MB maximum memory use
• 2¹⁰ ~approx~ 10 ³
• 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 ^l) complexity.
• Bear in mind that there are N! permutations and 2 ⁿ subsets or combinations of Nelements 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  for i = 1 to n
 3    sum = sum + i

A double nested loop is often O(N ²): 

# fill array a with N elements
1 for i = 1 to n-1
2   for j = i + 1 to n
3     if (a[i] > a[j])
         swap (a[i], a[j])
Note that even though this loop executes N x (N+1) / 2 iterations of the if statement, it is O(N ²) since doubling N quadruples the execution times.

Consider this well balanced binary tree with four levels: 

An algorithm that traverses a general binary tree will have complexity O(2 ^N).

Solution Paradigms

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 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 space 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 conditionals, 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 challenge 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 you can use the same algorithm twice on different (independent!) parts of your data to significantly improve your running time.

Symmetries

Many problems have symmetries (e.g., distance between a pair of points is often the same either way you traverse the points). Symmetries can be 2-way, 4-way, 8-way, and more. Try to exploit symmetries to reduce execution time.

For instance, with 4-way symmetry, you solve only one fourth of the problem and then write down the four solutions that share symmetry with the single answer (look out for self-symmetric solutions which should only be output once or twice, of course).

Forward vs. Backward

Surprisingly, many contest problems work far better when solved backwards than when using a frontal attack. Be on the lookout for processing data in reverse order or building an attack that looks at the data in some order or fashion other than the obvious.

Simplification

Some problems can be rephrased into a somewhat different problem such that if you solve the new problem, you either already have or can easily find the solution to the original one; of course, you should solve the easier of the two only. Alternatively, like induction, for some problems one can make a small change to the solution of a slightly smaller problem to find the full answer.

获得竞争优势的一个好方法是写下一个你在比赛中要做什么的比赛计划。这可以帮助你制定出你的行动，就事情进展顺利和事情出错时该做什么而言。通过这种方式，您可以花费自己的思考时间来全面了解编程问题，而不是试图弄清楚接下来应该做什么……这就像对大多数情况的预计算一样。

心理准备也很重要。

比赛回合的比赛计划

通读所有的问题; 草图笔记与算法，复杂性，数字，数据结构，棘手的细节，…

• 头脑风暴许多可能的算法 – 然后选择最愚蠢的工作！
• 算一算！（空间和时间复杂性，并插入实际预期和最差情况下的数字）
• 尝试打破算法 – 使用特殊（退化？）测试用例
• 为了解决这些问题：首先要做到最短的工作，就你的努力而言（最短到最长：以前做过，简单，不熟悉，很难）

编码问题 – 对于每个问题，一次一个：

• 完成算法
• 为棘手的情况创建测试数据
• 写数据结构
• 对输入例程进行编码并对其进行测试（编写额外的输出例程以显示数据？）
• 编写输出例程并对其进行测试
• 逐步细化：写评论概述程序逻辑
• 一次填写代码并调试一个部分
• 让它工作并验证正确性（使用琐碎的测试用例）
• 尝试激活成功教程代码 – 使用代码正确性的特殊情况
• 逐步优化 – 只根据需要进行优化，并保留所有版本（使用硬测试用例来计算实际运行时）

时间管理策略和“损害控制”方案

当各种（可预见的！）事情出错时，制定计划做什么; 想象你可能遇到的问题并找出你想如何反应。核心问题是：“你什么时候花更多的时间来调试一个程序，你什么时候减少你的损失，然后继续前进？”。考虑以下问题：

• 你花了多长时间调试它？
• 你看起来有什么类型的错误？
• 你的算法错了吗？
• 您是否需要更改数据结构？
• 你有什么问题的线索吗？
• 少量（20分钟）的调试比切换到其他任何东西都好; 但是你可以在45分钟内从头开始解决另一个问题。
• 你什么时候回到以前遗弃的问题？
• 你什么时候花更多的时间来优化一个程序，你什么时候切换？
• 从这里考虑 – 忘记先前的努力，关注未来：你如何在下一个小时内获得最多的积分？

在提交解决方案之前，请准备一份清单：

比赛结束前五分钟停止代码冻结？
打开关闭。
关闭调试输出。

提示与技巧

• 尽可能蛮力
• 吻：简单聪明！
• 提示：关注限制（在问题陈述中指定）
• 浪费记忆，让你的生活更轻松（如果你能逃脱它）
• 不要删除额外的调试输出，将其注释掉
• 逐步优化，并且只根据需要进行优化
• 保留所有工作版本！
• 要调试的代码：
  • 空白是好的，
  • 使用有意义的变量名，
  • 不要重用变量，
  • 逐步细化，
  • 在代码之前的评论。
• 如果可以，请避免使用指针
• 避免像瘟疫一样的动态记忆：静态分配一切。
• 尽量不要使用浮点; 如果必须，将公差放在任何地方（从不测试平等）
• 评论意见：
  • 不久散文，只是简短的笔记
  • 解释高级功能：++ i; / *通过* /增加i的值比无用更差
  • 解释代码欺骗
  • 分隔和文件功能部分
  • 就好像有人知道这个问题，但不知道这个问题
  • 任何你必须考虑的事情
  • 你甚至曾经说过的任何东西，“现在再怎么样呢？”
  • 始终注释数组索引的顺序
• 记录每次比赛中的表现：成功，失误，以及你可以做得更好; 用它来重写和改进你的游戏计划！

复杂

基础知识和订单表示法

复杂性分析的基本基础围绕着“大哦”符号的概念，例如：O（N）。这意味着当问题大小加倍时，算法的执行速度或内存使用量将翻倍。当问题大小加倍时，O（N ²）算法的运行速度会慢四倍（或者使用4倍的空间）。恒定时间或空间算法表示为O（1）。这个概念既适用于时间和空间; 在这里，我们将集中讨论时间。

通过检查程序的循环来推导程序的运行时间。循环最多（因此最慢）循环支配运行时间，是讨论O（）符号时唯一提到的循环。具有单个循环和嵌套循环的程序（可能是每个执行N次的循环）是O（N ²），即使存在O（N）循环也是如此。

当然，递归也算作循环，递归程序可以有O（b ^N），O（N！）或甚至O（N ^N）的顺序。

经验法则

• 在分析一个算法以确定给定数据集运行多长时间时，第一条经验法则是：modern（2004）计算机可以每秒处理100M行为。在五秒时间限制计划中，可以处理大约五亿个行动。真正优化的程序可能会使这个数字增加一倍甚至四倍。具有挑战性的算法可能只能处理一半。对于大型数据集，当前竞赛通常有1秒的时间限制。
• 最大内存使用量为16MB
• 2 ¹⁰〜约10〜³
• 如果您有k个嵌套循环， 每个循环运行约N次，则程序具有O（N ^k）复杂性。
• 如果你的程序是递归调用，每个级别有b个递归调用，并且具有l个级别，则程序O（b ^l）复杂。
• 请记住，有N！在处理这些算法时，排列和2 ⁿ个子集或N个元素的组合。
• 排序N个元素的最佳时间是O（N log N）。
• 算一算！ 插入数字。

例子

具有N次迭代的单个循环是O（N）：  1  对于i = 1到n  3，sum = 0 2 sum = sum + i

双重嵌套循环通常是O（N ²）： ＃ 如果（a [i]> a [j]），则用N个元素 1 填充数组a，对于i = 1到n-1 2，对于j = i + 1到n 3，         swap（a [i]，a [j]） 请注意，即使此循环执行 if语句的N x（N + 1）/ 2次迭代，也是O（N ²），因为加倍N会使执行时间增加 四倍。 

考虑这个具有四个层次的平衡二叉树： 

遍历一般二叉树的算法将具有复杂度O（2 ^N）。

解决方案范例

生成与过滤

生成大量可能答案然后选择正确答案的程序（想象一个8王后解算器）是 过滤器。那些在没有任何错误启动的情况下正确磨练正确答案的人就是生成器。一般来说，过滤器更容易（更快）编码和运行速度较慢。做数学计算以查看过滤器是否足够好，或者如果您需要尝试创建生成器。

预计算

有时，生成表格或其他数据结构可以实现对结果的尽可能快的查找。这被称为预计算（其中一个交易时间空间）。可以将预先计算的数据编译成程序，在程序启动时计算它，或者在计算时记住结果。例如，在大写的情况下，必须将字母从大写字母转换为小写字母的程序可以进行非常快速的表格查找，而不需要条件语句。比赛问题通常使用素数 – 很多时候生成一长串素数以便在程序的其他地方使用是很实际的。

分解（编程竞赛中最难的事）

虽然比赛问题中使用的基本算法少于20个，但需要将两种算法结合使用以解决问题的组合问题面临的挑战令人望而生畏。尝试从问题的不同部分分离线索，以便您可以将一个算法与一个循环或另一个算法组合，以独立解决问题的不同部分。请注意，有时您可以在数据的不同（独立！）部分使用相同的算法两次，以显着缩短您的运行时间。

对称性

许多问题具有对称性（例如，一对点之间的距离通常与遍历点的方式相同）。对称性可以是2路，4路，8路等。尝试利用对称性来减少执行时间。

例如，使用4向对称，您只能解决问题的四分之一，然后记下与单一答案共享对称性的四个解决方案（注意自我对称解决方案，当然应该只输出一次或两次，当然）。

前进与后退

令人惊讶的是，许多比赛问题在向后解决时比使用正面攻击时效果更好。注意以相反的顺序处理数据，或者构建一种以明显的顺序或方式查看数据的攻击。

简单化

有些问题可以转化为一个不同的问题，如果你解决了新的问题，你可能已经或很容易找到原来的解决方案; 当然，你应该解决两个更容易的问题。或者，像感应一样，对于某些问题，可以对稍微小一点的问题的解决方案进行小的改变以找到完整的答案。

今天的文章Crafting Winning Solutions 制作获奖解题方法分享到此就结束了，感谢您的阅读。