Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Spring 2016 -- CSC 2700 Section 01 (Tureaud Hall 112, 6:30 PM - 8:20 PM)

How to Approach a Programing 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:


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: 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).

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.


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.

This approach has some advantages: It also has some disadvantages: So what does this have to do with a programming contest? 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 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.

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, such as:

Problem Evaluation

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

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.

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:


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: