Introduction to Competitive Programming

2016 ACM-ICPC World Finals in Phuket, Thailand

When people hear the phrase “competitive programming”, some of them conjure up images of hackers pulling all-nighters trying to build the best app or website over a weekend. However, that kind of programming contest is called a hackathon.

Competitive programming is an intellectual sport where coders race each other to solve the most algorithmic problems within a limited amount of time. Many of the CS topics used while developing apps, such as networking, GUI, and databases, won’t be showing up during these contests — they’re all about your algorithmic problem solving ability, data structure knowledge, and implementation skills. Scoreboards update in real-time, and participants feel the exhilarating rush when they solve a difficult problem and jump ahead of their competitors. At higher levels of competition, the best of each region or school all gather in one location to vie for the chance of bringing home a medal, trophy, or even cash.

Why should I do competitive programming?

Training for and participating in programming competitions have several benefits:

  1. You will become a better, more efficient, and less error-prone coder.
  2. Your technical programming interviews will be a piece of cake. Getting one will be easier as well — Gayle Laakmann McDowell, author of Cracking the Coding Interview, mentioned in a Quora post that “competitive programming [on a resume] usually merits an automatic “yes” for an interview”.
  3. You will increase your problem solving abilities that will help you solve, design, and implement difficult real-world programming problems and algorithms in the future.
  4. Win prizes and trips to places around the world as you compete with and meet other motivated and smart students.
  5. It’s really fun! At least, I hope it will be for you.

How can I get started?

The prerequisite for jumping into competitive programming is a good working knowledge of your favorite programming language, and some basic data structures. C++ is by far the most popular language of choice for competitive programmers due to its speed, and most resources/solutions will probably be written in C++. If you’re a student at UCLA, a class like CS 32 would be sufficient.

A good first step would be to tackle the USACO Training Pages. The first few sections cover some basic but very important algorithms, such as Greedy, DFS/BFS, binary search, dynamic programming, and more. The training pages have tutorials that you can read on these topics, plus a host of practice problems to hone your skills. This provides you with a structured and organized way of learning the basic algorithms you need in competitive programming.

However, one shortcoming of the USACO training pages is that to progress to the next section, you must first successfully solve all problems in the previous section. Sometimes, this can lead to frustration if one difficult problem is blocking your progress, since it does not allow you to view the solutions to a problem until you solve it. You can, however, try searching online or asking for help by emailing them.

Read about algorithms

Besides the USACO training pages, there’s a lot of other material out there that can be useful for learning algorithms.

If you like going through textbooks, the CLRS Introduction to Algorithms textbook is a good choice. There’s probably a lot of details in textbooks that might not necessarily be useful for competitive programming, however.

For others, who think textbooks are too dry and/or long, you can take a look at slides and practice problems for Stanford’s CS97SI: Introduction to Programming Competitions course.

Another good resource for learning algorithms is the TJHSST Lecture Archive. Here, you can browse through years of their lectures and high quality handouts to learn about whatever topic you want to focus on.

In addition, TopCoder has a collection of Data Science Tutorials (but really they mean algorithms) on various algorithmic topics.

Practice makes perfect

Just reading about algorithms alone will not make you a better coder. You must take the time to implement those algorithms by solving practice problems.

Codeforces has a great interface and huge collection of problems from their past competitions. There are also editorials (solutions) to almost all of their problems in case you get stuck, and you can even look at other people’s source code to see how they did it efficiently. One way of practicing would be to participate virtually in past contests, then go over a few of the problems you couldn’t get in the end.

TopCoder also has a large collection of problems, but in my experience the interface is buggy and not as polished as Codeforces.

USACO Training Pages and USACO Past Contests has a bunch of problems as well, as mentioned earlier.

If you would like to work on longer, more complex, ACM-ICPC style problems (i.e. if you’re training for ICPC Regionals or World Finals), you can use online judges such as SPOJ, Kattis, and a few others. It’s pretty rare to see editorials or solutions on these websites, however. You might have to resort to Googling the problem.

Compete

There’s no substitution to real competition and the time crunch and pressure that comes with it.

ACM-ICPC is the premier programming competition for college students. Students compete in teams of three to solve ten difficult problems in five hours. Regional contests are held once a year in the fall, and winners of those are invited to the World Finals in May to compete against other top universities from around the world. UCLA’s teams have seen some stellar performances, with two World Finals qualifications in the last few years. Tryouts for UCLA’s teams will be conducted during Fall Quarter.

Codeforces offers two-hour online contests once or twice every week. They are a pretty good choice if you would like to compete regularly. They even have a ranking/ELO system, with your personal ranking increasing as you improve and do better at their competitions. As mentioned earlier, their interface is very nice and you’ll get access to editorials, solutions, and other contestants’ code after each contest as well.

Topcoder, HackerRank, and CodeChef all have periodic online contests as well.

Companies often sponsor programming competitions once or twice a year. Two of the largest ones include Google Code Jam and Facebook Hacker Cup.

No matter where you compete though, it’s very important to upsolve — take the next 1 or 2 problems that you couldn’t get during the competition, and figure out how to do them afterwards. You can consult the editorial and other solutions, but make sure to write your own code and get your solutions accepted.

Have Fun

Programming competitions are meant to be fun. If you’re not having fun, take a break and try coming back after some time away from your computer. It’s hard to improve on something if you’re not enjoying it.

I hope you found this blog post useful. UCLA’s ACM-ICPC club hosts training sessions every Wednesday from 6–8 PM in Boelter 2763, so come out if you’re interested in learning algorithmic techniques. You can follow our important announcements on our Facebook page. Thanks for reading.