World Champions - about sports programming

DataArt has long been friends with the ITMO team in sports programming and helps it. This summer, Ilya Zban, Ivan Belonogov and Vladimir Smykalov came to our St. Petersburg development center. World champions in 2017 talked about how programmers compete with each other, training camps, favorite tasks and the strongest rivals.

Programming Olympiad

The main competition of programmers - the International Student Olympiad under the auspices of ACM (ACM-ICPC, or simply ICPC) - has been taking place since the 1970s, and took shape in 1989 in the form close to today. The Olympiad is intended for students and graduate students, with a rare exception to the competition does not allow programmers older than 24 years. In addition, one can only experience strength in the final twice, and only five times are allowed to participate in regional selections. In the early stages, passing around the world, thousands of teams compete. About a hundred of the best reach the final.
')

Fundamental rules

Teams consist of three people, while at the disposal of each team - only one computer. Before the start of the competition, all are given envelopes with algorithmic or mathematical tasks - from eight to 13 pieces - which need to be solved in five hours. The solution of the problem is a program that reads a text query and issues a text response. For verification, the decision is run on about a hundred tests prepared by the jury in advance — it is recognized as true only if the answer is correct in each of the tests.

The ICPC rules are very clearly stated in the video released for the Ural Programming Championship - one of the primary stages of selection for the Olympics. They are the same for all regions and since 2013 have remained unchanged.

Languages ​​and environment

In the final of 2017, it was possible to use the languages ​​Java, C ++ and Python. However, it is clear that Python is not very fast in principle - the jury did not guarantee that it would be possible to pass the task on it. However, it provided guarantees that they have solutions written in these languages ​​that pass all tests.

At different competitions, the set of languages ​​may be different. For example, on the online Codeforces platform, about 20 languages ​​are allowed: from C ++ and Java to Haskell and Perl.

Most teams in the finals write in C ++ , because speed comes to the fore. As a development environment, many teams use VIM (in it, for example, Ivan and Ilya worked) or Gina (Vladimir worked in it). Those who still write in Java, as a rule, use an environment like Eclipse, since writing in Java without an autocomplete is much more difficult.

In the near future, we can expect changes, since the finals will now be sponsored by JetBrains (20 years to the end of May 2017, the ICPC sponsor was IBM). This means that the products of the sponsor will appear on them: IDEA for Java and CLion for C ++. Perhaps after this command will begin to widely use debuggers, although so far more often cope without them.

Evolution of tasks

In the early 2000s, brute-force tasks with small restrictions prevailed, now there are more tasks on data structures. At the same time, there are several rather separate schools of sports programming in the world: if in Poland they like ideological, often mathematical, tasks, in China they prefer complex technical ones, where they have to write a lot of code, for example, to consider combinatorics.

The goal is always to come up with and implement a solution that works quickly. Any task can be somehow solved, for example, by writing a program that simply goes through all possible options. But in recent years, tasks that involve writing enumeration are practically not encountered.

There are time and memory limitations; however, in practice, problems with the fact that the solution uses too much memory occur infrequently. The time limit for each test is usually from one to three seconds depending on the task - this is also indicated in the condition.

Examples of tasks

Tasks are different: on graphs, lines, geometry, etc. Suppose, calculate the shortest path between cities on the map. Or to build the longest runway on the island, presented in the form of a nonconvex polygon. The task may be a comparison of texts - the search for the largest common substring for a couple of lines.



Another format is interactive tasks where you are offered to play some game with a system written by a jury. In one of the semifinals, it was necessary to write a program that in 90% of cases could outperform the proposed algorithm in tic-tac-toe. Challenges from past finals, including the last one, can be viewed here .

Decision process

Basically, team members sort out sheets with conditions depending on personal preferences: someone loves tasks for lines more, someone for geometry. In general, individual work here prevails over the team.

The first thing you need to come up with an algorithm for solving one of the problems. Sometimes the author of the decision discusses it with the team to make sure that the solution is mathematically correct. After that, the author sits down to write code - the other two participants at this time continue to think about the solutions of the remaining problems. When the code is written, it can be checked on test examples, which are usually attached to the condition, and sent to the system for evaluation. Since computer time is limited (we recall that the participants have only one computer), a printer is always present at the competitions: if the solution does not work, someone — usually its author — looks for errors by printing the code on paper.

Code Features

On the one hand, people involved in sports programming can write code quickly and clearly, and under stressful conditions. On the other hand, they are often criticized for the fact that this code contains incomprehensible variables and is difficult to read. In the code that is written at competitions, there are really no long clear names for the variables - after all, it will not have to be supported in a year. However, at a high level, this problem is not so acute, since the code still needs to be understood by teammates.

Another feature of sports programming is that the test system does not evaluate the release of memory - the solution works only a few seconds.

Algorithms

We know quite a lot of algorithms, use different data structures: a segment tree, a Fenwick tree, a Cartesian tree, etc. Sometimes a balanced search tree has to be written on its own, modifying it in parallel so that it reads the information determined by the condition of the problem. For example, in C ++ there is a set structure that can support a set of numbers and, for example, find the following. The task may require to find not the next number, but the sum of all numbers less than or equal to the given one. Standard structures cannot do this.

You cannot bring any code fragments with you, but at the World Championships it is allowed to use the so-called team reference - a set of algorithms printed on paper. Although we can write a lot on the fly, this year we spent a lot of time preparing it - we tested more complex algorithms. But in the end the records were not used at all.

The amount of code does not directly affect the final assessment, another thing is that it is difficult to write 1000 lines in the allotted time. And having come up with a beautiful concise decision, you can meet just 10-15 minutes. It is under the search for such elegant paths that most of the conditions are sharpened: the average solution volume is 100-200 lines of code, although in some cases it can go up to 300. In ordinary life, 300 lines are not too many, but here you have only five hours solution of all problems. It is necessary to write quickly, and if an error is made in three hundred lines - the task will not work, it means that all the time for its solution will be simply lost. In addition, the longer the code, the more difficult it is to find an error in the printed version.

Other tournaments and training

Cash prizes are far from the main motivation of participants in tournaments. In the photo: Ivan Belonogov and Ilya Zban - winners of the VK Cup 2015 (source - Ivan Belonogov's page). In 2017, the VK Champion's third member Vladimir Smykalov became the winner of the VK Cup.

We constantly participate in individual tournaments - there are a lot of them. For example, competitions on the Russian Codeforces site are regularly collected by several thousand people, of which Russians are usually about 20%. The standard tour here consists of five algorithmic tasks that need to be solved in two hours. The most important thing in the community that has developed around this resource is a personal rating calculated according to the Elo system, as in chess. Successfully speaking at tournaments, programmers get points - a certain amount of them automatically changes the color of the nickname. Those with red nicknames receive not only requests for help, but also offers from employers. And most importantly, like any champion athletes, they are universally respected - for many participants, a “red nickname” in itself serves as a sufficient incentive to fight.


Steeper than red nicks, only red nicks with the first black letter. On July 13, there were eight Russians in the twenty best on Codeforces, two Ukrainians, Polish and Chinese, and one each from Switzerland, Australia, Korea, USA, Taiwan and Belarus. At the same time, the Belarusian programmer now heads the rating, although in principle the rearrangements in the table occur constantly.

Major competitions are held Mail.ru , Yandex , Facebook , Google and other companies. For example, in the first round of the current Google Code Jam tournament, 20,000 people participated. Thousands of the best were branded T-shirts, 25 - will go to the finals, which this year will be held in Dublin.

In addition to Google Code Jam, Google held another tournament - Hash Code , the final of which was held at the company's head office. The participants, in particular, were given out plans for buildings that needed to be covered as much as possible with a network of Wi-Fi-points, using as few routers and wires as possible. The optimal solution for such a problem does not exist, but it is possible to solve it better than others.


One of the buildings in which the organizers of Google Hash Code offered to place routers was the Paris Grand Opera.

A separate type of competition is the AI Cup , where you need to write an artificial intelligence program that can play against the original program provided by the organizers in the form of a library. Games are created specifically for tournaments, i.e. it’s basically impossible to play hands with them. But the scripts are selected so that writing strategies for them was interesting.


This year the game was similar to the modern MOBA: the solution was to manage a team of five wizards, ensuring the exchange of commands between them using code words.

Such competitions are constantly held on the French site CodinGame . And it is nice that in AI tournaments we achieve good results, taking places in the first two twenties with no training at all. Still, in sports programming, the main skill is to sit down, think and write code.

The Topcoder platform sometimes holds marathon competitions that can last several weeks. There are several tournaments, for example, Deadline24 or Challenge24 , the final part of which lasts a day. They are selected on them, solving ordinary algorithmic problems, and in the final here you need to create strategies for managing the game. At this tournament, it seemed most effective for us to write the code for the first 12 hours, and to fix errors after a break for sleep.

Online platforms allow you to keep yourself in shape, otherwise the skill of solving problems is lost very quickly. But they are interesting, of course, not only as training. Competitions are always drive and emotions, which without them can be sorely missed.

Trainings

Almost all of our workouts last for five hours, as well as the most important competitions. Usually we just solve problems from one of the past tournaments. We practically do not learn new algorithms, because we know quite a lot of them. In the end, what is expected of us is not the knowledge of complex data structures, but the ability to quickly come up with a solution. Therefore, special books do not really help us. It is much more effective to read individual articles or listen to lectures on specific topics on the Internet.

Several times a year are held fees, which are going to teams from different countries. In particular, strong Poles came to Petrozavodsk this year, and programmers from China and Australia came to MIPT in Dolgoprudny. At the training camp, we have been dismantling new, specially prepared tasks for a week and a half, including those brought by other teams.

Combining sports programming with studies was difficult in the first two years - in the third and fourth courses it became easier, because there were less classes at the university. In principle, at this time many students are already starting to work. We do not have time for full-fledged work yet, although of course we get offers after tournaments.

Rivals

The strongest teams consistently collect universities from Russia, Poland, China, Korea and Japan. At times, successful teams are selected from one of the Western European or American universities, but in general there are obviously less interested in sports programming. Eastern Europe and Asia dominate individual tournaments, for example, Codeforces . In terms of the number of participants in many competitions, India is constantly the first, but most often the results of their representatives show not the highest. Although in solving design problems, Indians are just strong - this is manifested in special tournaments at Topcoder .


US school team season 2017/18. Success in sports programming in America is mainly achieved by young people with Asian roots.

The most mysterious rivals seem to be programmers from North Korea, who, under conditions of limited access to the Internet, still train and often perform fairly well. However, this year they did not come to the finals in the United States, and they had a reputation as cheaters for Codeforces. In particular, the North Korean participants of online tournaments accused that with a single account code is clearly written by different people. And this is strictly prohibited by the rules.


This year, only one team from Western Europe - the students of the Royal Institute of Technology from Stockholm - ranked in the top ten at the international Olympics.

The successes of Russia look quite understandable, because here there is a very strong mathematical school, and the current crowd of olympiads, ready to help beginners. In Russia, in addition to ITMO, very strong teams represent St. Petersburg State University (last year’s champions), Moscow State University, Moscow Fiztekh, universities of Ekaterinburg and Saratov, although from time to time other universities can also assemble good teams.


There is another ITMO team in the photo: Artem Vasilyev and Boris Minaev and Gennady Korotkevich - 2015 World Champions. The cups of the International Programming Olympiad are not transferable - now there are already seven in ITMO.