Competitive Programming

This article tells you about competitive coding, and how to get started. More importantly, it lists all the competitions you should be looking at. You don't have to be in Computer Science to be a good competitive programmer. Hardwork, is what is needed.

Introduction

You are given a problem and write code to solve it. The judge runs your program on several inputs and tests for correctness. Every program has constraints. You get a verdict based on how your code performs on the test cases. Here are some:

AC (Accepted) - Rejoice! Your code passes all testcases given by the judge and is deemed correct.
Time limit ( about a few seconds ) - You get a verdict of "Time Limt Exceeded" if your program doesn't terminate in time.
Memory limit- gives a bound on maximum memory your program can use, includes both stack and heap memory.
Runtime errors- These occur when your code is prone to faulty pointers and stuff. Keep an eye if your code breaks for large inputs.
Wrong Answer- This means that your code produces incorrect output. This may be incorrect output formats, trailing spaces, incorrect "solutions", or anything which can give a non-empty diff to the correct answer.
Constraints on input - most important, this gives you an idea about how fast your algorithm should be. It is like a sport and many do it for just fun. If you are into programming, you can give it a try!

Pre-Requisites

A basic programming knowledge, in any language of your choice ( preferably C++, Java or Python ) is assumed. Otherwise, take a look at Programming 101. Also, if you want to try your hands on competitions like ACM ICPC, you need to be proficient in some techniques discussed below. Practice is key. A LOT of practice and consistency is required to perform well in a competition like ICPC.

Getting Started

The best starting point is to solve some problems on SPOJ. You can sort the problems based on number of users and start with the problems with the most number of users solved.
The next step is to read up on algorithms. It's strongly suggested that while solving a problem on SPOJ and you don't get idea, google it and find the algorithm for it, code it your self and get accepted. As you go along, you come across different algorithm techniques such as greedy, dynamic programming etc. Topcoder Tutorials are a great source for getting started with algorithms for competitive programming. These are well written and accessible to everyone.
As you solve more and more problems, look at other online judges(mentioned below). Also, start exploring harder concepts. Once you learn a new idea, you can use this Classifier to find problems from SPOJ on a given topic.

Excellent Resources

Online Judges:

Codeforces is the best website for competitive programming. It has a huge problem collection, with solution descriptions for every problem. You can also see the codes of other users for every problem. There are weekly live contests, in which thousands of users compete. They also have blogs and the community is very active: If you have any queries, they are ready to help you.
Topcoder also hosts weekly contests called as SRM. Requires some effort setting up the arena, but well worth the effort. It contains many good problems in Dynamic Programming, Math, Geometry and Graphs. For help in setting up, see this blog
Codechef Similar to the above two. It also hosts 10 day contests called as Long Challenge every month.
Hackerrank Also hosts weekly contests. It also contains basic programming tutorials. Good UI. You can buy testcases for hackos, which is usually good for training and getting ideas for corner cases.
Timus More like SPOJ. Contains collection of good problems. Unlike the above four, doesn't contain editorials, so hard to find solutions online.
Polish Online Judge - If you are looking for 'harder' problems.
Latest ones such as csacademy and Atcoder are definitely worth a try!

Algorithms:

IARCS for gentle introduction to the algorithms needed
A hackerearth blog with links to several good websites online
Stanford Course on competitive programming
Programming Camp Syllabus - A comprehensive list of topics required for competitive programming and some practice problems for them
A Codeforces blog with references to pretty much every good resource on competitive programming
A Codechef blog - lists pretty much every useful algorithm and data structure with links to tutorials and example problems
A good book on competitive programming
Another book with codes for most of the important algorithms

Gearing Up

Now that you tried some algorithms, and you want to take it to the next level. It would be good if you have some formal knowledge of algorithms. A really good book is Introduction to Algorithms. It covers a variety of topics. Here are some topics which you should really master-

Number Theory, combinatorics, algebra and mathematical problems in general.
Search, Sort, and Traverse algorithms - Although you should not write these algorithms in a contest environment and rather use the STL functions, you should have the knowledge of the working of those algorithms.
Data Structures - Arrays, Linked lists, stacks, queues, heap, trees, are some of the most commonly used data structures for a variety of problems, using and mastering the STL versions of these data structures will save a lot of time in contest environments and can help in solving the required problem much more efficiently (given you use the right data structure).
General algorithm categories - Dynamic programming, greedy algorithms, backtracking, constructive algorithms are topics that are frequently tested by competitive coding contests, Technical interviews in companies and the like.
Graph theory - This branch of competitive coding needs its own description. Graph algorithms span a wide variety of problems. Trivial problems use one or more combinations of graph traversal, connected components, spanning trees, shortest paths, Eulerian circuits and more. Make sure you gear up on some of these algorithms.

Taking it Forward

Competitive Programming is like any other sport and it requires practice to improve. As you become better and better, it becomes more fun.

Try to participate in as many live contests on Codeforces, Topcoder, Codechef and Hackerrank as possible. After every contest, read the solution and code at least one problem that you couldn't solve in the contest. This is very important: Just doing the contest itself won't help you to improve. Also, read the codes of top rated coders for the problems that you solved. You can learn many coding tricks from looking at their code.
Learn advanced algorithms such as network flows. Refer to resources above.
Form a team and register for ACM ICPC. Simply put, it's the Olympics of Competitive Programming.Teams to the world finals are selected based on 'Regionals' held in 3-4 Cities in India. Look at previous year problems and start practicing!
Try your hands on Google Code Jam and Facebook Hacker Cup

Competitive Programming

Contents