CP101

Welcome to CP101, an introduction to what competitive programming is about, and how you can get started with it.

What is Competitive Programming?

Competitive Programming (CP, also known as Informatics) is an activity where participants try to solve well-defined computational problems using code.

These problems can be thought to train and test you in three related areas:

  1. Problem solving.
  2. Algorithms and data structures, which we apply to solve problems.
  3. Implementation, the process of writing and testing code.

At the heart of CP, naturally, are contests. These require you to write correct and fast programs to a number of problems in a fixed timeframe, varying from around two to five hours. Many people participate in competitive programming mostly for the challenge and for the fun of it, but it is also great practice for technical interviews for software jobs, university courses, and general problem solving in the real world.

Competitive Mathematics Workspace

Image credit: ireneperezstudio

Competitive Programming at UNSW

CPMSoc runs workshops and contests throughout the year, suitable for all experience levels. We are always happy to give advice and help out.

We also recommend taking COMP4128 (Programming Challenges) when you are able to, as having the lecturer and tutors there to help you quickly is very useful.

The most notable university competition is the International Collegiate Programming Contest (ICPC). The contests are five hours long with roughly twelve problems, and you compete in teams of three. Generally there are three stages: the Preliminary, Regionals, and World Finals.

Sample problem

If you’ve already encountered a programming problem, feel free to skip this section.

To get a sense of the kind of problems you might encounter, consider this example:

You have bought N identical flowers to arrange into three vases. As an expert in interior design, there are three important rules you must follow:

  1. Every flower must go into one of the vases, since throwing flowers away is wasteful.
  2. Each vase must contain at least one flower, since an empty vase looks very odd.
  3. Each vase must contain a different number of flowers, so all the vases look different.

Given a value of N, print a possible way to arrange the flowers, or say that there is no way.

For this problem, we have to write a program that reads an integer N as input, and outputs the number of flowers you want in each vase.

Go here for the full specifications (including some examples) and a place to submit your code, and see this for help reading the statement and solving the problem.

Getting started

Pick your programming language

A requirement for CP is knowing how to write and run code. If you are just starting out or even completely new, that’s okay – many problems are accessible with only a very basic understanding of programming, and you can learn as you go.

The languages available in the ICPC are C++, Python and Java, but different platforms support different languages. There are many online tutorials for learning a language.

C++ is the most commonly used language in CP, for its speed and its standard template library. Python is easy to learn and use, but is slow, and so may not be able to solve certain problems.

  1. C++ is the most commonly used language in CP, for its speed and its standard template library.
  2. Python is easy to learn and use, but is slow, and so may not be able to solve certain problems.

Most C code will compile as C++, so if you have only learnt C from UNSW, you can start with that and pick up any extra functionality from C++ as required.

Training and contests

The best way to get started is to start solving some problems. There are many free online training judges and contests available. The most well known one is Codeforces, and we recommend these steps to start off with:

  1. Solve a really simple problem, like Wrong Subtraction, (or Vases from earlier, although this isn’t on Codeforces) to get used to reading input and writing output.
  2. Solve more problems, of increasing difficulty. You can search problems by difficulty rating in the Solve a really simple problem, like Problem Set.
  3. Try some contests. The Educational, Division 3 and Division 4 contests are targeted towards beginners.

At the bottom right of many problems is a “Tutorial” button, which brings you to a page with an explanation and solution (usually in C++) for the problem.

Learning algorithms and techniques

There is a huge range of online resources to help you learn about algorithms, data structures and common approaches.

We recommend following a course such as the USACO Guide, or a book such as the Competitive Programmer’s Handbook.