|
Tips & Tricks
This section is a compilation of various tips and tricks that we have picked up
over the past two years of competing in various competitions.
- Read problems carefully - This seems obvious, however, there's
been many times where sloppy reading has cost us several hours of
competition time (eg. Regionals 2003). With all the pressure and
excitement at the beginning of a competition, it's often tempting to rush
right in, in order to start getting something done, however, if you aren't
careful, you may misinterpret the problem and code the wrong algorithm.
It's better to take a few extra minutes, guarantee that you have the right
idea, and then begin.
- Team strategy - When working as a team, it's important to have a
team strategy and follow it. You don't want to be fighting over the
computer, and you need to know your team members strengths and weaknesses.
Know what everyone is working on, and discuss ideas. Never waste time over
a syntax or logic issue when your team members could answer your questions.
Keep in mind that you have only 5 computing hours, but 15 man/woman hours.
Try to limit the amount of thinking time you do in front of the terminal.
Code and debug on paper as much as possible, and try to limit terminal time
to hacking code in from paper.
- Have your own algorithm implementations - Remember, you are
allowed to bring in any non-electronic resources you want, this includes
books and source code print outs. It's important to have your own
implementations of known algorithms. Trying to implement an algorithm from
pseudocode in some textbook during competition is probably not going to be
very successful unless you are extremely familiar with it. Having your own
working implementations will greatly increase your chances of coding it
correctly. Personally, I find that having your geometry routines pre-coded
is extremely helpful when dealing with geometry problems. We always bring
books into our competitions, but in all the competitions we've competed in
(practice and real), we have never once looked in a book. As our old coach
Oleg Golubitsky use to say, ultimately, it's what is in your head that
counts.
- Know your algorithms - You don't have to be a super genius to do
well in these competitions (although it probably helps). If you know your
standard algorithms, it will greatly improve your success. There's usually
a problem or two that uses a standard algorithm, or is similar to a
standard algorithm. Even if you are a super genius, knowing these
algorithms will cut down on the number of original problem solutions that
you have to cook up.
- Check problem constraints - Checking problem constraints, such
as how big the input will be, often gives you hints about what type of
algorithm you're going to need (ie. O(N^2), O(N^3), etc). Sometimes,
bruteforce is the solution, or atleast, it will get the job done.
- Pretty code is not essential - No one actually cares what your
code looks like, except maybe your team members; the judge simply compiles
it and runs it, if it produces correct output, then it's right. It's
important to keep your code clean enough for your team members to read and
understand it if necessary, but it doesn't have to something you'd give to
your boss. Graham Fyffe and I (Sean Falconer) always strive for what we
call 'tight' and 'clean' code. Tight means that the code is small (less
typing is faster), and clean means it's readable. Often, when I
practice, I'll solve a problem or take someone's solution, and try to cut
the code down and speed it up. I find this is good practice, because simple
optimizations that you make, can then be adapted to your regular coding
style.
- Avoid getting stuck - Sometimes you can get stuck on a
problem. You have what seems to be the correct solution, and all your test
cases work, but you keep getting wrong answer. In this type of situation,
it's tempting to keep banging away at it, trying to get it accepted, but
sometimes it may be better to move on to another problem. If there's
another problem that you know you can code, do that one, and come back to
this one. Or have a team mate try to break it, sometimes they'll see
something that you can't. At the last APICS competition, after I had my
first problem accepted, I did another one, it was an easy problem, and the
code was only like 70 lines, but I got wrong answer. I tried a few things
and kept getting wrong answer. Eventually, around the 3 and a half hour
mark, they told us there was an error in the problem. I then got it
accepted, but I had wasted 2 and a half hours. Also, the year before in
Rochestor, we kept getting wrong answer on a problem, then with 30 minutes
left in the competition, they told us there was a judging error, and we had
it accepted. This rarely happens in the World Finals, but at the lower
level competitions, this thing is pretty common.
- Work as a team - Try to workout a team strategy that is
applicable for your team make up. However, regardless of your team make up,
you need to work as a team. Often, at the lower level competitions, I see a
lot of teams where one guy is busy using the computer while the other two
guys are watching him. Typically, this is not a good idea, you always want
to be doing something, even if you don't know how to solve any of the
problems, you could be making test cases for your team mates. Also, try to
avoid everyone going off and working completely on their own problems. If
one of your team members runs into issues while trying to solve a
particular problem, it will take you several minutes just to get familiar
with what they are working on before you will be able to help. Try to
discuss your solution ideas first, then when everyone has a plan, go to
work.
|
|