![[logo]](ecr.gif)
Back to information on the whole contest.
Back to information on the whole contest.
This document is intended to help you be a better contestant. In the past, teams have gone to the regionals (and even the finals), fully expecting to do well, but not solving any problems. I hope that after reading this, all teams will know enough to get the easy problems. The other goal is that teams will understand why their programs are failing.
In past years, some contestants came to the regionals with the wrong mindset. In Q&A, someone asked `What documentation are we supposed to provide?' and I've heard of teams that fought over the importance of code reuse in software design methodology. If you don't already know it, the objective is to write the simplest, dirtiest hack that gets through the judging data.
The reason why you want your code to be intelligible is that your team members need to be able to debug your code. Software reuse doesn't exist outside of the contest, and is often assisted by search and replace. Design decisions should favour getting it right the first time, or at least easy debugging. You can write things that would make your employers and TAs scream, just so long as you can make it work.
Your overall strategy should be to find the problems that are easiest to solve, no matter how hard the judges try to hide them, and solve them. When I was at the finals, one team tried to solve the hardest problem (Trucking) first. No team managed to solve it, and I consider the problem specification to be full of bugs. Any guesses what this did to their final score? Moreover, solving easy problems first will decrease your time penalty. Even without solving more problems or getting fewer incorrects, this will improve your time.
If you haven't trained for speed coding of easy problems, take your time and solve them. Not rushing will improve your performance, because debugging the simple programs will take longer than writing them from scratch. This is probably true of all of the problems, but teams that can't get the bugs out of their code won't ever get to the harder problems.... You do know that you aren't allowed to use a debugger during the regionals, don't you?
Being the first team to solve all of the problems is not the point of the practice contest. Use your time to try out the environment, test error responses, send clarifications and find out how much you can do in 5 seconds of CPU time.
Judges don't want to put easy problems on the contest, because they have thought up too many difficult problems. So what we do is hide the easy problems, hoping that you will be tricked into working on the harder ones. If we want you to add two non-negative numbers together, there will be pages of text on the addition of `0' to the number system and 3D-pictures to explain the process of addition as it was imagined on some island that nobody has ever heard of.
Once we've scared you away from the easy problems, we make the hard ones look easy. `Given two polygons, find the area of their intersection.' Easy, right?
Sometimes the judges get meta-nasty and write problems like `given two regular polygons of 4 vertices, sides parallel to the coördinate axes, find the area of their intersection'. Hmmn, not quite so hard as the previous problem. The limitations on the problem might only appear in the input specification, too.
It isn't always obvious that a problem is easy, so teams ignore the problems or start on an overly complex approaches to them. Remember, there are dozens of other teams working on the same problems, and they will help you find the easy problems. If everyone is solving problem G, maybe you should take another look at it.
Read the Jargon File entry on brute force. That pretty much says it all.
Write test programs during the practice session to find out just how much you can do in the CPU time available. When you read a problem description, look at the size of the possible inputs to the problem. If a O(n!) or O(2n) algorithm will work, then go for it.
But do you really think the judges are going to let you use brute force? There was a TSP problem with at most 8 cities on a final, so sometimes the answer is `yes'. More often, if an NP-complete problem is put on a contest, you are expected to come up with some simple heuristics that will make your program efficient on most cases. (Usually there are only a few instances of NP-complete problems that are difficult, and figuring out how to solve these efficiently would get you the Turing Award.)
Sizing applies to problems with obvious polynomial size algorithms. How big is the data? Can you use a O(n2) sort/linear insertion/whatever, or do you need a O(n lg n) sort/priority queue/hash table/invent-your-own-data-structure-here?
If you think about a problem too hard, then even the most trivial problem can become a monster. Sometimes you just need to ask yourself, `is this an easy or a hard problem?'.
An important class of problems (for programming contestants, at least) contains problems that look exponential, but can be solved by low-order polynomial algorithms. These are often solved by memoization or dynamic programming.
If you write a program with a recursive algorithm that calls itself with the same arguments many times, the simplest thing to use is memoization -- storing the results of previous computations for later use. Anybody can do this without the rigorous physical training in the mountains that is used to prepare dynamic programmers. Here is a trival example that should be familiar to most people. If you are asked to find the nth Fibonacci number, the obvious algorithm is
F(n) = if n < 2 then 1
else F(n-1)+F(n-2)
But if you try that for large n, just how many times does the function call itself recursively? Now consider this slight change:
f[1] := 1 f[2] := 1 f[3..BIGNUM] := -1 F(n) = if f[n] < 0 then f[n] := F(n-1)+F(n-2); f[n]
This sort of strategy is easy to implement. All you ever need to do is check a table listing all possible arguments at the start of an inefficient recursive function and assign to the table when you return from the function. (But don't forget to think about the size of the table.)
Sometimes a problem is not structured in a way that makes memoization possible (maybe the table is too big). Or perhaps you want to create a straight-forward iterative program. Dynamic programming consists of systematically rewriting a problem so that it is built from optimal solutions to sub-problems. This process takes some getting used to.
The `programming' in `dynamic programming' has the same meaning as the one on `linear programming'. It refers to the table of values. For people that haven't seen this technique before, I will give two classic examples. I will describe the contents of the tables that are used and you figure out how to fill the tables and write your own solutions to the problems.
Using Canadian or US coins, we can make change for n cents using as few coins as possible by using as many of the biggest coins as possible. But what if we had coins worth 17, 8 and 1 cents? Then to make change for 24 cents, that algorithm would use a 17-cent coin and 7 1-cent coins instead of 3 8-cent coins. How can you find the minimum number of coins? Use a table in which M[n] is the minimum number of coins required to make change for n cents. So, how can you fill in that table using the results of smaller problems?
Given two strings of characters, one way of determining how similar they are is to find out how many characters must be deleted before they are identical. (If the strings contain no characters in common, then the answer is `all of them'.) This has applications in DNA research and file comparison (as in the diff(1) program). The table this time is one in which M[m][n] is the fewest number of deletions required to make the first m characters of the first string and the first n characters of the second string the same.
How can you find out which coins should be used? Which characters are left in the strings?