Us, humanity, have for centuries believed that we are the smartest thing on Earth. No other creature or mechanism could even approach our intellectual abilities. Recently, however, things started to change:
- first, there was a defeat in 1997 of world chess champion Garry Kasparov by Deep Blue chess program
- board game Go (considered one of the most complex games) held until 2016, when Go grandmaster Lee Sedol was defeated by AlphaGo program
- 2017 — professional poker players dominated by Artificial Intelligence
- 2018 — Dota 2 video game veterans steamrolled by AI team
- soon, AI may make the steering wheels and pedals in our cars obsolete (and all the drivers, as well)
It looks like human intelligence is getting dominated, obsolete and irrelevant at an ever-increasing pace. So, is there any hope remaining? Are there any areas where human intelligence cannot be surpassed by machines (at least in the foreseeable future)?
Turns out, there is. In this post, I will talk about one such area. The area is Competitive Programming. It is a niche area, barely heard of even by the majority of people in Computer Science / IT industry. A very dull definition from Wikipedia says:
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.
I believe this definition begs for a further explanation. Basically, Competitive Programming is an activity that involves participation in competitions of solving algorithmic challenges, by writing code. The solution is a short program (tens of lines of code, sometimes a hundred or more) that reads the input data, computes the solution to the problem defined in the problem statement, and outputs the result.
Contestants can choose from multiple programming languages — their availability depends on the platform that is hosting the competition. Because of high-performance requirements, compiled languages dominate (C++ and Java being the most popular ones).
The difficulty of those challenges varies from simple implementation tasks to advanced algorithms and data structures. In some cases, knowledge of number theory, geometry, probability theory also matters. Usually, several such problems are to be solved during one round which typically lasts around two hours. And it is common to see the easiest problems solved in 2–3 minutes (including reading the problem statement, coding the solution and submitting it). In some competitions, there is an option to review your opponent's code. And if you see a bug in it, hack it by submitting an input that exposes the bug, for additional points!
In order to succeed, contestants need to focus on the correctness of their solutions, their performance (it has to be optimal in terms of big O notation), and implementation speed. In many cases, it is only after the end of the round when you find out that your solution has failed (being either incorrect, or too slow). This completely defeats the habit of coding by trial and error that is so common in the industry — you have to think before you code! Creativity, general problem-solving skills, grace under pressure and brain endurance help a lot. Also, debugging skills — but if you have to spend time debugging, you are already in trouble!
The benefit of Competitive Programming is the development of all the skills mentioned above (possibly taking them to extreme levels). Some competitions award prizes (most common prizes being rarity T-shirts).
Many people practice Competitive Programming simply because they enjoy it. Also, many participants are attracted by the fact that top tech companies use those competitions to find and recruit top talent. Also, the skills developed can really help to crack any technical job interview.
Some competitions are annual events consisting of multiple rounds, for example, Google Code Jam, or Facebook Hacker Cup. Tens of thousands of contestants start from the Qualification Round, and after a few rounds, the best ones remaining are invited to the finals held in one of the offices of organising companies.
Also, there are websites hosting regular competitions (best known among them are codeforces.com and topcoder.com). Usually, they host one or more rounds per week. There are separate divisions for beginners (with simpler problems) and for experienced participants. Each participant has a rating that reflects their performance. They can see their rating graphs and compare their progress against other competitors over the time. Also, there’s a thriving community, with blogs and discussions.
Surely, there is no good explanation without an example! This is an example of a solution to a rather simple problem, written in Scala (the first few lines are just a boilerplate from the template):
It solves the problem A — The King’s Race from Lyft Level 5 Challenge 2018 that was hosted on Codeforces. A short description: you have a chessboard of size NxN with two kings placed in the opposite corners. Given the coordinates of some square (X, Y), you have to tell which king would reach that square first. Unlike in real chess, the kings can move without affecting each other. The tricky part is the size of the board (N) — it can be up to 10^18, so good luck with any brute force approaches…
2 minutes 48 seconds were spent on the whole process of reading and understanding the problem statement, coding the solution, testing and submitting it. And there were a few contestants who managed to do it in even less than 2 minutes!
In the begging of this post, I’ve made a bold claim that AI will not be able to challenge humans in Competitive Programming any time soon. What makes me think so? It requires both creativity and a very deep level of abstract thinking (correctness, complexity). It does not have a limited set of moves that can be attacked with brute force (like chess). Pattern recognition would hardly help — every problem is unique, and there is no way to interpolate between them because maintaining precision is critical. Solution space is enormous (all valid programs that fit in, say, few hundred lines of code). Then, there’s the Halting problem — there does not exist a way to determine whether the program will even finish running. Then, there was this attempt to train machines to solve Competitive Programming problems. All in all, I strongly believe that the human brain is far superior in this area than any current technology AI.
And for the final thought, I believe that in some regard, the brain is like a muscle — if you don’t exercise it to the limit, it degrades. Competitive Programming can give you just that exercise your brain needs. And don’t think that you are covered on this by your daily work — I would say, less than 1% of the typical work of a software developer comes close to it in terms of intensity. You don’t have to take my word for it — just try and see for yourself!