Competitive programming or sport programming is a

mind sport A mind sport is a game of skill based on intellectual ability. Etymology The first major use of the term was as a result of the Mind Sports Olympiad in 1997. The phrase had been used prior to this event such as backgammon being described as a ...

involving participants trying to program according to provided specifications. The contests are usually held over the

Internet The Internet (or internet) is the Global network, global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a internetworking, network of networks ...

or a

local network A local area network (LAN) is a computer network that interconnects computers within a limited area such as a residence, campus, or building, and has its network equipment and interconnects locally managed. LANs facilitate the distribution of d ...

. Competitive programming is recognized and supported by several multinational software and

companies, such as

Google Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...

, and Meta. A programming competition generally involves the host presenting a set of

logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...

al or

mathematical problem A mathematical problem is a problem that can be represented, analyzed, and possibly solved, with the methods of mathematics. This can be a real-world problem, such as computing the orbits of the planets in the Solar System, or a problem of a more ...

s, also known as

puzzle A puzzle is a game, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together ( or take them apart) in a logical way, in order to find the solution of the puzzle. There are differe ...

s or challenges, to the contestants (who can vary in number from tens or even hundreds to several thousand). Contestants are required to write

computer program A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. It is one component of software, which also includes software documentation, documentation and other intangibl ...

s capable of solving these problems. Judging is based mostly upon number of problems solved and time spent on writing successful solutions, but may also include other factors (quality of output produced, execution time, memory usage, program size, etc.).

History

One of the oldest contests known is the

International Collegiate Programming Contest The International Collegiate Programming Contest (ICPC) is an annual multi-tiered competitive programming competition among the universities of the world. Directed by ICPC Executive Director and Baylor Professor William B. Poucher, the ICPC oper ...

(ICPC) which originated in the 1970s and has grown to include 88 countries in its 2011 edition. From 1990 to 1994,

Owen Astrachan Owen Astrachan is an American computer scientist and professor of the practice of computer science at Duke University, where he is also the department's director of undergraduate studies. He is known for his work in curriculum development and met ...

, Vivek Khera and David Kotz ran one of the first distributed, internet-based programming contests inspired by the ICPC. Interest in competitive programming has grown extensively since 2000 to tens of thousands of participants (see Notable competitions), 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 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 Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

algorithmic game theory Algorithmic game theory (AGT) is an interdisciplinary field at the intersection of game theory and computer science, focused on understanding and designing algorithms for environments where multiple strategic agents interact. This research area com ...

, computational geometry, string analysis,

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

and

data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

s. Problems related to

constraint programming Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state t ...

and

artificial intelligence Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...

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 In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

, and implementing the algorithm in a suitable

programming language A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...

(the set of programming languages allowed varies from contest to contest). 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 (usually secret) 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 is 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 rank lists showing users with the biggest number of accepted solutions and/or shortest execution time for a particular problem.

Notable competitions

Algorithm competitions

In most of the above competitions, competitions are usually organized in several rounds. They usually start with online rounds, which conclude in the onsite final round. The top performers at IOI and ICPC receive gold, silver and bronze medals. In the other contests, cash prizes are awarded to the top finishers. The competitions also attract the interest of recruiters from multiple software and Internet companies, which often reach out to competitors with potential job offers.

Artificial intelligence and machine learning

* List may be incomplete

Contests focusing on open-source technologies

*List may be incomplete

Online platforms

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. Users will typically be assigned a rating based on their performance on said contests. The archives of past problems are popular resources for training in competitive programming. There are several organizations that host programming competitions on a regular basis. These include:

Benefits and criticism

Participation in programming contests may increase student enthusiasm for

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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 A programmer, computer programmer or coder is an author of computer source code someone with skill in computer programming. The professional titles Software development, ''software developer'' and Software engineering, ''software engineer' ...

. One critical point is that many fast-paced programming contests teach competitors bad programming habits and code style (like unnecessary use of macros, lack of OOP abstraction and comments, use of short variable names, etc.). Also, by offering only small algorithmic puzzles with relatively short solutions, programming contests like ICPC and IOI do not necessarily teach good

software engineering Software engineering is a branch of both computer science and engineering focused on designing, developing, testing, and maintaining Application software, software applications. It involves applying engineering design process, engineering principl ...

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 Peter Norvig (born 14 December 1956) is an American computer scientist and Distinguished Education Fellow at the Stanford Institute for Human-Centered AI. He previously served as a director of research and search quality at Google. Norvig is th ...

stated that based on the available data, being a winner of programming contests correlated negatively with a programmer's performance at their job at Google (even though contest winners had higher chances of getting hired). Norvig later stated that this correlation was observed on a small

data set A data set (or dataset) is a collection of data. In the case of tabular data, a data set corresponds to one or more table (database), database tables, where every column (database), column of a table represents a particular Variable (computer sci ...

, but that it could not be confirmed after examining a larger data set. 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. (2013). ''Competitive Programming 3: The New Lower Bound of Programming Contests''. Lulu. * Laaksonen, A. (2017). ''Guide to Competitive Programming'' (Undergraduate Topics in Computer Science). Cham: Springer International Publishing. * Xu, X. (2020) ''The development, prosperity and decline of Olympic in Informatics''. Publishe
online
* Kostka, B. (2021). ''Sports programming in practice.'' University of Wrocław.

References

{{Reflist, refs=https://www.atlantis-press.com/proceedings/icaicte-13/8933 * Computer science competitions