|
Introduction
This article is aimed at programmers who are thinking of using C++ as a programming language for TopCoder algorithm matches — either because they are new to TopCoder, or because they want to switch languages. You should already be familiar with the basics of C++. I'll look at how C++ is used in the arena and consider some pros and cons of using C++ as a competition language.
If you haven't used the arena before, start with the official How to compete guide. You may also want to take a look at some sample problems to get a feel for the style of the challenges. If you sign up and enter the arena, all the previous challenges are available for practice. The default editor is a bit lacking, so you should also check out the available plugins; these include several alternative editors (KawigiEdit is quite popular), a plugin to let you use your normal desktop editor (FileEdit), as well as other plugins to help automate testing.
Why C++?
Every language offers a slightly different set of tools, and a good knowledge of the available tools can reduce coding time and lead to more reliable code. C++ is the most popular language in the arena; let's take a look at what it has to offer.
The Standard Template Library
The Standard Template Library (STL) is by far the most important set of tools that a C++ programmer has. While expert competitors will know the details of most of the classes, there are two that you need to be familiar with because they may be used to hold the input or output data: vector and string. Fortunately, they are also the simplest to use. They both have a size() method that returns the number of elements (or characters), and they can be indexed like a normal array. You'll need to know a bit more than that to use them for output, but you can read up on them at the link above. To see what other TopCoder members have had to say about the STL, check out this crash course or this more in-depth coverage.
A big advantage of the STL over the Java Collections Framework is that it uses operator overloading to provide natural syntax for operations. For example, two strings can be lexicographically compared using the normal comparison operators.
Macros
Macros are one of the dirtier parts of C++, but they also let you do things that are impossible in other languages. The most common use in the arena is in code templates that define short macros for long-winded pieces of syntax. A common example is:
#define FOR(i, n) for (int i = 0; i < n; i++)after which one may write FOR(i, n) instead of the full loop specification.
There are a few things to keep in mind when you do this:
- In the real world, this is considered very poor style. Don't do it outside of programming challenges.
- Have a look at other programmers' submissions to get some ideas (Eryx's template shows off the possibilities as well as several GCC extensions), but any code you submit in the arena has to have been written by you (no copy-and-paste).
- The challenge rules limit the amount of unused code that you submit, so you need to keep your template to a minimum.
C++ is generally regarded as the fastest of the TopCoder-provided languages (for the compilers used in the arena). This is seldom a major issue, since the administrators usually do a good job of making sure that speed differences don't make it easier for C++, but from time to time it is possible to get away with a less algorithmicly efficient solution. This occurred in SRM 334: top-ranked coder Petr had to re-submit a problem because his C# solution was too slow, while my C++ solution using the same algorithm was fast enough.
Popularity
Roughly three quarters of TopCoder competitors use C++ in the arena. While that doesn't necessarily mean that you should submit in C++, a decent knowledge of C++ (including the subtle tricks and shortcuts) will help you in the challenge phase.
Why not C++?
Debugging difficulty
While modern languages like Java and C# have well-defined behaviour in most error situations (such as overrunning the end of an array, or using memory that hasn't been initialised), C++ programs tend to crash, or, worse, produce unexpected and variable results. A good debugger or IDE can be immensely helpful in tracking down such errors and I believe that all C++ competitors should at least know how to use a debugger to determine where a program crashed. Nevertheless, tracking down memory-related bugs can be a difficult and time-consuming process that isn't necessary with safer languages.
A related problem is that the heavy use of templates in the STL means that compiler errors can be almost incomprehensible. It gets easier with practice, but nevertheless this can slow you down.
Missing library functionality
There are a few things that can be done in other languages but not in C++. Two notable examples are arbitrarily large integers (BigInteger in Java) and computational geometry operations (line intersections, etc.). This is less of a problem in TopCoder than in other challenges, since nothing prevents you from maintaining pre-written libraries and just pasting them into your code when the need arises (subject to the rules that you have to have written the library yourself, of course, and the limit on the amount of unused code).
Conclusions
Ultimately, the particular language you choose will be less important than how familiar you are with it. If you switch languages, you should not expect to do better unless you get to know the new language as well as you know the old one.
For someone who knows all its secrets, C++ submissions will be both faster to write and faster to execute, but generally slower to debug. There is a lot more that can be said about C++ in competitions than I have space for here, so I'd like to invite the experts to share their wisdom in the forums: What's your advice on writing reliable code and testing? What's your favorite C++ tutorial? What practice problems would you recommend for a C++ beginner?
