ACM Programming Competition Tips

This article is being spawned from my experience at the Northern Michigan College ACM style Programming Competition that I attended today. While the competition is fresh in my mind I wanted to cover some tips I learned from failing miserably this time in the competition.

First tip, and probably the most important thing to understand, ACM competitions are not so much about raw programming skills as they are about knowing certain API's and knowing how to solve certain categories of programming questions. The API's you need to understand are a language's File IO, String parsing (especially tokenizing), Collection classes (List, Dictionary, Vector), and Math libraries. The reason for this is that almost every problem that you will encounter in an ACM style competition is rooted in this problem format:

Step 1: Parse input line by line
Step 2: Perform computation on each entry parsed, or on a collection of entries parsed
Step 3: Output result in a specific format

This implies two very important things:
Tip two, KNOW how to write very versatile parsing code. The number one issue that I had today was that although I know C# file IO, and I would say that I am fairly proficient at it. I generally tend to use documentation heavily when I write code. In an ACM competition you rarely have documentation. Everything is basically from memory. If you are lucky and do get documentation, the reliance of  API documentation for something like parsing, which will need to be done at some level for each problem, becomes a hinder and a time sap. If you practice writing versatile parsing, code that can handle tokenizing both strings and integers (C# Split function works really well for this and you can easily write a re-usable block of tokenizing code in about 4-6 lines using it), the ability to simply write this from memory when you walk into the competition is crucial for a good time on the first couple of easy questions.

Tip Three: Have a working knowledge of Math libraries. I can not stress this enough, there is inevitably some problem that requires you to use at a minimum the Pow function (pretty much a standard in any languages Math API). I recommend knowing the parameter order from memory. There really isn't a whole lot more to say on this other than to have a somewhat working knowledge of math, which if you are a computer scientist, you should have.

The rest of the tips that I have are domain specific tips. These are good to have a fundamental understanding of how to use effectively.
Tip four: Understand sorting algorithms. The better you are at understanding sorting algorithms (or at least their use as part of a language's API) the better off you will be. Generally optimization isn't the primary concern at a competition, output correctness is. However when a grader is testing your problem, they will generally have that one input test that will destroy O(n^2) operations. It is best if you can work your sorting algorithms to be O(n log n) on general practice. Search algorithms are also another similar domain, these should be on average O(log n) if you can. Keep in mind that most languages already have optimized searching and sorting algorithms as long as you are using the provided data structure types (I.E. System.Collections.Generic package in C# or your standard java.util.AbstractCollection package in java). Use these to your advantage whenever possible.

This leads me to my final domain specific tip:
Tip five: Understand recursion and how to define a recursive problem. This is the one topic that spurred me today. I do not use recursion at work (in fact I am required not to by my works coding standards). This has lead me to be a bit rusty on looking at problems in a non-iterative manner. A problem that I had fundamentally correct in an iterative solution was too slow (see tip four), and as a result was returned incorrect. Less than 15 minutes before the competition was over, I saw the recursive solution but it was too late to implement it for points. Had I brushed up on my recursive algorithm design practices prior to the competition I may have been able to do better on this problem.

Overall, the best method of doing well in an ACM competition is to practice, practice, practice. Try implementing simple programs that manipulate some sort of text input, and output it in another format after some sort of computation. This is also useful for any career where you work with managers that do not know how to program, because if they give you menial documentation work, or data parsing work to be done by hand (first hand experience talking here, it happens), you are more prepared to take what could be a 20-40 hour task and turn it into about 3-8 hours of fun programming.

As far as practice, there are resources online, where you can get old ACM competition questions to practice with. You can see some of the world finals problems here. There are other sites out there that have varying degree of difficulty programming problems that are like little brain teasers and can also help build the skills needed to do well in a programming competition. Like I said, you can study for this test like you would any standardized test, it is not about skill as a programmer, but skill as an ACM problem solver.

Good luck to anyone who goes to take part in an ACM competition, they are a lot of fun and they let you let your geek hang out. I did the one this weekend as an independent team since I am no longer in college, I did it for fun, and fun was had. If you can not find an ACM competition that you can participate in, start your own competition, let me know if you do.