Competitive programming
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 problems, also known as puzzles, to the contestants, and contestants are required to write computer programs capable of solving each problem. Judging is based mostly upon number of problems solved and time spent for writing successful solutions, but may also include other factors
History
One of the oldest contests known is ICPC which originated in the 1970s, and has grown to include 88 countries in its 2011 edition.From 1990 to 1994, Owen Astrachan, Vivek Khera and David Kotz ran one of the first distributed, internet-based programming contests inspired by ICPC.
Interest in competitive programming has grown extensively since 2000, and is strongly connected to the growth of the Internet, which facilitates holding international contests online, eliminating geographical problems.
Overview
The aim of competitive programming is to write source code of computer programs which are able to solve given problems. A vast majority of problems appearing in programming contests are mathematical or logical in nature. Typical such tasks belong to one of the following categories: combinatorics, number theory, graph theory, geometry, string analysis and data structures. Problems related to artificial intelligence are also popular in certain competitions.Irrespective of the problem category, the process of solving a problem can be divided into two broad steps: constructing an efficient algorithm, and implementing the algorithm in a suitable programming language. These are the two most commonly tested skills in programming competitions.
In most contests, the judging is done automatically by host machines, commonly known as judges. Every solution submitted by a contestant is run on the judge against a set of test cases. Normally, contest problems have an all-or-none marking system, meaning that a solution is "Accepted" only if it produces satisfactory results on all test cases run by the judge, and rejected otherwise. However, some contest problems may allow for partial scoring, depending on the number of test cases passed, the quality of the results, or some other specified criteria. Some other contests only require that the contestant submit the output corresponding to given input data, in which case the judge only has to analyze the submitted output data.
Online judges are online environments in which testing takes place. Online judges have ranklists showing users with the biggest number of accepted solutions and/or shortest execution time for a particular problem.
Notable competitions
There are two types of competition formats: short-term and long-term. Each round of short-term competition lasts from 1 to 5 hours. Long-term competitions can last from a few days to a few months.Short-term
- International Collegiate Programming Contest – one of the oldest competitions, for students of universities in groups of 3 persons each
- International Olympiad in Informatics – one of the oldest competitions, for secondary school students
- American Computer Science League – computer science competition with written and programming portions, for middle/high school students
- CodeChef – competition held from 2009, there are two short contests held every month and an annual competition called CodeChef SnackDown
- Codeforces Round – typically two hour contest, held every week
- Facebook Hacker Cup – competition held from 2011, provided and sponsored by Facebook
- HackerRank – multiple competitions
- Gridwars – four competitions held between 2003 and 2004.
- Google Code Jam – competition held from 2003, provided and sponsored by Google
- IEEEXtreme Programming Competition – annual competition for IEEE Student Members held since 2006 by IEEE.
- Topcoder Open – Algorithm competition held since 2001 by Topcoder
Long-term
- HackerRank Week of Code
- ICFP Programming Contest – annual 3-day competition held since 1998 by the International Conference on Functional Programming
- Topcoder Marathon Matches
Artificial intelligence and machine learning
- Microprediction - live time series prediction on streams contributed by anyone
- Kaggle – machine learning competitions.
- CodeCup – board game AI competition held annually since 2003. Game rules get published in September and the final tournament is held in January.
- Google AI Challenge – bi-annual competitions for students that ran 2009 to 2011
- Halite – An AI programming challenge sponsored by Two Sigma, Cornell Tech, and Google
- Russian AI Cup open artificial intelligence programming contest
Contests focusing on open source technologies
- List may be incomplete
| Contest Name | Main Sponsor | Description | Running Since | Usual Time | Next Application Cycle | Status |
| Multi-Agent Programming Contest | Clausthal University of Technology in conjunction with agent-oriented workshops | Annual international programming competition to stimulate research in the area of multi-agent system development and programming. | 2005 | Sept | Sept 2011 | Active |
| Google Summer of Code | Google Inc. | An annual program in which Google awards stipends to hundreds of students who successfully complete a requested free software / open-source coding project during the summer. | 2005 | Mar-Aug | Mar 23- Apr 3 | Active |
| Google Highly Open Participation Contest | Google Inc. | A contest run by Google in 2007-8 aimed at high school students. The contest is designed to encourage high school students to participate in open source projects. | 2007 | Nov-Feb | Unknown | Unknown |
Online contest and training resources
The programming community around the world has created and maintained several internet-resources dedicated to competitive programming. They offer standalone contests with or without minor prizes. Also the past archives of problems are a popular resource for training in competitive programming. These include:| Name | Description | Website |
| CodeChef | Maintained by Directi, it hosts a 10-day-long contest and a couple of short contests every month, and provides a contest hosting platform to educational institutions for free. The top two winners of the long contest win cash prizes while the top 10 global get a tee-shirt. | |
| CodeCup | Annual international board game AI programming competition organized by the Dutch Olympiad in Informatics since 2003. | |
| Codeforces | Russian resource, maintained by ITMO University, which mostly provides frequent short contests. Special features: ability to check correctness of other contestants' solutions during "hacking phase", virtual contests, trainings etc. | |
| CodinGame | Puzzles, code golf. Hosts regular online competitions. | |
| HackerEarth | Bangalore, India based company providing online contest like environment aiming at providing recruitment assessment solutions. | |
| HackerRank | HackerRank offers programming problems in different domains of Computer Science. It also hosts annual Codesprints which help connect the coders and Silicon Valley startups. | |
| Project Euler | Large collection of computational math problems. | |
| Topcoder | US resource and company, which organizes contests and also provides industrial problems as a kind of free-lance job; it offers dozens of short contests and several long every year. Specific feature - participants have a chance to check correctness of other contestants' solutions after coding phase and before final automatic testing. | |
| UVa Online Judge | Contains over 4,500 problems for practising. Hosts regular online competitions. Opened in 1995, it is one of the oldest such websites. | |
| SPOJ | Polish online judge system which provides a lot of problems for training, and provides a platform for other organizers to host their programming contests. | |
| Open Kattis | Public version of the Kattis contest management system, with an archive of over 2600 problems. Kattis was developed to aid computer science courses, but it's also used to host prestigious competitions, like ICPC World Finals. | |
| AtCoder | Based in Japan, Atcode offers online programming contests on a weekly basis. The contests are offered in the Japanese and English language. | |
| Caribbean Online Judge | Spanish resource, maintained by University of Information Science. Contains over 3,000 problems for practicing. Also hosts regular online competitions. | |
| Microprediction.Org | Turnkey prediction of live data accomplished through streaming contests. |
Benefits and criticism
Participation in programming contests may increase student enthusiasm for computer science studies. The skills acquired in ICPC-like programming contests also improve career prospects, as they help to pass the "technical interviews", which often require candidates to solve complex programming and algorithmic problems on the spot.There has also been criticism of competitive programming, particularly from professional software developers. One critical point is that many fast-paced programming contests teach competitors bad programming habits and code style. Also, by offering only small algorithmic puzzles with relatively short solutions, programming contests like ICPC and IOI don't necessarily teach good software engineering skills and practices, as real software projects typically have many thousands of lines of code and are developed by large teams over long periods of time. Peter Norvig stated that based on the available data, being a winner of programming contests correlated negatively with a programmer's performance at his or her job at Google.
Yet another sentiment is that rather than "wasting" their time on excessive competing by solving problems with known solutions, high-profile programmers should rather invest their time in solving real-world problems.
Literature
- Halim, S., Halim, F.. Competitive Programming 3: The New Lower Bound of Programming Contests. Lulu.
- Laaksonen, A.. Guide to Competitive Programming. Cham: Springer International Publishing.