How to Approach a Programing Contest

• Team Practice
• What to bring
• Time/Computer Allocation
• Problem Evaluation
• Things to do at beginning of contest

---

Team Practice

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 evaluating 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 develop 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 strengths and weaknesses), discuss 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
  • 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
• Supplies
  • Clock that all can see to help with time management
  • pencils - several, mechanical with spare lead, or old fashioned with a sharpener
  • erasers
  • graph paper - sometimes it helps a lot
  • some lined paper
  • ruler (straight edge)
  • compass or way to draw circles
  • stapler with staples
  • notebooks/folders to organize problems (may want 3 hole punch)
  • Scissors
  • Calculator -- if allowed (usually not)
  • zip lock bag with your name on it to put phone and other things into that you cannot have during contest
• Food
  • some candy (not much -- to avoid massive sugar highs/lows/illness)
  • nuts
  • bars (like granola or whatever you like)
  • water bottle (in case they do not have any)
  • Gum
• Toys
  • mascot or school pennant (something to get excited)
  • 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)

Reference: Things to think about:

• 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 you often use. This can save valuable time.

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/solution (or make a table of contents with a list of types and then a way to find all the problems that match that type).

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 comfortable 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 visualize a problem. Might help.

---

Time/Computer Allocation

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.

• 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

This approach has some advantages:

• 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 task gets cpu)
• tasks have a minimum amount of cpu time uninterrupted if they can use it

It also has some disadvantages:

• 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

So what does this have to do with a programming contest?

• 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

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.

At first glance the contest is 5 hours of continuous effort. This fact has many subparts:

• 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

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.

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

• Do you know an algorithm/data structure to solve it?
• Is the data going to be hard to read?
• Estimate 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)

Maybe using time slices and viewing problems as a sequence of slices, might prevent you from wasting time on that not difficult problem that is going to 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, such as:

• 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:
  1. They should relinquish the computer to someone else
  2. One of the other team members should help them debug
  If you decide to relinquish the computer, a printout of the code to be debugged should be made.

---

Problem Evaluation

Is has been stated that you should briefly look at the problems and then work towards solutions for every 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 problems:

• 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 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 obviously spend a LOT of time trying to answer the above questions.

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 thought 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 have solved one just like it recently (so rather than being easy -- it is just familiar), 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 each other
  • 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