Competitive Programming

What is it?

For me, competitive programming is the art of creating a program to solve a given mathematical, logical, or algorithmic problem, such as needing to generate all primes between two numbers, determining how to keep a robot on a grid, or finding the longest increasing subsequence.

Competitive programming is primarily focused around contests where individuals, or teams, compete to be the fastest to solve many different problems. The programming languages allowed vary, with some contests allowing you to use any language while others only allow C/C++ and Java.

My Experience

I have been practicing and competing since 2011. Recently, I placed 583 out of 3000 international programmers in Round 2 of the 2015 Google Code Jam, placed second with my team of three in the 2015 Alberta Collegiate Programming Contest, and won the Microsoft contest at the University of Alberta with my team in 2014.

For practice, I have completed 357 problems as of this post on UVa Online Judge and competed in many other contests throughout the years.

Why Practice

For me, I mainly practice competitive programming because I enjoy it, but it has also really helped with programming interviews.

I enjoy the two moments of accomplishment that I experience while solving a difficult problem. The first is the moment when I think of a solution. The second thrilling moment is after I have submitted my solution and “Accepted” appears. This is even better during a contest where I can see how much my ranking increased, or that I was the first in the contest to solve the problem.

Benefits for Interviews

For programming interviews where you will be coding, which companies like Google or Microsoft have, it is helpful to be strong in data structures and algorithms. After all, interviewers love to ask “Can you make it more efficient?”, which essentially boils down to determining a better data structure/algorithm.

By practicing competitive programming, you will naturally become familiar with many of the data structures (like a hash table, or a trie) and algorithms (like Dynamic Programming (DP) or Binary Search) that are helpful for programming interviews.

Additionally, participating in a contest is similar to a programming interview, because you need to solve one or more problems with limited time. Best of all, the most difficult interview coding problems I have come across so far as an undergraduate (even from Microsoft/Google) would be considered medium difficulty in a regular contest.

Suggestions

Books

I would recommend two different books, depending on your interests:

Competitive Programming 3
  • Excellent introduction to important concepts for competitive programming, like:
    • What complexity is acceptable for certain sized inputs
    • General solving strategies
  • Walks you through more and more difficult concepts with code examples
  • Gives example problems to practice on from UVa Online Judge
Introduction to Algorithms
  • Provides a very strong understanding of algorithms and data structures
  • Has good pseudocode
  • Has a heavy focus on proofs
  • However, lacks suggestions for getting started in competitive programming

 

There are many other possible books for competitive programming such as Programming Challenges: The Programming Contest Training Manual (which I have heard good things about, but not worked through). If you have any other suggestions for books please comment below!

Practice Websites

Introduction

For an introduction to competitive programming and online judges, I would recommend using HackerRank’s tutorial since it has complete code examples for many languages.

General

Once you are familiar with online judges, I would recommend two different websites depending on what you are interested in:

For those not interested in competing in major contests, like the ACM ICPC or the Google Code Jam, then I would recommend using Topcoder purely because you do not need to deal with input/output, which makes the problems simpler.

Otherwise, I would recommend to continue to use HackerRank since the problems are organized by category. The most relevant problem domains for HackerRank would be the Algorithms and Data Structures domains, with the specific programming language domains and Mathematics domains also being helpful.

Please note that when practicing myself, I have mainly used UVa Online Judge, so my experience with most other websites is rather lacking, so if you have any other suggestions please comment your favourite website and why!

Major Contests

Association for Computing Machinery (ACM) International Collegiate Programming Contest (ICPC)

The ICPC is held every year and the contest is open to university students. Due to the entrance restrictions, the contest participants are primarily undergraduate students, but masters students may be able to compete. In the contest, teams of 3 have five hours to work together to solve 10 or more problems which range in difficulty. However, each team has to share one computer, so an important part of the contest is having some members planning out their solutions to problems while always having someone coding a solution.

For this contest, there are Regional Contests that occur around October-December, then the World Finals usually occur in May-July. To participate in the World Finals, you will need to qualify in the regional contest for your area.

Google Code Jam

This contest is hosted by Google each year and culminates in an onsite final at one of Google’s offices around August. Anyone can compete, and the contest starts around March. Unlike many other contests, some problems are weighted more than others. What also makes this contest different is how there is a small input for which you get immediate feedback, and a large input where the results are released once the contest ends. It is often possible to brute force, or even sometimes hand-solve, the small input while the large inputs will usually require more finesse.

In this contest, there is a qualification round, where anyone scoring above a certain level will advance, as well as three online rounds where a limited number will advance.

Here is a list of the previous contests and rounds for the Code Jam. A great aspect of the Code Jam is that they will analyse each problem within a few weeks after the contest ends, so you can learn how to solve each problem.

A similar contest is the Google APAC, which is meant for BS, MS and PhD students who will be graduating and are interested in working at Google.

Facebook Hacker Cup

A yearly contest, starting in January, which anyone can compete in. Like the Code Jam, there are multiple rounds with the final round being an onsite final on Facebook’s campus around March. However, unlike the Code Jam, its problems do not have the separation into small and large inputs, with there instead being instant feedback on all of the problems.

Other contests

There are many other smaller contests as well, especially for university students, where the competitive programming club at your school may host a school wide contest or have a joint contest with other universities in the area. As well, it is very possible that some of the larger companies, like Microsoft, also runs a contest at your school.

There are also many websites that have regular contests: Topcoder has their SRMs, Codechef has many contests, Codeforces has regular contests among many others. The easiest of these to get started in would probably be those for Codechef, and there are also editorials that discuss the solutions.

During the winter break I will be trying out many other websites and will make another post with a better breakdown of suggestions for the many websites that there are, as well as some additional suggestions about how to get started in competitive programming. For some other people’s suggestions, you can look at this Quora answer, this post on HackerEarther, or this post.

One thought on “Competitive Programming

  1. Men , just want to thank you , I have been struggling with uva 11790 a quite time, but then i read your code it was the most beautiful code I have ever read, no need to commentate , self explained, just want to say thanks

Leave a Reply

Your email address will not be published. Required fields are marked *

[TOP]