Competitive programming

Last updated

Petr Mitrichev (left) and Gennady Korotkevich (right), two prominent competitive programmers during the 2013 Yandex algorithm cup. IandeksAlgoritm.jpg
Petr Mitrichev (left) and Gennady Korotkevich (right), two prominent competitive programmers during the 2013 Yandex algorithm cup.

Competitive programming or sport programming is a mind sport involving participants trying to program according to provided specifications. The contests are usually held over the Internet or a local network. Competitive programming is recognized and supported by several multinational software and Internet companies, such as Google [1] [2] and Meta. [3]

Contents

A programming competition generally involves the host presenting a set of logical or mathematical problems, also known as puzzles or challenges, to the contestants (who can vary in number from tens or even hundreds to several thousand). Contestants are required to write computer programs 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 (ICPC) which originated in the 1970s [4] 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 the ICPC. [5]

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 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, algorithmic game theory, computational geometry, string analysis, discrete mathematics and data structures. [6] Problems related to constraint programming and 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 (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. [7]

Notable competitions

Algorithm competitions

Name of the competition [8] OrganizersAudienceDescriptionNumber of participants
Google Code Jam (GCJ) Google openAnnual competition organized and sponsored by Google from 2003 until its cancellation in 2023. [9] 32,702 (2022) [10]
International Collegiate Programming Contest (ICPC) [11] ICPC Foundationuniversity studentsTeam competition for university students, the contest consists of many regional rounds that conclude in a world final organized yearly. Teams consist of three students from the same university and they are allowed to use only one computer. [12] 50,000+ (2022) [13]
International Olympiad in Informatics (IOI)IOIsecondary school studentsInternational competition for secondary school students. Organized yearly since 1989. Each country can send at most 4 participants to compete.349 from 88 countries (2022) [14]
Meta Hacker Cup (formerly Facebook Hacker Cup) Meta Platforms openAnnual competition held since 2011. Organized and sponsored by Meta (formerly Facebook).27,604 (2022) [15]
Topcoder Open (TCO) Topcoder openAnnual algorithm competition held from 2001 until its cancellation in 2023 [16]

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

NameMain OrganizersDescriptionStatus
Kaggle GoogleData science, machine learning and mathematical optimization competition platform and online community.Active
AI Challenge University of WaterlooInternational artificial intelligence programming contest that ran from 2009 to 2011.Inactive
Halite AI Programming Competition Two Sigma, Cornell TechComputer programming contest where participants build bots in desired programming language to compete on a two-dimensional battlefield.Unknown
Russian AI Cup Mail.Ru Group, My.comAnnual artificial intelligence programming contest.Unknown

Contests focusing on open-source technologies

Contest NameMain SponsorDescriptionRunning SinceUsual TimeNext Application CycleStatus
Multi-Agent Programming Contest Clausthal University of Technology in conjunction with agent-oriented workshopsAnnual international programming competition to stimulate research in the area of multi-agent system development and programming.2005SeptSept 2011Active
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.2005Mar-AugMar 23- Apr 3Active
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.2007Nov-FebUnknownUnknown

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. Also the past archives of problems are a popular resource for training in competitive programming. There are several organizations that host programming competitions on a regular basis. These include:

NameDescription
Advent of Code An annual programming competition taking place during Advent, with a new pair of puzzles released each day, up to and including Christmas Day. The second problem of each day is locked until the completion of the first part, and usually follows on from it logically. There are both global and private leaderboards for each year, where rankings are based on who solves the problem first.
CodeChef [17] [18] Maintained by Unacademy, it hosts a 3-day-long contest and a couple of short contests every month (one IOI styled called Lunchtime and another ICPC styled called Cook-Off), 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 t-shirt.
Codeforces [19] [17] Russian resource, maintained by ITMO University, which mostly provides frequent (up to two per week) short contests. Special features: all solutions are open source, the ability to check the correctness of other contestants' solutions during the "hacking phase", virtual contests, trainings etc.
CodinGame Puzzles (increasing difficulty), code golf. Hosts regular online competitions (coding games and programming challenges).
HackerEarth [17] Bangalore, India based company providing an 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 [18] Large collection of computational math problems (i.e. not directly related to programming but often requiring programming skills for solving).
Topcoder [19] [17] 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 ("marathons") every year. Specific feature - participants have a chance to check the correctness of other contestants' solutions after the coding phase and before final automatic testing (so-called "challenge phase").
UVa Online Judge [19] [17] Contains over 4,500 problems for practising. Hosts regular online competitions. Opened in 1995, it is one of the oldest such websites.
SPOJ [17] Polish online judge system which provides a lot of problems for training, and provides a platform for other organizers to host their programming contests.
LeetCode LeetCode has over 2,300 questions covering many different programming concepts and offers weekly and bi-weekly contests. The programming tasks are offered in English and Chinese.

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. [19] [20]

There has also been criticism of competitive programming, particularly from professional software developers. [21] 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.). [22] [21] Also, by offering only small algorithmic puzzles with relatively short solutions, programming contests like ICPC and IOI do not 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. [21] Peter Norvig 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). [23] Norvig later stated that this correlation was observed on a small data set, but that it could not be confirmed after examining a larger data set. [24] [ unreliable source? ]

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. [21]

Literature

See also

Related Research Articles

<span class="mw-page-title-main">International Olympiad in Informatics</span> Annual programming competition

The International Olympiad in Informatics (IOI) is an annual competitive programming competition and one of the International Science Olympiads for secondary school students. The first IOI was held in 1989 in Pravetz, Bulgaria. It is the second largest science olympiad, after the International Mathematical Olympiad, in terms of number of participating countries. Each country sends a team of up to four students, plus one team leader, one deputy leader, and guests.

<span class="mw-page-title-main">International Collegiate Programming Contest</span> Worldwide competitive programming contest for university students

The International Collegiate Programming Contest, known as the 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 operates autonomous regional contests covering six continents culminating in a global World Finals every year. In 2018, ICPC participation included 52,709 students from 3,233 universities in 110 countries.

Topcoder is a crowdsourcing company with an open global community of designers, developers, data scientists, and competitive programmers. Topcoder pays community members for their work on the projects and sells community services to corporate, mid-size, and small-business clients. Topcoder also organizes the annual Topcoder Open tournament and a series of smaller regional events.

Hong Kong Olympiad in Informatics is an annual programming competition for secondary school students in Hong Kong, emphasizing on problem solving techniques and programming skills. It is co-organized by the Hong Kong Association for Computer Education (HKACE) and the Hong Kong Education Bureau (EDB). It serves as a preliminary contest to international, national and regional competitions such as the China National Olympiad in Informatics (NOI) and the International Olympiad in Informatics (IOI). The first HKOI was held in 1997.

The United States of America Computing Olympiad (USACO) is an online computer programming competition, which serves as qualification for the International Olympiad in Informatics (IOI) in the United States of America. Primarily for secondary school students in the United States, the USACO offers four competitions during the academic year. Participants compete in four increasingly difficult divisions, each of which is provided a distinct set of 3 solvable competitive programming problems during each contest. Coding & submitting computer programs can be done in one of four languages: C, C++, Java, and Python. Competitors begin in the Bronze division, and advance through the levels by performing well in their current division.

PC² is the Programming Contest Control System developed at California State University, Sacramento in support of Computer Programming Contest activities of the ACM, and in particular the ACM International Collegiate Programming Contest. It was used to conduct the ACM ICPC World Finals in 1990 and from 1994 through 2009. In 2010, the ACM ICPC World Finals switched to using Kattis, the KTH automated teaching tool; however, PC2 continues to be used for a large number of ICPC Regional Contests around the world.

<span class="mw-page-title-main">Google Code Jam</span> Programming competition hosted by Google

Google Code Jam was an international programming competition hosted and administered by Google. The competition began in 2003. The competition consists of a set of algorithmic problems which must be solved in a fixed amount of time. Competitors may use any programming language and development environment to obtain their solutions. From 2003 to 2007, Google Code Jam was deployed on Topcoder's platform. Since 2008 Google has developed their own dedicated infrastructure for the contest.

UVa Online Judge is an online automated judge for programming problems hosted by University of Valladolid. Its problem archive has over 4300 problems and user registration is open to everyone. There are currently over 100000 registered users. A user may submit a solution in ANSI C (C89), C++ (C++98), Pascal, Java, C++11 or Python. Originally it began without the last three options, but the Java option was added in 2001, the C++11 option was added in 2014, then the Python option was added in 2016.

SPOJ is an online judge system with over 1 million registered users and over 20,000 problems. Tasks are prepared by its community of problem setters or are taken from previous programming contests. SPOJ allows advanced users to organize contests under their own rules and also includes a forum where programmers can discuss how to solve a particular problem.

<span class="mw-page-title-main">Petr Mitrichev</span> Russian sport programmer

Petr Mitrichev is a Russian competitive programmer who has won multiple major international competitions. His accomplishments include gold and silver (2001) medals in the IOI, gold medals in the ACM ICPC World Finals as part of the team of Moscow State University and winning Google Code Jam (2006), the Topcoder Open, the Topcoder Collegiate Challenge, Facebook Hacker Cup as well as numerous national and online contests. He has achieved the highest rating ever among the Algorithm competitors of Topcoder and consistently ranks in the top two of the world. He is the second highest rated Algorithm coder on Topcoder ratings as of February 2021. He currently works at Google on the search engine and helps to prepare Code Jam.

Meta Hacker Cup is an annual international programming competition hosted and administered by Meta Platforms. The competition began in 2011 as a means to identify top engineering talent for potential employment at Meta Platforms. The competition consists of a set of algorithmic problems which must be solved in a fixed amount of time. Competitors may use any programming language and development environment to write their solutions.

Crowdsourcing software development or software crowdsourcing is an emerging area of software engineering. It is an open call for participation in any task of software development, including documentation, design, coding and testing. These tasks are normally conducted by either members of a software enterprise or people contracted by the enterprise. But in software crowdsourcing, all the tasks can be assigned to or are addressed by members of the general public. Individuals and teams may also participate in crowdsourcing contests.

<span class="mw-page-title-main">Gennady Korotkevich</span> Belarusian competitive programmer (born 1994)

Gennady Korotkevich is a Belarusian competitive sport programmer who has won major international competitions since the age of 11, as well as numerous national competitions. His top accomplishments include six consecutive gold medals in the International Olympiad in Informatics as well as the world championship in the 2013 and 2015 International Collegiate Programming Contest World Finals. As of October 2023, Gennady is the highest-rated programmer on Codeforces, CodeChef, Topcoder, AtCoder and HackerRank. In January 2022, he achieved a historic rating of 3979 on Codeforces, becoming the first to break the 3900 barrier.

<span class="mw-page-title-main">CodeChef</span> Global competitive programming platform

CodeChef is an online educational and competitive programming platform. CodeChef started as an educational initiative in 2009 by Directi, an Indian software company. In 2020, it was purchased by Unacademy.

<span class="mw-page-title-main">Topcoder Open</span>

Topcoder Open (TCO) was an annual design, software development, data science and competitive programming championship organized by Topcoder, and hosted in different venues around US. In the first two years, 2001 and 2002, the tournament was titled TopCoder Invitational.

Codeforces is a website that hosts competitive programming contests. It is maintained by a group of competitive programmers from ITMO University led by Mikhail Mirzayanov. Since 2013, Codeforces claims to surpass Topcoder in terms of active contestants. As of 2019, it has over 600,000 registered users. Codeforces along with other similar websites are used by some sport programmers, like Gennady Korotkevich, Petr Mitrichev, Benjamin Qi and Makoto Soejima, and by other programmers interested in furthering their careers.

Makoto Soejima is a Japanese former competitive programmer. He is one of three people to have won both the Google Code Jam and the Facebook Hacker Cup and the only one to have also won a gold medal with a perfect score at the International Mathematical Olympiad (IMO). In International Science Olympiads, he has won three gold medals and one bronze in the International Mathematical Olympiad as well as two silver medals in the International Olympiad in Informatics (IOI).

<span class="mw-page-title-main">Harsha Suryanarayana</span> Indian programmer

Harsha Suryanarayana, popularly known as "humblefool" in the coding community, was an Indian programmer who is often considered to be "India's greatest coder".

Tiancheng Lou is a Chinese businessman who is the co-founder and chief technology officer of Pony.ai, an autonomous vehicle technology company. He is also a competitive programmer whose achievements include winning the Google Code Jam twice in 2008 and 2009, winning the Topcoder Open Marathon in 2015 and being a gold medalist at the 2004 International Olympiad in Informatics, coming third overall. In terms of prize money won in major competitions, Lou is currently the most successful competitive programmer from China.

Andrew He is an American competitive programmer and the winner of the 2021 Facebook Hacker Cup.

References

  1. ↑ "Google Code Jam". google.com. Archived from the original on May 31, 2023. Retrieved February 20, 2016.
  2. ↑ "TCO12 Sponsor: Google - TCO 12". topcoder.com. Archived from the original on February 16, 2012.
  3. ↑ "Facebook Hacker Cup". Facebook. Retrieved February 20, 2016.
  4. ↑ Li, Yujia; Choi, David; Chung, Junyoung; Kushman, Nate; Schrittwieser, Julian; Leblond, Rémi; Eccles, Tom; Keeling, James; Gimeno, Felix; Lago, Agustin Dal; Hubert, Thomas; Choy, Peter; d'Autume, Cyprien de Masson; Babuschkin, Igor; Chen, Xinyun (December 9, 2022). "Competition-Level Code Generation with AlphaCode". Science. 378 (6624): 1092–1097. arXiv: 2203.07814 . doi:10.1126/science.abq1158. ISSN   0036-8075.
  5. ↑ Khera, Vivek; Astrachan, Owen; Kotz, David (1993). "The internet programming contest" (PDF). ACM SIGCSE Bulletin. 25 (1): 48–52. doi:10.1145/169073.169105. ISSN   0097-8418. Archived from the original (PDF) on August 8, 2017. Retrieved March 10, 2020.
  6. ↑ Pak, Igor. "Algorithms". Math 182. University of California, Los Angeles. Retrieved March 31, 2024.
  7. ↑ Programming Challenges (Skiena & Revilla) ISBN   0387001638, ISBN   978-0387001630
  8. ↑ Kostka, Bartosz (2021). Sports Programming in Practice (PDF). University of Wrocław.
  9. ↑ "Celebrate Google's Coding Competitions with a final round of programming fun". Google Developers Blog. Google. Retrieved February 28, 2023.
  10. ↑ "Code Jam - Google's Coding Competitions". Coding Competitions. Archived from the original on June 27, 2023. Retrieved February 26, 2023.
  11. ↑ "ICPC". icpc.global. Retrieved February 26, 2023.
  12. ↑ "Programming Environment – ICPC Documents" . Retrieved February 15, 2024.
  13. ↑ "ICPC". icpc.global. Retrieved February 26, 2023.
  14. ↑ "Olympiads". stats.ioinformatics.org. Retrieved February 26, 2023.
  15. ↑ "Meta Hacker Cup - 2022 - Qualification Round". www.facebook.com. Retrieved February 26, 2023.
  16. ↑ "FAQ - Topcoder Community Town Hall with Doug Hanson, Topcoder CEO". Topcoder. Retrieved February 28, 2023.
  17. 1 2 3 4 5 6 Luigi, William Di; Farina, Gabriele; Laura, Luigi; Nanni, Umberto; Temperini, Marco; Versari, Luca (2016). "oii-web: an Interactive Online Programming oii-web: an Interactive Online Programming Contest Training System" (PDF). Olympiads in Informatics. 10: 207–222. doi:10.15388/ioi.2016.13. S2CID   6877554.
  18. 1 2 Combéfis, Sébastien; Wautelet, Jérémy (2014). "Programming Trainings and Informatics Teaching Through Online Contests" (PDF). Olympiads in Informatics. 8: 21–34.
  19. 1 2 3 4 Bloomfield, Aaron; Sotomayor, Borja. "A Programming Contest Strategy Guide" (PDF). SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education.
  20. ↑ Jackson, Dean (December 1, 2013). "The Google Technical Interview. How to Get Your Dream Job" (PDF). XRDS: Crossroads, the ACM Magazine for Students. 20 (2): 12–14. doi:10.1145/2539270. S2CID   27549057.
  21. 1 2 3 4 Smith, Duncan (December 2, 2015). "The Competitive Programming Debate".
  22. ↑ Halim, Steven. "CS3233 - Competitive Programming". NUS School of Computing.
  23. ↑ "Winning at programming competitions is a negative factor for being good on the job". YouTube . April 5, 2015.
  24. ↑ "HN discussion on correlation between job performance and competitive programming". December 2020.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.