Introduction to Competitive Programming

Introduction to Competitive Programming 

Have you heard your friends talk about LeetCode or Codeforces contests? Maybe you’re wondering what competitive programming is all about. Here’s what you need to know.

What is Competitive Programming?

Competitive Programming (CP, or sometimes known as Informatics) is an activity where we try to solve clearly defined computational problems using code. The 'competitive' part of CP comes from the numerous contests where people aim to correctly solve as many problems as possible in a fixed timeframe, typically around two to five hours. Solutions must also follow time and memory constraints which means your code needs to be both correct and efficient.

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

  1. Problem solving.

  2. Algorithms and data structures, which we apply to solve problems efficiently.

  3. Implementation, the process of writing and testing code.

Many people participate in competitive programming for the challenge and fun of it, but it is also great practice for technical interviews in software jobs, university courses, and general problem solving in the real world.

Competitive Programming at UNSW

CPMSoc’s programming team runs regular workshops and occasional contests, 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 Divisionals, Regionals, and World Finals.

Sample Problem

If you’ve already encountered a competitive 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 large standard library.
  • 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 slowly pick up any extra functionality from C++.

Training and contests

The best way to get started is to start solving some problems. There are many free online training judges that host problems for you to solve and contests to participate in. The most well known one is Codeforces, and we recommend these steps to start off with:
  • 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.
  • Solve more problems, of increasing difficulty. You can search problems by difficulty rating in the Problem Set.
  • 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.

We hope to see you at a CPMSoc workshop or event in the near future!

Links to our socials

Popular posts from this blog

Tips for Competitive Programming

Implementation tips for competitive programming

The Art of Making Programming Problems

Interactive Tasks

Sqrt linked lists

Introduction to Dynamic Programming

Fracturing Search

Union-find Disjoint set