World Champions - About Sports Programming / DataArt Blog

DataArt has long been friends with and helps the ITMO sports programming team. This summer, Ilya Zban, Ivan Belonogov and Vladimir Smykalov came to visit our development center in St. Petersburg. The 2017 world champions talked about exactly how programmers compete with each other, about training camps, favorite tasks and 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 held since the 1970s, and in a form close to today, took shape in 1989. The Olympiad is intended for students and graduate students, with rare exceptions, programmers older than 24 years old are not allowed to compete. In addition, you can only test your strength in the final twice, and you can participate in regional selections only five times. Thousands of teams compete in the early stages throughout the world. About a hundred of the best reach the finals.

Basic Rules

Teams consist of three people, while at the disposal of each team - only one computer. Before the start of the competition, everyone will be given envelopes with problems of an algorithmic or mathematical nature - from eight to 13 pieces - which must be solved in five hours. The solution to the problem is a program that reads a text request and produces a text response. To test, the solution 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.

ICPC rules are very clearly stated in the video released for the Urals programming championship - one of the primary stages of selection for the Olympics. They are the same for all regions and since 2013 remained unchanged.

Languages ​​and Environment

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

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

Most teams in finals write in C ++because speed comes to the fore. As a development environment, many teams use VIM (for example, Ivan and Ilya worked in it) 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.

Changes can be expected in the near future, since the finals will now be sponsored by JetBrains (for 20 years until the end of May 2017, IBM was the sponsor of ICPC). This means that sponsor products will also appear on them: IDEA for Java and CLion for C ++. Perhaps after this, the teams will begin to widely use debuggers, although for now they are more likely to manage without them.

Task evolution

In the early 2000s brute force tasks prevailed with slight restrictions; now there are more tasks on data structures. At the same time, there are several quite 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 you have to write a lot of code, for example, consider combinatorics.

The goal is always to come up with and implement a solution that works quickly. Any problem can be solved at least somehow, for example, by writing a program that simply goes through all possible options. But in recent years, tasks involving writing brute force, almost never occur.

There are restrictions on time and memory, however, in practice, problems with the fact that the solution uses too much memory arise 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

The tasks are different: on graphs, lines, geometry, etc. Suppose, calculate the shortest path between cities on a map. Or build the longest possible runway on the island, presented in the form of a non-convex polygon. The task may be to compare the texts - finding the largest common substring for a pair of strings.



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

Decision process

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

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

Code Features

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

Another feature of sports programming is that the memory system is not evaluated in any way by the test system - the solution only works for a few seconds.

Algorithms

We know quite a lot of algorithms, we use different data structures: a segment tree, a Fenwick tree, a Cartesian tree, etc. Sometimes you have to write a balanced search tree yourself, 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 many numbers and, for example, find the following. The task, however, may require finding not the next number, but the sum of all numbers less than or equal to a given one. It will not work out with standard structures.

You cannot bring any fragments of codes with you, but at the World Cup you are 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 recordings were not used at all.

The amount of code does not directly affect the final grade, it’s another matter that writing 1000 lines in the allotted time is difficult. And having come up with a beautiful concise solution, you can keep within just 10-15 minutes. It is under the search for such elegant paths that most of the conditions are sharpened: the average volume of a solution is 100-200 lines of code, although in some cases it can reach 300. In ordinary life, 300 lines are not so many, but here you have only five hours to the solution to all problems. You need to write quickly, and if a mistake is made in three hundred lines, the task will not work, which means that all the time to solve it will simply be 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 for tournament participants. In the photo: Ivan Belonogov and Ilya Zban - winners of the VK Cup 2015 (source - Ivan Belonogov page). In 2017, Vladimir Smykalov, the third member of the ITMO champion team, 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 site Codeforcesseveral thousand people are regularly gathered, of which about 20% are usually Russians. The standard tour here consists of five algorithmic problems 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, like in chess. Successfully speaking at tournaments, programmers get points - a certain number of them automatically changes the nickname color. 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, the "red nick" in itself serves as a sufficient incentive to fight.


Steeper than red nicks, only red nicks with the first black letter. On July 13, the top twenty on Codeforces included eight Russians, two Ukrainians, Poles and Chinese, and one representative from Switzerland, Australia, Korea, the USA, Taiwan and Belarus each. At the same time, the Belarusian programmer is now leading the rating, although in principle, permutations in the table occur constantly.

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

In addition to the Google Code Jam, Google held another tournament -Hash Code , the final of which was held at the head office of the company. Participants, in particular, were given building plans that needed to be covered as much as possible with a network of Wi-Fi points, using as few routers and wires as possible. There is no optimal solution to such a problem, but it is, of course, possible to solve it better than others.


One of the buildings in which the organizers of the Google Hash Code suggested arranging routers was the Paris Grand Opera.

A separate type of competition is 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, that is, you can’t play them with your hands in principle. But the scripts are chosen so that writing strategies for them is interesting.


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

Such competitions are constantly held on the French site CodinGame . And it's nice that in AI tournaments we achieve good results, taking places in the first two twenty with a complete lack of training. Still, in sports programming, the main skill is to sit down, think, and write code.

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

Online platforms allow you to keep fit, otherwise the task-solving skill 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.

Training

Almost all of our workouts last five hours, as do 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 a lot of them. In the end, what is expected of us is not 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, training camps are held, for which teams from different countries gather. 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 analyze one and a half weeks new, specially prepared tasks, including those brought by other teams.

Combining sports programming with study was difficult in the first two years - it became easier in the third and fourth courses, since lesson at the university. In principle, at this time, many students are already starting to work. We do not have time for a full-fledged work, although we, of course, receive 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 less interested in sports programming. Eastern Europe and Asia dominate individual tournaments, such as Codeforces . By the number of participants in many competitions, India is constantly the first, but most often the results of their representatives are not the highest. Although Indians are just strong at solving design problems - this is manifested in special tournaments at Topcoder .


USA school team of the 2017/18 season. Success in sports programming in America is mainly achieved by young people with Asian backgrounds.

The most mysterious rivals seem to be programmers from North Korea, who, in conditions of limited access to the Internet, still train and often perform pretty well. True, this year they did not come to the finals in the USA, and at Codeforces they had a reputation as cheaters. In particular, North Korean participants in online tournaments were accused that clearly different people wrote the code from one account. 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 - entered the top ten at the International Olympics.

The successes of Russia seem quite understandable, because here - and a very strong mathematical school, and the established party of the Olympiad, ready to help beginners. In Russia, in addition to ITMO, very strong teams are represented by St. Petersburg State University (last year's champions), Moscow State University, Moscow Physics and Technology University, and the universities of Yekaterinburg and Saratov, although from time to time other universities also manage to assemble good teams.


Another ITMO team is pictured: Artyom Vasiliev and Boris Minaev and Gennady Korotkevich - 2015 world champions. Cups of the International Programming Olympiad are not transferable - now seven are already stored in ITMO.