How to Approach a Programing Contest
It is pretty obvious that practicing as a team before the contest is a wise thing to do. Beyond that,
what else should you do? Here are some ideas:
- Do a pretend contest
- do a 1-2 hour pretend contest (at least)
- generate some random numbers to pick problems
- Bring with you what you intend to bring in the real contest (this will go a long way
to making sure you have what you need and help identify additional things)
- Ignore the Internet and just use one computer -- need to get used to that environment
- Use a generic Linux install without all of you normal customizations
- Practice as pairs and as all three on evaluationg problems
- As a pair, try to solve and try to debug a problem
- Go through typing in stubs and using them
- Write lots of partial solutions (just the code to do the input)
- Spend time looking at each others code. Try to develope a common style. At least get
used to each others style so that distraction when helping debug is diminished.
- Spend 5 hours together -- make sure you can do that
- Each member should make a profile (listing their strenghts and weaknesses), dicuss these with
each other. Before the contest is a great time to discover that no one likes certain types of problems.
At least each of you can divvy up those categories and each one of you can get better at one of them.
- Figure out some things in advance:
- Best typist
- Best at syntax error free code
- Best at logic error free code
- Who knows syntax best
- What are the 5-10 mistakes each person tends to make
- Who is good at numeric input
- Who is good at string input
- WHo is good at variable format input
- Who can parse best
What to bring
The first thing you check is the rules. Most contests we participate in limit you to
non-machine readable references and non-computational devices.
Here is a cut at a list:
Reference: Things to think about:
- Language syntax/api reference
- algebra/geometry/statistics - books with formulas
- Data structure examples
- Algorithm examples
- Code Notebook - source code and problem statement of solved problems
- Printout of stub(s)
- Cheat sheets
- Clock that all can see to help with time management
- pencils - several, mechanical with spare lead, or old fashioned with a sharpener
- graph paper - sometimes it helps a lot
- some lined paper
- ruler (straight edge)
- compas or way to draw circles
- stapler with staples
- notebooks/folders to organize problems (may want 3 hole punch)
- Calculator -- if allowed (usually not)
- zip lock bag with your name on it to put phone and other things into that you cannot have
- some candy (not much -- to avoid massize sugar highs/lows/illness)
- bars (like granola or whatever you like)
- water bottle (in case they do not have any)
- mascot or school pennant (something to get excied)
- dice (helpful for visualization if a problem is about dice or cubes)
- cards (helpful if a card based problem shows up)
- rubiks cube (useful for cube problems or rotation problems)
Each of you have written solutions to more than a few problems by now. You should print out your solutions AND
the problem statement that goes with that solution. I wold suggest putting these in a binder with dividers. Also
you should organize them based on type of problem/soltion (or make a table of contents with a list of types
and then a way to find all the problems that match that type).
- If you have not looked at/used the book much, it will be of little advantage
- Pick books you know. If you do not have favorite book(s) for each category above you now
have something else to work on
- Bookmark things. Put postit notes in various places in books oyu often use. This can save valuable time.
Do NOT forget about input. Having a dozen different pieces of code that load different types of input
to refer to may save a lot of time in the contest (if you can find it easy).
Cheat sheets can be useful. For instance if you plan to use vi(m) and know some of it pretty good but can
never remember a few commands that you know will be useful, consider printing a cheat sheet in advance (you
can even highlight what you expect to want to know).
The References web page has links to some good books
and it has some links to few neat cheat sheets!
Supplies: Bring pencils that you like. It is a bummer to have to borrow and not be compfortable with
them. Spend some time noticing what you use while solving these problems. If you look something up online,
find a reference(s) that provides that information. Practice finding it there so that you will be able to
during a contest. If you chew on a pen -- bring some pens that you plan to use to chew on. Make yourself
as comfortable as possible. If you squeeze a foam ball while thinking -- make sure you bring one.
Food: In theory you should not need any. The contest should provide what you need. The contest may not
allow you to take any food to your work area. On the other hand, a pack of poptarts may be a life saver if
you don't like lunch or just get hungry.
Toys: I never thought much about this before. For some teams a mascot really seems to make a
difference. Beyond that, comfortable things make it easier to relax. Dice, cards, ... can sometimes
help you visiualize a problem. Might help.
Allocation of the computer (time at the keyboard) is often a big issue.
When the contest is over, it is probably not a good thing if one person dominated
the keyboard. It usually correlates with others having written solutions that they did not have
time to type in. It also tends to create issues between folks.
I believe a good idea is to think about how a multiuser computer manages cpu.
This approach has some advantages:
- It creates a time slice (a maximum period of time a task can use the cpu without interruption).
- It then sorts the possible tasks into a priority list
- It takes the highest priority (top of list) task and gives it access to the cpu
- When the time slice expires, the current task moves to the bottom of the list, and the new
top task takes over
- If a task stops before its time slice is over (does I/O, needs something), it forfeits the
rest of its time slice
It also has some disadvantages:
- Within a period of time, every task gets a chance at cpu
- Time is not wasted waiting on I/O (when a task does I/O, it is requeued and the next tsk gets cpu)
- tasks have a minimum amount of cpu time uniterrupted if they can use it
So what does this have to do with a programming contest?
- Time slice may expire before task needs to do I/O
- If all tasks use full time slice, it may take a while before each task gets its next shot
- One task doing a lot of I/O amongst multiple cpu bound tasks might feel starved
Avoiding conflict during a contest is a good thing. If using a rigid, time slice mechanism allows folks with
different personalities to swap keyboard time, then personal conflict is avoided. The frustration that
might occur when some one has to leave before they wish is not direct4ed at the team mates.
- If you implement a time slice concept and
always swap who is at the keyboard when a time slice expires (or when the person reaches an
interrupt), you can (probably) more fairly allocate keyboard time amongst the team members
- You can avoid conflict when one person wants/needs the computer and another person does not want to give
it up (some people are not comfortable being aggressive -- this approach takes that out of the equation)
- It breaks the contest into a series of time slices that can be used to gauge progress
- It helps point out problems not worth further effort
At first glance the contes tis 5 hours of continuous effort. This fact has many subparts:
By picking a time slice, you automatically provide a new perspective. Say you chose 30 minutes as your
time slice. This would mean that 10 time slices would exist (basically each person gets 3 shots at the
computer). If you plan to solve 5 problems, each problem gets 2 time slices.
- Can you do 5 continuous hours of high effort thought
- Can you effectively divide the five hours amongst multiple different problems
- Can you estimate how long to work on each problem
Clearly, 30 minutes is a long time for a time slice. Plus the math is yucky (5 problems of 2 time slices with 3
people of 3 time slices). What if you choose 5 minutes for a time slice? You get sixty time slices. Each problem
gets 12 time slices. Each person gets 20 time slices. If you approach a problem modularly (get data read in,
confirm data loaded correctly, code solutioon part), then you can try to fit each module into 1 or more time slices.
Maybe 5 minutes is not enough. Anything over 10 minutes probably promotes someone not working for the full time.
Here is another side of time slicing. Suppose you use 5 minute time slices. Suppose you estimate that
a problem should need 5 time slices. Suppose after your 4th time slice, you have just now got the data read
in correctly. Should you continue investing timeslices on this problem or move to another? Maybe at this point
you believe that you need 3 more time slices to finish -- how does that impact other problems and their current
state? In other words, the time slices can be used as a tool to determine if your are on "schedule".
Maybe you should spend a little time early on thinking about this. As you rank each problem, do the following:
Maybe using time slices and viewing prblems as a sequence of slices, might prevent you from wasting time
on that not difficult problem that is going ot be really long or help you realize when a problem is a
lot harder than you thought.
This gets you started. That last step sounds easy but has lots of parts,
- Do you know an algorithm/data structure to solve it?
- Is the data going to be hard to read?
- Estiamte how many time slices to get data loaded.
- Estimate how many time slices to "solve" problem
- These combined estimates could make it easier to decide which ones to do in what order (or which ones
to not do at all)
- Establish a time quantum (15 minutes for example)
- After each 15 minute window, determine if anyone other than
the person currently at the keyboard could benefit from using
the computer. If yes, swap to next person (consider always
giving someone 2 slices to start with if possible).
- If a person has been debugging for the majority of a time
slice, one of two things should happen:
If you decide to relinquish the computer, a printout of the code
to be debugged should be made.
- They should relinquish the computer to someone else
- One of the other team members should help them debug
Is has been stated that you should briefly look at the problems and then work towards solutions
for eavery problem you intend to solve early on. What does this actually mean?
Problem evaluation can be short or it can be very indepth. Here are some goals to shoot for when evaluating
If you can determine reasonable answers for all of the above for each problem, you can begin to
decide which problems to attack and in what order. You could obviuously spend a LOT of time
trying to answer the above questions.
- Do you really understand the problem?
- What hidden complexities exist?
- What algorithm(s)/data structures(s) make sense?
- Is the solution apparent (i.e. is it trivial)?
- How bad will it be to load the data?
- How bad will output be?
- How long to solve it (time or time slices)?
- What gotchas exist?
- Can you step through all the sample input and figure out how they get each sample output?
- What questions seemed unanswered?
- What boundary/extreme cases exist for the input data?
If you make a first pass making rough answers/estimates to these questions about all the problems (say 1-3 minutes
per problem), you should be a lot closer to organizing the next 4.5 hours of your time.
Then you probably want to spend a little longer answering these questions with more detail on the
problems you have decided to attack.
Remember the scoreboard. If you see quick solutions for a problem that you thaoght was hard, it could
mean any of the following:
- You misread the problem and it is easy
- The judge data is much simpler that you anticipated
- An unnoticed trick makes it much easier
- That one or more teams happened to ahve solved one just like it recently (so rather than being
easy -- it is just famaliar), pay attention to who is solving a problem (if all the solutions are
coming from teams from 1 school, this may be the case)
Things to do at beginning of contest
At the very beginning of the contest there are a number of things you can do that
might improve your final results:
- At the computer
- Build a directory for each problem
- Type in a generic stub that can be used
- type in input data for each problem in its subdirectory
- Work on the input routines (and a dump to prove data read in properly), if these
are done, then when someone is ready to type the "solution"a lot of time is saved
- Away from the computer
- Split problem set and re-staple
- Read (lightly) each problem making a few notes about
it, keep a short list ranking the problems relative to
- Decide which ones you intend to solve
- Start working on "solutions" for each of these problems, remember to invest early time on
solutions for all intended problems