Competitive Programming

Wikipedia defines competitive programming best:


Competitive programming is a mind sport usually held over the Internet or a local network, involving participants trying to program according to provided specifications. Contestants are referred to as sport programmers. Competitive programming is recognized and supported by several multinational software and Internet companies, such as Google, and Facebook. There are several organizations who host programming competitions on a regular basis.

A programming competition generally involves the host presenting a set of logical or mathematical practiceProblems to the contestants (who can vary in number from tens to several thousands), and contestants are required to write computer programs capable of solving each problem. Judging is based mostly upon number of practiceProblems solved and time spent for writing successful solutions, but may also include other factors (quality of output produced, execution time, program size, etc.)

The best way is to just dive in and start coding. Pick a programming language you are comfortable with and go to any one of the various competitive programming websites and start solving the easier practiceProblems. If you have limited experience in programming in general too, aim to solve hundreds of simple practiceProblems. This will acquaint you with the basic patterns of coding.

Initially focus on learning the language - its syntax and library. That can be done by first solving practiceProblems and then looking at others' solution to the problem. While looking at others' code, attention should be paid to how they use the language features and library to write concise code.

More Info
Codechef Getting Started page
Spoj simple practiceProblems

Any programming language that you are already familiar with is the best. Most sites support a huge range of languages. However if you are preparing for ICPC, C++ or Java are the best ones as they are the allowed languages at ICPC. Note that most sites usually have a time multiplier for Java as it is usually slower than C++.

Between C++ and Java any is fine. While C++ generally leads to shorter code, that should not be the main factor for choosing it. If you are using Java, make sure to use proper fast I/O so that your code does not take a long time to read the input. If you are still unsure, just try both of them and choose whichever you like better.

Whatever language you choose, first learn its basic syntax. Then focus on getting familiar with its standard library. Knowing the standard library really well is the key to fast and accurate implementation. Knowing that there is a library function for doing a particular task will help avoid wasting time by coding your own implementation.

Useful C++ Links
Basic C++ tutorial
C++ Reference
C++ tricks
STL tutorial
C++ I/O Optimizations
Useful Java Links
Basic Java tutorial
Java Reference
Java I/O
There are too many sites to list all of them here. Instead we will list out the more popular ones. Besides practice practiceProblems, some of these sites hold regular long and short contests. If you want to see the upcoming ones, do visit our contests page.
SiteComment
Topcoder It is one of the oldest site to host regular short contests. The quality of problem is quite high and consitent. Topcoder conducts a 1 hr 35 min contest called "Single Round Match" (SRM) frequently
Codeforces Probably the most popular site right now, codeforces has a variety of practiceProblems and regular Div 1 and Div 2 rounds
Codechef Codechef holds monthly long contests (with big prize money!). It also holds regular short contest named cookoff. Apart from the 2, there is also a monthly contest named lunchtime, targetted specifically at school and IOI students. It has quality editorials for most practiceProblems
Spoj Spoj has a huge collection of practiceProblems on almost every area of competitive programming
You can get info on all the topics required from various sources online, but if you like all things in one place, maybe books are the way to go. Here are some useful books on algorithms and competitive programming:
BookComment
Often called "CLRS" after the initials of the author, it is used as the algorithm reference at many colleges. Do attempt and solve the exercises to get the most out of this book.
Aimed specifically at competitive programmers, this book has a brief overview of each algorithm followed by a ton of practiceProblems on that topic.

First find some good tutorials/articles on that topic. It helps to find multiple articles so that you get different perspectives on the same topic. Try going through them and understanding them. The next step depends on if you are learning some specific algorithm (like, say, DFS/BFS, KMP etc.) or a technique (like Dynamic Programming, Greedy etc.).

If you are learning a specific algorithm, walk through the pseudo-code/code on an actual example to get the feel of the algorithm. Also, some prefer to first use it as a black box. Learn where and how it is used and just use it without knowing how exactly it works. Then try implementing the algorithm on your own in your favourite language.

If you are learning a general technique, after reading the basics, it is best to go through a lot of classical algorithms that uses the technique. For example, if you are learning dynamic programming, go through classic DP algorithms like edit distance, knapsack dp etc.

Finally whether you are learning an algorithm or technique, practice a LOT of practiceProblems on that topic.

So, you know all the basic algorithms, their usage and can probably solve the first 2 practiceProblems of a Div 2 round? That's great. Now improving gets slightly harder than before. First off, we would recommend solving lots of adhoc/implementation problem so that your implementation and general understanding skill is strengthened. This will help you as you learn more advanced algorithms and techniques.

After that it is just a matter of smart practicing. The trick is to always try practiceProblems which are just beyond your current ability. This will ensure you are always improving. Solving one single good medium problem is way better than solving a ton of easy practiceProblems at this stage.

Upsolving

What does that mean? After a contest, try solving the easiest problem that you could not solve. If you are consistently unable to solve a problem of a particular type, then you should learn it in depth.

Besides the regular contests listed above, there are some annual contests run regularly by various organizations. Here are some of the popular ones:
Contests
International Olympiad in Informatics (IOI)
International Collegiate Programming Contest (ICPC)
Google Code Jam
Topcoder Open
Facebook Hackercup
Codechef Snackdown
Internet Problem Solving Contest

ICPC is a team contest, so it is very important to work on it as a team. Of course every team member must know the basics of all topics, so all the individual practice tips given above apply here too. Specifically for ICPC, analyze each of the team member's weak and strong areas. Then make sure that each topic is at least 1 member's strong area.

Another important thing is to understand the penalty system intuitively. For example, if you solve the first problem just 5 min late, and then go on to solve 8 practiceProblems, then the first problem's penalty actually becomes 40 (5 * 8 - since the penalties are added for each problem). So it is vitally important to solve the easiest problem asap.

To achieve the above, make sure there is a team plan. Maybe 2 of the team will go through the practiceProblems (one from front and one from back) while the 3rd starts typing the basic code template. Basically try to get the first few practiceProblems quickly.

Also, practice a lot together so that you become good at solving the harder practiceProblems together.

Competitive programming helps a lot in clearing the interview for the said software job. If you are good at competitive programming, then the algorithm round of the interview will be a breeze. Some companies like Google have only algo rounds , so it will be easy to get into those companies if you are good at competitive programming

Coming back to the question, while you will rarely implement a segment tree or dynamic programming in a software job, the computational thinking skils develped in competitive programming will always help. We have found that debugging and (especially) thinking about corner cases are things that are very useful in both competitive programming and actual software jobs.

code-drills

We built code-drills primarily for problem recommendations. Whenever we sat down for practicing we faced a big problem: what problem to solve next? So we decided to build code-drills to recommend practiceProblems to solve next based on your past submissions.

Right now we analyze and recommend from 3 sites: Codeforces, Codechef and Spoj.
  • Each handle should be prefixed with the site prefix (in lowercase) of that handle
  • Sites supported
    Site Prefix Example
    Codeforces cf/
    no prefix
    cf/tourist
    petr
    Codechef cc/ cc/mugurelionut
    Spoj sp/ sp/xilinx
  • You can apply multiple prefixes to same handle. This is useful if the same handle is used across multiple sites
    e.g. cf/sp/cc/acrush
  • Different handle groups should be space separated
    e.g. cc/sp/balajiganapath cf/balajiganapathi
RecommendationComment
WarmupThis just recommends very easy problem and is ideal for solving before start of contest or a long practice session
Daily PracticeIt has one easy problem and one medium problem. It is best for individual practice if you don't have the time to do a big practice session. It should ideally just take an hour or so
Easy/Medium/HardWe especially recommend the medium recommendations. These are the ones which are just beyond your solved practiceProblems level
ICPCRecommended for a full fledged team practice. Enter all the handles of the entire team for best results
Strong/weak areasRecommendation in your strong/weak areas. If you are practicing the weak areas, we recommend soving the middle ones as those are the medium ones
Topic recommendationJust as above, the middle ones in the list are the medium ones

That depends on how you want to practice and how much time you have. If you are in a hurry, the Daily Practice is what will be most useful. It has 1 easy problem and 1 medium problem. If you have enough time, the best one is either the Medium or Weak Area recommendations.

Of course if you want to practice a particular topic, the recommendation for that topic is the best. Keep in mind that the recommendations for each tag start with easy practiceProblems. So sometimes, you may want to skip the first 3-4 practiceProblems and directly jump to the middle of the list

For team practice, ICPC recommendations is the best. We would also recommend taking a look at the team's weak areas and focussing on those topics individually or using the Weak Area recommendation

We just aggregate the information from all the handles of sites you have enterred. There are a few things to keep in mind while looking at the verdicts chart:

  1. We count codechef's partial accepted as AC
  2. We map every non standard verdict of codeforces to the Other verdict tag

We look at tags of all practiceProblems you have solved and aggregate them from the handles enterred. There are a few things to keep in mind while looking at the tags chart:

  1. The count shown in title may not match the sum of the counts shown in the chart. This is because tag stats is actually a count of (problem, tag) pair. i.e. if a problem has 2 tags then both the tags' count are incremented
  2. Untagged practiceProblems are those which have no tag in their corresponding sites
  3. The tags are mapped to Adhoc or Implementation when none of the other tags are a good fit

Strong/weak areas are relative to your own submissions. We look at some of the hardest practiceProblems you have solved in a particular topic and compare it with your performance on other topics to compute your strong and weak areas

We use the number of users who have solved the problem to estimate its difficulty. The recommendations are relative to the difficulty of your solved practiceProblems so far. So, for example, the easy recommendations for a red coder will be harder than the easy recommendations for a grey coder