Jump to content

Competitive programming

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by CodeTalker (talk | contribs) at 02:03, 29 December 2023 (rvt per MOS:OVERLINK). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Petr Mitrichev (left) and Gennady Korotkevich (right), two prominent competitive programmers during a contest.

Competitive 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. Contestants are referred to as sport programmers. Competitive programming is recognized and supported by several multinational software and Internet companies, such as Google[1][2] and Facebook.[3]

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 and data structures. 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.[6]

Notable competitions

Algorithm competitions

Name of the competition[7] Organizers Audience Description Number of participants Website
Google Code Jam (GCJ) Google open Annual competition organized and sponsored by Google from 2003 until its cancellation in 2023.[8] 32,702 (2022)[9] https://codingcompetitions.withgoogle.com/codejam Archived 2022-06-24 at the Wayback Machine
International Collegiate Programming Contest (ICPC)[10] ICPC Foundation university students Team 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. 50,000+ (2022)[11] https://icpc.global/
International Olympiad in Informatics (IOI) IOI secondary school students International competition for secondary school students. Organized yearly since 1989. Each country can send at most 4 participants to compete. 349 from 88 countries (2022)[12] https://ioinformatics.org/
Meta Hacker Cup (formerly Facebook Hacker Cup) Meta Platforms open Annual competition held since 2011. Organized and sponsored by Meta (formerly Facebook). 27,604 (2022)[13] https://www.facebook.com/codingcompetitions/hacker-cup
Topcoder Open (TCO) Topcoder open Annual algorithm competition held from 2001 until its cancellation in 2023[14] https://www.topcoder.com/community/member-programs/topcoder-open/

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

[15]

  • Kaggle – data science and 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.[16][17][18]
  • Google AI Challenge – bi-annual competitions for students that ran from 2009 to 2011.
  • Halite[19] – An AI programming challenge sponsored by Two Sigma, Cornell Tech,[20] and Google.[21]
  • Russian AI Cup – open artificial intelligence programming contest.
  • CodinGame – hosts seasonal bot programming competitions.

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 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:

Name Description Website
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. adventofcode.org
beecrowd Largest competitive programming platform based in Latin America. Contains 2300+ programming challenges in 3 different languages (English, Portuguese and Spanish), classified in 9 categories and 10 different levels of difficulty. It hosts frequent competitions sponsored by corporations and by themselves. It was formerly known as URI Online Judge. www.beecrowd.com.br
CodeChef[22][23] 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. www.codechef.com
CodeCup Annual international board game AI programming competition organized by the Dutch Olympiad in Informatics since 2003.[17][18] codecup.nl
Codeforces[24][22] 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. codeforces.com
CodinGame Puzzles (increasing difficulty), code golf. Hosts regular online competitions (AI сhallenges, optimization problems). www.codingame.com
HackerEarth[22] Bangalore, India based company providing an online contest like environment aiming at providing recruitment assessment solutions. www.hackerearth.com
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. hackerrank.com
Project Euler[23] Large collection of computational math problems (i.e. not directly related to programming but often requiring programming skills for solving). projecteuler.net
Topcoder[24][22] 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"). www.topcoder.com
UVa Online Judge[24][22] Contains over 4,500 problems for practising. Hosts regular online competitions. Opened in 1995, it is one of the oldest such websites. onlinejudge.org
SPOJ[22] Polish online judge system which provides a lot of problems for training, and provides a platform for other organizers to host their programming contests. www.spoj.com
Open Kattis Public version of the Kattis contest management system, with an archive of over 2600 problems.[24] Kattis was developed to aid computer science courses, but it's also used to host prestigious competitions, like ICPC World Finals.[25] open.kattis.com
AtCoder Based in Japan, AtCoder offers online programming contests on a weekly basis. The contests are offered in Japanese and English.

As of 2020, it is one of the most popular platforms of its kind.[26]

atcoder.jp
Timus Contains problems from competitions in the Ural region. acm.timus.ru
VJudge Contains problems from many online judges. vjudge.net
Baekjoon OJ Korean online judge. acmicpc.net
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. leetcode.com
Luogu Luogu is an online judge in China. It contains many problems from Chinese Olympiads in Informatics organized by the China Computer Federation, as well as user-hosted contests. luogu.com.cn

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.[24][27]

There has also been criticism of competitive programming, particularly from professional software developers.[28] 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.).[29][28] 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.[28] 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).[30] 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 [31][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.[28]

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. Published online.
  • Kostka, B. (2021). Sports programming in practice. University of Wrocław.

See also

References

  1. ^ "Google Code Jam". google.com. Archived from the original on 2023-05-31. Retrieved 2016-02-20.
  2. ^ "TCO12 Sponsor: Google - TCO 12". topcoder.com. Archived from the original on February 16, 2012.
  3. ^ "Facebook Hacker Cup". Facebook. Retrieved 2016-02-20.
  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 (2022-12-09). "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 2017-08-08. Retrieved 2020-03-10.
  6. ^ Programming Challenges (Skiena & Revilla) ISBN 0387001638, ISBN 978-0387001630
  7. ^ Kostka, Bartosz (2021). Sports Programming in Practice (PDF). University of Wrocław.
  8. ^ "Celebrate Google's Coding Competitions with a final round of programming fun". Google Developers Blog. Google. Retrieved 28 February 2023.
  9. ^ "Code Jam - Google's Coding Competitions". Coding Competitions. Archived from the original on 2023-06-27. Retrieved 2023-02-26.
  10. ^ "ICPC". icpc.global. Retrieved 2023-02-26.
  11. ^ "ICPC". icpc.global. Retrieved 2023-02-26.
  12. ^ "Olympiads". stats.ioinformatics.org. Retrieved 2023-02-26.
  13. ^ "Meta Hacker Cup - 2022 - Qualification Round". www.facebook.com. Retrieved 2023-02-26.
  14. ^ "FAQ - Topcoder Community Town Hall with Doug Hanson, Topcoder CEO". Topcoder. Retrieved 28 February 2023.
  15. ^ "14 Active AI Game Competitions to Check Out in 2022 (Ongoing & Upcoming)". www.gocoder.one.
  16. ^ "CodeCup". www.codecup.nl.
  17. ^ a b Lasse Hakulinen. Survey on Informatics Competitions: Developing Tasks – Olympiads in Informatics, 2011, Vol. 5, 12–25.
  18. ^ a b Wevers, Lesley (2014). "Monte-Carlo Tree Search for Poly-Y" (PDF). University of Twente. Archived from the original (PDF) on 13 April 2017. Retrieved 16 September 2018.
  19. ^ "Halite Artificial Intelligence Programming Challenge". www.halite.io.
  20. ^ "Two Sigma Announces Public Launch of Halite". tech.cornell.edu. 2 November 2016.
  21. ^ "Halite helps students and developers compete to build better AI on Google Cloud Platform". Archived from the original on 2023-01-31. Retrieved 2017-11-17.
  22. ^ a b c d e f 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.
  23. ^ a b Combéfis, Sébastien; Wautelet, Jérémy (2014). "Programming Trainings and Informatics Teaching Through Online Contests" (PDF). Olympiads in Informatics. 8: 21–34.
  24. ^ a b c d e Bloomfield, Aaron; Sotomayor, Borja. "A Programming Contest Strategy Guide" (PDF). SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education.
  25. ^ Enström, E.; Kreitz, G.; Niemelä, F.; Söderman, P.; Kann, V. (2011). "Five years with Kattis – using an automated assessment system in teaching" (PDF). IEEE Frontiers in Education Conference.
  26. ^ Mirzayanov, Mike; Pavlova, Oksana; Mavrin, Pavel; Melnikov, Roman; Plotnikov, Andrew; Parfenov, Vladimir; Stankevich, Andrew (2020). "Codeforces as an Educational Platform for Learning Programming in Digitalization" (PDF). Olympiads in Informatics. 14. ISSN 1822-7732.
  27. ^ 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.
  28. ^ a b c d Smith, Duncan (December 2, 2015). "The Competitive Programming Debate".
  29. ^ Halim, Steven. "CS3233 - Competitive Programming". NUS School of Computing.
  30. ^ "Winning at programming competitions is a negative factor for being good on the job". YouTube. April 5, 2015.
  31. ^ "HN discussion on correlation between job performance and competitive programming". December 2020.
Open-source project for running contests
Retrieved from "https://en.wikipedia.org/w/index.php?title=Competitive_programming&oldid=1192387832"