Are competitive programming and algorithm courses linked together

Competitive programming - Competitive programming

Competitive programming is a thought sport, usually played over the Internet or a local network, in which participants take part who try to program according to the specified specifications. Participants are registered as Sports programmer called . Competitive programming is recognized and supported by several multinational software and internet companies such as Google and Facebook. There are several organizations that hold programming competitions on a regular basis.

In a programming contest, the host generally presents participants with a series of logical or mathematical problems, also known as puzzles (the number of which can vary from tens of thousands to several thousand), and participants are required to write computer programs that will solve each problem can. The assessment is mainly based on the number of problems solved and the time it takes to write successful solutions, but may include other factors (quality of the output produced, execution time, program size, etc.).

history

One of the oldest known competitions is the ICPC, which was founded in the 1970s and expanded to 88 countries in its 2011 edition.

From 1990 to 1994 Owen Astrachan, Vivek Khera and David Kotz held one of the first distributed, Internet-based programming competitions inspired by ICPC.

Interest in competitive programs has grown significantly since 2000 and is strongly linked to the growth of the Internet, which makes it easier to hold international online competitions and eliminates geographic problems.

overview

The goal of competitive programming is to write source code of computer programs capable of solving given problems. The vast majority of problems encountered in programming competitions are mathematical or logical in nature. Typical such tasks fall into 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.

Regardless of the problem category, the process of problem solving can be broken down into two major steps: creating an efficient algorithm and implementing the algorithm in an appropriate programming language (allowable programming languages ​​vary from competition to competition). These are the two most commonly tested skills in programming competitions.

In most competitions, the evaluation is done automatically by host machines commonly known as judges. Each solution submitted by a participant is examined by the judge using a series of (usually secret) test cases. Normally, competition problems have an all-or-none marking system, which means that a solution will only be "accepted" if it gives satisfactory results in all test cases carried out by the judge and is otherwise rejected. However, some competition issues may allow partial assessment, depending on the number of test cases passed, the quality of the results, or other set criteria. For some other competitions, the entrant only needs to submit the output that matches the input data provided. In this case, the judge only has to analyze the submitted output data.

Online judges are online environments where tests are held. Online judges have leaderboards that show users with the largest number of accepted solutions and / or the shortest execution time for a given problem.

Notable competitions

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

Short term

In most of the above competitions, competitions are usually organized in several rounds because the number of participants is quite large. They usually require online participation in all rounds except the last, which requires on-site participation. A special exception is IEEEXtreme, an annual virtual 24-hour programming competition. The top performers at IOI and ICPC receive gold, silver and bronze medals, while the top finishers at the other competitions receive cash prizes. Reaching the top positions in the point tables of such competitions can also arouse the interest of recruiters from software and internet companies.

Long term

Artificial intelligence and machine learning

  • Kaggle - Machine Learning Competitions.
  • CodeCup - AI competition for board games that has been held annually since 2003. The rules of the game will be published in September and the final round will take place in January.
  • Google AI Challenge - bi-annual competitions for students that ran from 2009 to 2011
  • Halite - An AI programming challenge sponsored by Two Sigma, Cornell Tech, and Google
  • Russian AI Cup opens artificial intelligence programming competition

Competitions focusing on open source technologies

  • The list may not be complete
Name of the competition Main sponsor description Running since Ordinary time Next cycle of use status
Multi-agent programming competition Clausthal University of Technology in connection with agent-oriented workshops Annual international programming competition to promote research in the field of development and programming of multi-agent systems. 2005 Sept September 2011 active
Google Summer of Code Google Inc. An annual program where Google awards scholarships to hundreds of students who successfully complete a requested free software / open source coding project during the summer. 2005 Mar-Aug March 23rd - April 3rd active
Google Open Participation Contest Google Inc. A competition organized by Google in 2007/08 and aimed at high school students. The competition aims to encourage students to participate in open source projects. 2007 Nov-Feb Unknown Unknown

Online competition and training resources

The programming community around the world has created and maintained several Internet resources devoted to competitive programming. They offer stand-alone competitions with or without smaller prizes. The past problem archives are also a popular resource for training in competitive programming. These include:

Surname description website
CodeChef Managed by the Unacademy, it hosts a 10-day competition and a few short competitions (one IOI style called Lunchtime and another ICPC style called Cook-Off) every month, and provides a platform for educational institutions to host competitions for free. The two best winners of the long competition win cash prizes, while the ten best in the world receive a t-shirt. www .codechef .com
CodeCup Annual international board game AI programming competition organized by the Dutch Computer Science Olympiad since 2003. Codecup .nl
Code forces Russian resource managed by ITMO University and mostly offering frequent (up to two per week) short competitions. Special features: All solutions are open source, the possibility of checking the correctness of the solutions of other participants during the "hacking phase", virtual competitions, training courses, etc. codeforces .com
CodinGame Puzzles (increasing difficulty), code golf. Regularly organizes online competitions (AI challenges, optimization problems). www .codingame .com
CodeWizardsHQ Organizes the annual free Code Challenge for children between 8 and 18 years of age. The challenge is divided into two parts: 21 Python-based questions and a boss level that requires Python or Javascript code to pass. www .codewizardshq .com / challenge
HackerEarth Based in Bangalore, India, the company runs online competitions to provide solutions for hiring assessment. www .hackerearth .com
HackerRank HackerRank offers programming problems in various areas of computer science. It also includes annual code sprints that can be used to connect the coders and Silicon Valley startups. hackerrank .com
Neps Academy The Neps Academy is a platform that offers both online judging and programming courses to help people start programming and train them for programming competitions. It is a platform based in Brazil and has all the problems of the previous Brazilian Olympiad in Computer Science in Portuguese and English (as well as many more problems, currently around 900). neps .academy
Euler project Large collection of computational math problems (that is, not directly related to programming, but often requires programming knowledge to solve). projecteuler .net
Topcoder American resource and company that organizes competitions and also offers industrial problems as a type of freelance job; It offers dozens of short competitions and several long ones ("marathons") each year. Special feature - Participants have the opportunity to check the correctness of the solutions of other participants after the coding phase and before the final automatic test (so-called "challenge phase"). www .topcoder .com
UVa online judge Contains over 4,500 problems to practice on. Regularly organizes online competitions. It opened in 1995 and is one of the oldest websites of its kind. onlinejudge .org
SPOJ The Polish online judging system presents many problems for training and provides a platform for other organizers to host their programming competitions. www .spoj .com
Open Kattis Public version of the Kattis Contest Management System with an archive of over 2600 problems. Kattis was designed to support computer science courses, but it is also used to host prestigious competitions such as the ICPC World Finals. open .kattis .com
AtCoder AtCoder, based in Japan, has weekly online programming competitions. The competitions are offered in Japanese and English.

As of 2020, it will be one of the most popular platforms of its kind.

atcoder .jp
Caribbean Online Judge Spanish resource maintained by the University of Information Science. Contains over 3,000 problems to practice on. Online competitions are also held here on a regular basis. coj .uci .cu

Use and criticism

Participating in programming competitions can increase students' enthusiasm for computer science studies. Skills acquired in ICPC-like programming competitions also improve career prospects as they help pass the "technical interviews" that often require candidates to solve complex programming and algorithmic problems on-site.

There has also been criticism of competitive programming, especially from professional software developers. A critical point is that many quick programming competitions instill bad programming habits and code styles (such as unnecessary use of macros, lack of OOP abstraction and comments, use of short variable names, etc.) to competitors. Because programming competitions like ICPC and IOI only offer small algorithmic puzzles with relatively short solutions, they don't necessarily convey 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 a long period of time Periods. Peter Norvig stated that based on the data available, the winner of programming contests negatively correlated with a programmer's performance at Google (although contest winners had higher chances of being hired).

Another feeling is that high-level programmers should invest their time solving real-world problems rather than "wasting" their time in overly competitive solving problems with known solutions.

literature

  • Halim, S., Halim, F. (2013). Competitive Programming 3: The new lower bound of programming competitions . Lulu.
  • Laaksonen, A. (2017). Competitive Programming Guide (Bachelor subjects in computer science). Cham: Springer International Publishing.

See also

References

External links

Open source project for the implementation of competitions