Competitive programming

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Open championship on programming Yandex.Algorithm, August 22, 2013.

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,[1][2] and Facebook.[3] 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 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 problems solved and time spent for writing successful solutions, but may also include other factors (quality of output produced, execution time, program size, etc.)

History[edit]

One of the oldest contests known is ACM-ICPC which originated in the 1970s, and has grown to include 88 countries in its 2011 edition. Interest in competitive programming has grown extensively[quantify] since 2000, and is strongly connected to the growth of the Internet, which facilitates holding international contests online, eliminating geographical problems.

Overview[edit]

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 (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 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.

Notable competitions[edit]

There are two types of competition formats: short-term and long-term. Each round of short-term competition lasts from 1 to 3 hours. Long-term competitions can last from a few days to a few months.

Short-term[edit]

In most of the above competitions, since the number of contestants is quite large, competitions are usually organized in several rounds. They usually require online participation in all rounds except the last, which require onsite participation. A special exception to this is IEEEXtreme, which is a yearly 24-hour virtual programming competition. The top performers at IOI and ACM-ICPC receive gold, silver and bronze medals while in the other contests, cash prizes are awarded to the top finishers. Also hitting the top places in the score tables of such competitions may attract interest of recruiters from software and Internet companies.

Long-term[edit]

Online contest and training resources[edit]

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:

Similarweb Rank Name Description Website
6047[11] HackerRank "Most Innovative" Competitive Programming website. It was started in 2012, and 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
9412[12] GeeksforGeeks A programming website with articles and practice platform. The site is mainly targeted for programming interview preparation. It was started in 2009 and competitive programming platform Practice was added in 2015 geeksforgeeks.org
14366[13] Codeforces Russian resource, maintained by Saratov State University, which mostly provides frequent (up to two per week) short contests. Special features: ability to check correctness of other contestants' solutions during "hacking phase", virtual contests, trainings etc. codeforces.com
23477[14] HackerEarth Bangalore, India based company providing online contest like environment aiming at providing recruitment assessment solutions. www.hackerearth.com
26450[15] CodeChef Maintained by Directi, it hosts a 10-day-long contest and a couple of short contests every month (one IOI styled and other ACM ICPC styled), 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. www.codechef.com
27239[16] CodinGame Puzzles (increasing difficulty), code golf. Hosts regular online competitions (AI Challenges, optimization problems) www.codingame.com
43360[17] 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 ("marathons") every year. Specific feature - participants have a chance to check correctness of other contestants' solutions after coding phase and before final automatic testing (so called "challenge phase"). www.topcoder.com
48672[18] Project Euler Large collection of computational math problems (i.e. not directly related to programming but often requiring programming skills for solving). projecteuler.net
67605[19] 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. www.spoj.com
100204[20] AtCoder AtCoder is a new but phenomenal contest platform created by a team of highly-rated Japanese competitive programmers. atcoder.jp/
147369[21] POJ Peking University judge online for ACM/ICPC created by Ying Fuchen, Xu Pengcheng and Xie Di. Contains 3,055 problems. www.poj.org
172157 Coderbyte Contains programming challenges you can solve in an online editor in one of nine programming languages. Also provides algorithm tutorials, introductory JavaScript courses, video tutorials, and job interview preparation material. www.coderbyte.com
914887[22] Riddles.io Long running competitive programming competitions with prizes since 2016. riddles.io
NA CS Academy Hosts regular online competitions with prizes. csacademy.com
NA UVa Online Judge Contains over 3,500 problems for practising. Hosts regular online competitions. uva.onlinejudge.org
NA Kattis Sweden-based competitive programming website in English www.kattis.com

See also[edit]

References[edit]

  1. ^ "Google Code Jam". google.com. 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. ^ "Programming problems and Competitions :: HackerRank". HackerRank. Retrieved 2016-02-20. 
  5. ^ "Programming problems and Competitions :: HackerRank". HackerRank. Retrieved 2016-02-20. 
  6. ^ a b c "COMPETE - CodeChef". codechef.com. Retrieved 2016-02-20. 
  7. ^ "Snackdown Home - CodeChef". codechef.com. 
  8. ^ "Al Zimmermann's Programming Contests". azspcs.com. 
  9. ^ "Halite Artificial Intelligence Programming Challenge". halite.io. 
  10. ^ "Two Sigma Announces Public Launch of Halite". tech.cornell.edu. 
  11. ^ "Security Screen". www.similarweb.com. Retrieved 2015-10-18. 
  12. ^ "Security Screen". www.similarweb.com. Retrieved 2016-07-09. 
  13. ^ "Security Screen". www.similarweb.com. Retrieved 2015-10-18. 
  14. ^ "Security Screen". www.similarweb.com. Retrieved 2015-10-18. 
  15. ^ "Security Screen". www.similarweb.com. Retrieved 2015-10-18. 
  16. ^ "Security Screen". www.similarweb.com. Retrieved 2016-10-19. 
  17. ^ "Security Screen". www.similarweb.com. Retrieved 2015-10-18. 
  18. ^ "Security Screen". www.similarweb.com. Retrieved 2015-10-18. 
  19. ^ "Security Screen". www.similarweb.com. Retrieved 2015-10-18. 
  20. ^ "atcoder.jp Traffic Statistics". SimilarWeb. Retrieved 2016-12-24. 
  21. ^ "Security Screen". www.similarweb.com. Retrieved 2016-04-20. 
  22. ^ "Security Screen". www.similarweb.com. Retrieved 2017-02-06. 

External links[edit]

Open-source project for running contests