What is competitive programming? Link to heading

Do you know about Advent of Code? Do you understand what the following piece of code does?

import sys

values = [int(x) for x in sys.stdin.readlines()]
windowed = [sum(values[idx-1:idx+1]) for idx in range(1, len(values) - 1)]
print(max(windowed))

then you might be able to do some competitive programming yourself.

The idea is that a bunch of people are shown the same problem and they all race to solve that problem with code. There is often some form of automated online judge that has a number of tests that it runs against the solution and thus judges if the solution adequately solves the problem or not.

Generally a problem is stated like this:

Blurb Link to heading

You are trying to solve the problem. It is an important problem for John Doe. He is having trouble with it. There are graphs.

Input Link to heading

You will receive a number, N, 1 < N < 100. Then follow N lines, each representing the connections from one node in a graph to another as a list of integers.

Then you will receive a number, Q, 1 < Q < 10000. Then follow Q lines, each with a pair of nodes.

Output Link to heading

For each Q pair of node, print the shortest path between the nodes.

Example Input Link to heading

The example contains the graph 1 <-> 2 and the queries 1 -> 2? and 2 -> 1?.

Example Output Link to heading

1 -> 2
2 -> 1

Back to the blog post Link to heading

And that is an example of how competitive programming works. Generally there is some element of computer science in there, some elements of datastructures and algorithms, some plain good ol’ coding skills . Often lots of input/output handling as well.

If you want to try competitive programming there are lots of online platforms that you can try it out on. I recommend Kattis.

If you are a student I can also recommend attending a competitive programming competition like NCPC or NWERC. Competitions online are often open to anyone and solutions tend to be posted on the sites a day or two after the competition.

Advent of Code is another example of “competitive programming”. It’s about solving a fictional problems that are easier to solve for a computer than for a human. Input is given as a file and interpreting that file and solving the problem posed by the input is just what you do in competitive programming.

The benefits Link to heading

During my university studies I spent quite a lot of time doing competitive programming. For 4 years I went to NCPC and NWERC in order to compete. These are some of the lessons I have learned along the way:

Thinking like the computer Link to heading

When using an online judge you will not know what edge cases they have in store for you. You have to code extremely defensively. Generally you will be told one of the following errors

Your codes too slow
Your code crashed
Your code produced the wrong output
Your code consumed too much memory

This gives you no hints as to what the actual problem is. The tricks I used to combat this was

KISS (Keep It Stupid Simple)

Generally the solutions are around 50-100 lines of code of C++. If you find yourself reaching into 200+ lines of code you are probably doing it wrong. In my professional career this also holds to some degree. Most problems that can be clearly defined don’t need large implementations.

Keep a model in your brain for the problem and the solution

You need a good theoretical understanding of computer science to be good at competitive programming. If we spend our brain power thinking about bits and bytes, compiler flags, “how do you do string parsing in C++ again?”, then we will not be able to focus on the problem we are solving.

Solve the problem on paper first, before solving it in your editor. Your editor won’t help you in finding the solution to a problem, it will only help you express it in code.

Time Management under Stress Link to heading

A competition generally has 4-5 hours of full on programming. It is mentally exhausting work to solve hard problems for that long. You have to be smart. It is not a 100-m sprint, but neither is it a marathon. It is more like a 5K run. In a competition it is much much better to solve four problems fully than three and two halves. Similarily in professional life, you might have to prioritize what is most important to solve with the limited time you have.

Only with good planning and a bit of luck can we solve “all” problems. If we already failed to plan well, then we need to manage the time left to solve the most prioritized things first. In competitive programming this means dropping tasks that you are unlikely to solve in favor of problems you are likely to solve.

Job opportunities Link to heading

No seriously, jobs! If you have a good track record of competitive programming, then that is great proof that you know how to solve problems with a computer. Not necesserily that you will be “the best candidate” in a job interview, but entering competitions like this shows that you know your way around a computer. There is a reason these events are sponsored and a lot of companies attend and give talks at the physical events.

The cons Link to heading

It’s not all great and glamor doing competitive programming tough. Some of the things that I do not like about it are listed here:

It’s mostly computer science Link to heading

Most competitive programming problems I have encountered (especially all in student competitions) revolve around theoretical computer science. Graph theory, string searching, sorting etc. Quite a lot of problems, but not that much focus on domains like AI, multithreading/GPU programming, IT security/Pen-testing. Sure, there are other competitions revolving around those areas, but competitive programming is not an arena in which you will be faced and train on a bredth of problems.

To be great you need encyclopedic knowledge Link to heading

What put me off striving for the really high-level of competitive programming was the high degree of encyclopedic knowledge you needed. I felt that often a lot of the problems were formed around a specific algorithm or data structure. To me, it’s not a challenge to learn as many things as possible. That is not something that speaks to me.

Don’t get me wrong, learning competitive programming to a good level has been awesome. But I am not interested in becoming great at it.

It is not software engineering Link to heading

Most solutions are 50-300 lines of code. They are generally looked at once, then thrown away as quick as possible. Your task when doing competitive programming is not to write readable code. Keeping the implementation time to a minimum is much more important.

You do not use any frameworks except what you can find in the standard library. Since C++ is such a common language you will probably use C++ the most. Possibly python or Java.

There are lots of these things that make competitive programming very different from software engineering, where things like readability, logging, and architectural concerns are a thing.

Summary Link to heading

All in all, I am happy that I participated in competitions but I am also glad that I did not take it further than that.