Coder’s Guide to Competitive Programming

Computer Science is a huge and rapidly expanding field nowadays. Many people (and probably you) are drawn to this area by high industrial demand and consequently high salaries. However, a plenty of time and effort should be devoted to learning to become a professional in this field, most of it building the foundation by learning Mathematics and Computer Science fundamentals. Many actual software engineers argue that they never use much of it in their day-to-day work, and therefore question the necessity of learning all of that. Nevertheless, many employers tend to use algorithmic and mathematical problems as interview tasks, especially software giants like Google or Facebook. While this might be a good screening tool for the IT monsters since they tend to build more sophisticated systems, many other companies, in my opinion, are mindlessly repeating their older brothers with no clear purpose. Nevertheless, the fact is – if you want to work as a software engineer, you not only need to have experience and knowledge relevant to your specific field of choice, you should as well be comfortable with algorithms, data structures and college mathematics for Computer Science. This is where competitive programming comes in.

What is competitive programming? In English, the term sounds totally fine, while in Russian it is almost like “Sports Programming”, which is a cause of countless jokes from those who are unaware of it. It is obviously about competitions, but, surprisingly, it is not really about programming. The most vital parts of competitive programming are Mathematics and Computer Science. The Mathematics part includes geometry, simple calculus, discrete mathematics, graph theory, combinatorics and number theory. It is worth noting that the hardest problems require knowledge of the advanced topics from the above fields, which are usually not taught in undergraduate courses, e.g. I have never seen the Fenwick tree in an algorithms course, while it is needed in some problems. The Computer Science part is based on a variety of algorithms, data structures, and, of course, knowledge of some programming language. It is worth noting that in order to succeed in competitions, you will need to have very deep understanding of those concepts and be able to implement them in minutes. That requires years of study and practice, and should rarely be the primary goal of a participant.

There are team and individual competitions. The former are usually more seldom and of greater significance, so they are mostly conducted on site, while the latter take place pretty often (up to several times a week) and do not last very long. Let me first describe the team competitions – the most significant of them is the Association for Computing Machinery International Collegiate Programming Contest (ACM ICPC), which is a competition for college students where teams of three students compete in solving problems in a limited time. There are usually about ten problems and the teams are given 5 hours to solve them. Depending on the region and the stage of the competition (be it quarterfinals or finals), the complexity of the problems varies greatly; the hardest ones touching the bleeding edge of today’s Computer Science. This competition is not for the beginners, and could be used for practice and fun, because winning it at any stage is very tough. However, if your team has made it to the finals, you are almost guaranteed to have your ticket to Google. Other team competitions are sometimes conducted by universities or large software companies. They have their own prizes and winning them is quite prestigious too. The individual competitions are aimed for anyone, and they can be used for practice because of their frequency. Their duration varies from an hour and more, and the complexity of the problems is usually more accessible for beginners. Those competitions are just a way to practice what you have learned in a competitive environment, which many people find more interesting than just solving problems. Some of these competitions have sponsors and prizes, which makes them even more interesting for the participants.

Sounds interesting? Yeah, everyone wants to work for Google! So how to get started? I might have scared you with the complexity involved, but it actually takes nothing to get started with competitive programming. Even if you do not know any programming language, you can catch up on the basics for example, on Hackerrank. Some platforms support a variety of languages, but the most widespread ones are Java, Python and C++, since they have good facilities for the tasks. However, you might experience problems with Python on some tasks because of its performance. Basically, the problem has description, format of input and output data, and usually some examples. In order to solve it, you need to write a program that will give correct output on a large, thoroughly compiled test suite and will do that in a restricted amount of time (most frequently, 1 or 2 seconds). You need to analyze the problem, come up with correct and efficient solution and implement it as fast as possible. The introductory problems do not require any special knowledge, and are easily solvable even without programming knowledge. Once you have practiced enough, you will want to switch to harder problems, which require  special knowledge, which is gradually growing as you go deeper. You can usually learn it from the website itself, or from external sources.

The competitive programming sites I recommend are Hackerrank, CodeChef and Codeforces. There are many more, and most of them are good. I personally use Hackerrank and Codeforces, and I think the former is a great choice for beginners, since you can both learn the topics and solve problems at the same place. Codeforces has a great community, a lot of blog posts describing advanced techniques, large problem archive and regular competitions, so I definitely recommend this one. The great source for learning specific topics is GeeksforGeeks, you have probably seen it while googling something. If you speak Russian (or are not afraid of decrypting google-translated text), you could use e-maxx, which has almost everything a competitive programmer would need. You could also take an online course on algorithms on Coursera or any other learning platform, and use problems for practice. It is a good idea to find someone to learn together, because topics get tough at times, so you could motivate each other. Even if you are stuck and despaired, there is usually an editorial published, if not, you always could ask help from a great community these websites have, you will definitely get help (I always did).

Solve problems, participate in competitions, learn algorithms and data structures and master your problem-solving skills! That will prepare you for tedious interviews and will benefit your career. Not to mention the satisfaction when you finally solve a hard problem or raise your rating after the contest. Good luck!

Leave a Reply

Your email address will not be published. Required fields are marked *