/
Crafting Winning Solutions.html
371 lines (242 loc) · 12 KB
/
Crafting Winning Solutions.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
<!-- saved from url=(0055)http://train.usaco.org/usacotext2?a=zWju1un286A&S=craft -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Crafting Winning Solutions
</title>
</head><body bgcolor="#f0f0f0">
<font face="Verdana,Tahoma,sans-serif,Arial,Lucida Sans,Gill Sans">
<div style="width:45em;background-color:white;border-style:solid;border-width:1px;padding:1em;">
<table cellspacing="8">
<tbody><tr><td><img src="./Crafting Winning Solutions_files/cowhead2.gif"></td>
<td> </td>
<td><b><font size="5">
<font face="Verdana,Tahoma,sans-serif,Arial,Lucida Sans,Gill Sans">
Crafting Winning Solutions
</font></font></b></td>
</tr>
</tbody></table>
<p> 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.
</p><p>
Mental preparation is also important.
</p><h4>Game Plan For A Contest Round</h4>
<p> Read through ALL the problems FIRST; sketch notes with algorithm,
complexity, the numbers, data structs, tricky details, ...
</p><ul>
<li> Brainstorm many possible algorithms - then pick the stupidest
that works!</li>
<li> DO THE MATH! (space & time complexity, and plug in actual
expected and worst case numbers)</li>
<li> Try to break the algorithm - use special (degenerate?) test
cases</li>
<li> Order the problems: shortest job first, in terms of your effort
(shortest to longest: done it before, easy, unfamiliar, hard) </li>
</ul>
<p> Coding a problem - For each, one at a time:
</p><ul>
<li>Finalize algorithm</li>
<li>Create test data for tricky cases</li>
<li>Write data structures</li>
<li>Code the input routine and test it (write extra output routines to show
data?)</li>
<li> Code the output routine and test it </li>
<li>Stepwise refinement: write comments outlining the program logic</li>
<li>Fill in code and debug <i>one section at a time</i></li>
<li>Get it working & verify correctness (use trivial test cases)</li>
<li>Try to break the code - use special cases for code correctness</li>
<li> Optimize progressively - only as much as needed, and keep all
versions (use hard test cases to figure out actual runtime)</li>
</ul>
<h4>Time management strategy and "damage control" scenarios </h4>
<p> 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:
</p><ul>
<li> How long have you spent debugging it already? </li>
<li> What type of bug do you seem to have? </li>
<li> Is your algorithm wrong? </li>
<li> Do you data structures need to be changed? </li>
<li> Do you have any clue about what's going wrong? </li>
<li> 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. </li>
<li> When do you go back to a problem you've abandoned previously? </li>
<li> When do you spend more time optimizing a program, and when do you switch? </li>
<li> 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? </li>
</ul>
<p>
Have a checklist to use before turning in your solutions:
</p><ul>
Code freeze five minutes before end of contest?
<li> Turn asserts off. </li>
<li> Turn off debugging output. </li>
</ul>
<h4>Tips & Tricks</h4>
<ul>
<li> Brute force it when you can </li>
<li>KISS: Simple is smart! </li>
<li>Hint: focus on <i>limits</i> (specified in problem statement) </li>
<li>Waste memory when it makes your life easier (if you can get away with it) </li>
<li>Don't delete your extra debugging output, comment it out </li>
<li> Optimize progressively, and only as much as needed </li>
<li> Keep all working versions! </li>
<li> Code to debug: </li>
<ul type="square">
<li>whitespace is good,</li>
<li>use meaningful variable names,</li>
<li>don't reuse variables,</li>
<li>stepwise refinement,</li>
<li>COMMENT BEFORE CODE.</li>
</ul>
<li>Avoid pointers if you can</li>
<li>Avoid dynamic memory like the plague: statically allocate everything.</li>
<li>Try not to use floating point; if you have to, put tolerances in
everywhere (never test equality)</li>
<li>Comments on comments:
<ul type="square">
<li> Not long prose, just brief notes </li>
<li> Explain high-level functionality: ++i; /* increase the
value of i by */ is worse than useless
</li><li>Explain code trickery</li>
<li>Delimit & document functional sections </li>
<li>As if to someone intelligent who knows the problem, but not the code </li>
<li>Anything you had to think about </li>
<li>Anything you looked at even once saying, "now what does
that do again?" </li>
<li>Always comment order of array indices </li>
</ul>
</li><li>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!</li>
</ul>
<h4>Complexity</h4>
<h5> Basics and order notation </h5>
<p> The fundamental basis of complexity analysis revolves around the
notion of ``big oh'' notation, for instance: O(<i>N</i>). This means
that the algorithm's execution speed or memory usage will double when
the problem size doubles. An algorithm of O(<i>N <sup>2</sup></i>) 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.
</p><p> 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 <i>N</i> times each) is O(<i>N <sup>2</sup></i>),
even though there is also a O(<i>N</i>) loop present.
</p><p>Of course, recursion also counts as a loop and recursive programs
can have orders like O(<i>b <sup>N</sup></i>), O(<i>N!</i>), or
even O(<i>N <sup>N</sup></i>).
</p><h4> Rules of thumb </h4>
<ul>
<li> 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.</li>
<li> 16MB maximum memory use
</li><li> 2<sup>10 </sup> ~approx~ 10 <sup>3 </sup></li>
<li> If you have <i>k</i> nested loops running about <i>N</i>
iterations each, the program has O(<i>N <sup>k</sup></i>) complexity.</li>
<li> If your program is recursive with <i>b</i> recursive calls per
level and has <i>l</i> levels, the program O(<i>b <sup>l</sup></i>)
complexity.</li>
<li> Bear in mind that there are <i>N!</i> permutations and <i>2
<sup>n</sup></i> subsets or combinations of <i>N</i> elements when
dealing with those kinds of algorithms.</li>
<li>
The best times for sorting <i>N</i> elements are O(<i>N</i> log<i> N</i>).</li>
<li> <b>DO THE MATH!</b> Plug in the numbers.</li>
</ul>
<h4> Examples </h4>
<p>
A single loop with <i>N</i> iterations is O(<i>N</i>):
<br>
<tt><font size="2"> <br>
1 sum = 0<br>
2 for i = 1 to n<br>
3 sum = sum + i<br>
</font></tt>
</p><p>A double nested loop is often O(<i>N <sup>2</sup></i>):
<br>
<tt><font size="2"> <br>
# fill array a with N elements<br>
1 for i = 1 to n-1<br>
2 for j = i + 1 to n<br>
3 if (a[i] > a[j])<br>
swap (a[i], a[j])<br>
</font></tt>
Note that even though this loop executes <i>N x (N+1) / 2</i>
iterations of the if statement, it is O(<i>N <sup>2</sup></i>) since doubling
<i>N</i> quadruples the execution times.
</p><p>
Consider this well balanced binary tree with four levels:
<br><img src="./Crafting Winning Solutions_files/craft1.gif"><br>
An algorithm that traverses a general binary tree will have complexity
O(<i>2 <sup>N</sup></i>).
</p><h4>Solution Paradigms </h4>
<h5> Generating vs. Filtering </h5>
<p> Programs that generate lots of possible answers and then choose
the ones that are correct (imagine an 8-queen solver) are
<i>filters</i>. Those that hone in exactly on the correct answer
without any false starts are <i>generators</i>. 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.
</p><h5> Precomputation </h5>
<p> Sometimes it is helpful to generate tables or other data
structures that enable the fastest possible lookup of a result.
This is called <i>precomputation</i> (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.
</p><h5> Decomposition (The Hardest Thing At Programming Contests) </h5>
<p> 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.
</p><h5> Symmetries </h5>
<p> 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.
</p><p> 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).
</p><h5> Forward vs. Backward </h5>
<p> 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.
</p><h5> Simplification </h5>
<p> 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.
</p></div><br>
<center>
<a href="http://train.usaco.org/usacogate?a=zWju1un286A">USACO Gateway</a> | <a href="mailto:rob.kolstad@gmail.com">Comment or Question</a>
</center>
</font></body></html>