Competitive Programming

blank

blank Last year, a short e-mail forwarded by a school teacher placed me into an interesting situation. An invitation to sign up for the national computer programming competition. I never really considered entering it, until one of my friends asked me to.

Two weeks later, we had won our division, come third overall, and won a nice amount of money from it (it wasn't a bad return for two hours work).

I've never looked back.

So what does Competitive Programming entail? Either individually, or in a team, you are given several questions – generally filled with really bad nerd humour (worse than mine :)) – and somewhere within the question, you have to find the problem to solve. These can range from cryptography, to graphing algorithms and the like. You get a fairly short amount of time (normally about two hours), and you go about solving as many of the questions as possible, by writing computer programs.

Doing well at a programming competition requires you to be highly fluent in at least one programming language, and your fortunes can generally be swayed by how many different types of language you know. Different problems suit different language. For example, in any given competition, I like to have FreeBASIC (unfortunate, I know), C++ and Python available at my disposal C++ is well suited to questions involving graphs and data structures (thanks to the Standard Template Library, a collection of basic structures that are pre-programmed for you. This saves a lot of time constructing structures yourself), Python is well suited to solving mathematically-oriented questions, in that it has built-in base conversion and arbitary-length number functions built in (hence you don't need to write your own multiplying routines), BASIC is good for string and language-based programs. Almost all programs that can be thrown at you fall into one of those categories, and if you have at your disposal languages that can help with all of these problems you are well set to go. C++ and Python can both be readily replaced with Java, but you will need to be able to code faster, since Java has a significantly more verbose syntax.

After choosing your language, you should also prepare some templates that take care of all of the non-important features of a language

Such as in C++:

using namespace std;
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <strings.h>
#include <math.h>

int main()
{
}

The above code generally takes care of all of the basic functionality that you need to begin coding as soon as you get a question. You may also want to write routines designed to parse input before you do a competition – for example, input for most questions is space-delimited, which is great if you are a C++ coder, but BASIC doesn't have a space-delimited input routine, so it often helps to write that before the time begins – it saves a lot of time during the competitions.

Knowing how to interpret a problem is a skill gained only by subjecting yourself to the humour of university lecturers for a few weeks – in other words, the best way to prepare for a new competition is to go back over previous years' questions, and have a go at solving them. It's really quite a skill. Before ever attempting a competition, you should have at least some idea of how to understand the competition's setting out of problems.

The last thing you need to do is know how your compiler works. You should have some idea of how you will go about compiling your code, and providing it with input.

So – what are the rewards if you get to be good at it? Good prizes, and recognition. At the University/College level, many competitions have some form of corporate sponsorship, so the competition can often be some sort of recruiting ground for big IT-related companies (such as Sun Microsystems running Java comps), and at the school level, the prizes are normally quite substantial (the biggest competition in Australia has a prize of AU$3000, I couldn't compete for it due to an unlucky series of circumstances), and many of them have International competitions that competitors are selected from: The International Olympiad in Informatics (IOI) is by far the biggest (but is competed only between individuals), but there are also competitions run by other organisations – last year, I represented Australia in the SEARCC International Schools' Software Competition, which was held in Chennai, India. Aside from being fully sponsored, it was one of the greatest times of my life.

Big programming competition meets can be a good way to make friends from all over the place. I made lasting friends from many countries in Chennai, and this made the time spent there much more memorable.

I'll be representing Australia at the SEARCC competition this year, this time in Sydney – with any luck, I'll be keeping a blog of the events that happen there.

blank

Written by Jason Striegel

C/C++, Java, Python, Linux developer for 18 years, A-Tech enthusiast love to share some useful tech hacks.