Competitive programming combines two topics: the design of algorithms and the implementation of algorithms.
Design of Algorithms. The core of competitive programming is about inventing efficient algorithms that solve well-defined computational problems. The design of algorithms requires problem-solving and mathematical skills. Often a solution to a problem is a combination of well-known methods and new insights.
Implementation of Algorithms. In competitive programming, the solutions to problems are evaluated by testing an implemented algorithm using a set of test cases. Thus, after coming up with an algorithm that solves the problem, the next step is to correctly implement it, which requires good programming skills. Competitive programming greatly differs from traditional software engineering: Programs are short (usually at most some hundreds of lines), they should be written quickly, and it is not needed to maintain them after the contest.
Competitive programming has its roots in the scientific study of algorithms. However, while a computer scientist writes a proof to show that their algorithm works, a competitive programmer implements their algorithm and submits it to a contest system. Then, the algorithm is tested using a set of test cases, and if it passes all of them, it is accepted. This is an essential element in competitive programming, because it provides a way to automatically get strong evidence that an algorithm works. In fact, competitive programming has proved to be an excellent way to learn algorithms, because it encourages to design algorithms that really work, instead of sketching ideas that may work or not.
Another benefit of competitive programming is that contest problems require thinking. In particular, there are no spoilers in problem statements. This is actually a severe problem in many algorithms courses. You are given a nice problem to solve, but then the last sentence says, for example: “Hint: modify Dijkstra’s algorithm to solve the problem.” After reading this, there is not much thinking needed, because you already know how to solve the problem. This never happens in competitive programming. Instead, you have a full set of tools available, and you have to figure out yourself which of them to use.
Solving competitive programming problems also improves one’s programming and debugging skills. Typically, a solution is awarded points only if it correctly solves all test cases, so a successful competitive programmer has to be able to implement programs that do not have bugs. This is a valuable skill in software engineering, and it is not a coincidence that IT companies are interested in people who have background in competitive programming.
Next, there will be posts considering solutions of most common problems used to practice competitive programming — that is known as CSES Problem Set.
