Interview with the legend of sports programming Peter Mitrichev

They say that when he was born, Donald Knut himself glanced over to him. They say that when he was invited to work at Google, he rewrote the entire search algorithm 16 times in 15 minutes. They say that he is watching the progress of quantum computing with a smile, because at the sight of his number, they themselves factorize themselves from fear. But we know one thing for sure: Peter is the real god of sports programming.

• Winner of numerous championships, Peter won twice in TopCoder and twice ranked second in the ACM ICPC.
• In his spare time, Peter keeps a blog about regular contests “Algorithmic problems for dummies”: petr-mitrichev.blogspot.ru.
• Now Mitrichev works at Google, where he deals with search quality. Peter also helps in the preparation of competitions Google Code Jam.

Many people think that sports programmers are cool guys, real geeks, versed in algorithms and solving complex problems. But they also say that it is very difficult for them to apply themselves somewhere. This is true?

Sports programming and, in general, what we do at Olympiads, is really not the thing you can earn for a living. On the other hand, programming, like any other sport, is a development for a person. Thanks to him, a person becomes smarter, programs better, searches for errors in programs better. After such training it is easier to work and do other interesting things.
')
The algorithms are definitely applicable in the practice of the programmer, although at work I also met with algorithms that are more complicated than those that occur at olympiads. But at olympiads we are limited to algorithms that, roughly speaking, can be written in half an hour. Therefore, there is used in the tasks quite specific, limited set of algorithms. In real life, everything is just more ... extensive.

In what language did you write solutions for problems?

In Java. At school I wrote on Pascal, because I did not know anything more then. And then, when it was necessary to choose what to switch to, Java was closer to Pascal.
In a competition, you need to write a program in 20-30 minutes, and it should immediately work correctly. Therefore, it is very important that the language does not allow to plant bugs. C ++, which uses most, is different because it is quite easy to write the wrong program. You can accidentally forget something, assign the wrong type of variable, but it will somehow compile and work somehow. Most likely, not the way you expect.

In Java, if you make a mistake or typo, the program most likely simply does not compile. Here everything is stricter, as is the case with Pascal. It seemed to me more appropriate. The other side of the coin - Java programs often run one and a half times slower than C ++ programs. Sometimes these one and a half times are not enough for the program to fit into the condition of the problem.

Anyone can choose a programming language, right?

There are limitations. Of course, there are different competitions ... take Google Code Jam, for example. When we decided how best to do it, we figured out that we could work in any language. You download the input file with the task data to the computer, launch your program on the computer, and then send the result to the server. What compiler / interpreter you have on your computer is what you can use. The disadvantage of this system is that people have different computers. Someone computer is ten times more powerful than the other. Therefore, it is necessary to create tasks where the wrong solution differs from the correct one at least a hundred times in speed. So if a person has a computer ten times slower, the correct solution works for him, or the wrong solution still does not work on the computer ten times faster. Therefore, we need tasks with a large gap between the correct and the wrong decision on the speed of work.

On Topcoder, Codeforces and ACM, a standard system is used, where you send the source code and they run it on your server. Here you are limited by what they have on the server. Most participants, 70–80% use C ++, another 20% use Java, the remaining languages ​​are very small. It seems to me that such a cycle is new people who come to competitions, begin to communicate with other, older participants, they teach beginners what they can do. As a result, new people also begin to use the same languages. So these two languages ​​are not particularly suitable for competitions, it just happened historically.

That is, in life, all this is applicable? After all, it is certainly difficult to find a job in which this knowledge would be useful. Yes, you can go to Google or Yandex, but is it more difficult to come to a bank?

I think this is a very useful part of the skill, the part that is responsible for the ability to write a program from the first time, without errors, or find an error in the program of a friend. I myself did not work in a bank, but it seems to me that such skills would be useful there. Although, of course, the algorithms themselves are not really used in any work. But personally this background helps me a lot.



You probably had some special story, how did you get on Google?

Yes, there is no story, everything was the same as in others. Now I am engaged in a search (its general part, which does not depend on the country and language), but, unfortunately, I cannot tell anything about it, since it is a very confidential part.

Sports programming: “for” and “against”

Let me try to ask you a stupid question :). Why do you need to do sports programming, how do you think?

Everything is very simple here and looks like any other sport. You need to do this if you like it, if you enjoy it. This should not be an end in itself. You need to take sports programming as a way to have a good time, meet interesting people and so on.

And if you try to think of a reason, why not spend time on sports programming?

I think you need to be aware that this is not the most important thing in life. Have some other goals besides this one. If something starts to take absolutely your whole life, perhaps this is already a reason to think about how to at least take a break.

But what does practice say, is it possible, for example, to build a career around sports programming?

In Russia, there are several people who are professionally engaged in the preparation of new sports programmers - coaches. Andrei Stankevich, Misha Mirzayanov and others. All of them teach at universities, but a significant part of their working time is spent preparing students and pupils for programming competitions. For them, this is really a job and, one might say, a career.

Did you yourself think about this? Nowhere to participate in the jury or as a compiler of tasks?

I tried to teach schoolchildren in the 57th school, where he studied. I tried to prepare teams for olympiads. Now in Moscow this topic is very active - there are teams at Moscow State University, the Physics and Technology Institute, the Higher School of Economics. But with the teaching I somehow did not work out.
As for the contests, first of all I help to do tasks for Google Code Jam, for our competition. Plus I help with the ACM semi-final, which takes place in St. Petersburg. This is a selection among Russian and former USSR teams for the final.

Is it possible to earn at competitions? After all, for the victory give cash prizes.

Too little chance. One prize for ten thousand participants? .. I would not call it a salary. To count on this as the main source of income ... it seems to me, no chance.

But, as I said, there are many different competitions. The same Topcoder holds program development competitions. Suppose you need to develop a component for a program that does this. According to the results, they estimate who got what and the best use - the client buys this decision and pays the money to the one who made this decision. People who are engaged in this full time, as I understand it, earn pretty well.

Contests today

Tell me more, what are the current competitions, how is all this happening?

Today there are two types of contests. There are weekly, regular competitions. They are conducted by two main sites - TopCoder and Codeforces. Each contest takes one and a half to two hours. There the participants are given several tasks that need to be solved and send the program to the server. The organizers check if the program works.

Then the subtleties begin, for example, in both of these competitions there is still the opportunity to look for mistakes in the decisions of other people and get points for those found.
TopCoder is the oldest and most well-known site with weekly contests. They have the following rules. On the solution of three problems one hour and fifteen minutes are given.

Assignments are usually divided into very simple, medium and complex. The organizers are trying to pick them up so that, say, five people solve all the problems, one hundred people two, and all the rest decide at least one. Moreover, for each task it is important when you send it - the later, the less points you get. So those people are separated that solved the same number of tasks. Then the points are added up. The usual task is 250 points. Average 500. Difficult 1000. On average, people from the first places get a thousand and something points for a competition.

Then they take a break for five minutes and another fifteen minutes are set aside for others to find mistakes. You can open the solution of any person, for any task in your "room". A “room” is when people participating in a competition are randomly divided into groups of twenty people. Break into "rooms". You can open any decision of any person from your "room". If the solution seems wrong to you, then you can drive in the input data on which it will be wrong. And if it really gives the wrong answer, you get another 50 points for it. This, of course, is less than the cost of the task. But this is again done to separate people. The main points are still charged for solving problems, and not for finding errors.

After all this, the tasks are checked on tests prepared by the jury. If the task does not work, the person gets 0 points.
There is also a second site, Russian, - Codeforces. They have slightly different rules, but the format is approximately the same - two hours and several tasks. If you like, this format can be called entertaining, as opposed to student competitions that last for five hours.

But still there are large, annual contests?

Yes, except for the two described competitions, which take place weekly, there are many more annual competitions. Usually they are arranged like this: a certain large company (Google, Yandex, TopCoder, IBM) holds a competition with several stages of selection. The first stages are on the Internet. And the final stage is already held in a particular place where all the finalists will be taken. There are five to ten such competitions, but they are long, so some of them happen all the time.

All these competitions are individual?

Most competitions are now individual. Team competitions are mainly student competitions, the main one being the ACM ICPC. And other student competitions are also usually made commanding, because, roughly speaking, there is already a team there. It's easier to get people interested. Here veteran competitions are usually personal.

Almost all competitions have certain ratings, the most famous among TopCoder. What it is?

The weekly competitions have a rating like in chess, which is updated after each competition. Those who performed better, get a plus, who is worse - a minus. If you did not participate at all, the rating does not change. The system is built in such a way as to equalize people who are often and rarely. The pressure “you need to participate constantly” is not there. There are many people who are much older than me, they appear very rarely - once in two months - and still they have a good rating, because they continue to solve problems well.

Are you second in the TopCoder ranking?

Yes, in the first place is Gena Korotkevich, a very smart student from Gomel, now he is studying at ITMO. I recently had worse results on Codeforces, now I’m sixth or fifth. There, too, Gena in the first place.


Probably, playing online and offline is a completely different sensation and experience?

Of course. It seems to me that a very important positive side of sports programming is that all competitions end in an onsite round where all the best come together. Thanks to this, I met many cool people from around the world. In general, the main “prize” in such competitions, I think, is meeting people. You spend time with them, communicate, learn something new. It is very funny that people from other countries, who often speak English poorly, are nevertheless very easy to understand, because they have very similar interests.

In such competitions - with selections - usually more people participate than in regular ones. If a person has never participated anywhere, weekly competitions can be a problem. There are such tasks that a person can solve nothing and get upset. In competitions with selections, everything is usually simpler, at least in the early stages. Their main idea is to make everyone enjoy. Again, there is a tangible prize at the end - cash prizes for first places. Plus, a trip somewhere, for example to the Google office, is also quite a prize.


Does it happen that companies then try to use in their life the groundwork of the solutions submitted by the contestants?
Pretty rare. The main goal of companies that conduct such competitions is simply to popularize programming. The second goal is to search for new employees. But the second is not so important. Usually, a company arranges a competition precisely for more people to become interested in programming, and it’s not even about those who directly participated in the competition. Therefore, such competitions are usually held by large companies.

Competitions change over time? Are they becoming more difficult or, on the contrary, easier?

They become harder. More and more algorithms are considered something from the category of "everyone should be able to do it," "everyone knows that." You need to think as much as ten years ago. The steps to build a solution will require the same amount, but the basic blocks that make up the solution have become more difficult. People have learned more algorithms. Take, for example, the suffix tree: when it appeared, I was in school, and it seemed like a very cool algorithm, everyone who knows it is very smart and it’s a revolution in general. Now the same problems are solved using the suffix automaton, and this is a very simple algorithm that takes ten lines. That is, standard things have learned to simplify cool. Therefore, more complex tasks are being solved now.

About tasks and their compilation

How are the tasks for the competition? There are compilers, people who already know how to do it, or is it some kind of crowdsourcing, where everyone can offer something of their own?

In the aforementioned weekly competitions, it is this way: everyone can offer their task. But there is a requirement that a person have previously participated in a sufficient number of competitions. A kind of check if the person understands what the task should be about. After you can send your assignments, and the jury will answer whether you can use them, whether they are suitable. If the tasks are suitable, they are then given at competitions, and the author is paid for it by money - not very big, but still.


To invent such tasks is a special skill?

Oh yeah. You can invent tasks, starting from solutions. Let's say you read some article in a scientific journal about an interesting algorithm. Or I just found a certain algorithm and remembered that I had come across it before, but lately I have not seen it for a long time. You can come up with a task that requires its use.
The second way is when a problem arises in work or in life, and you realize that it can be used coolly. You may have to complicate something or change the restrictions, but then you get an interesting challenge for the competition.


Authors often try to make tasks closer to reality, use terms from life?

There are competitions of varying degrees of proximity to life. Usually the task at a competition is not given in any formal terms, like "it is given: to solve an equation such and such." Usually just given a background, history. As in school textbooks in mathematics: “Ten liters of water per minute flows in through one pipe.” Therefore, first you need to somehow formalize this story, find a mathematical problem in it, and only then solve it.
There are other competitions. In TopCoder, this is called Marathon Match, and other companies also hold similar contests. They are arranged a little differently. This is already a competition not for algorithms, but for solving approximate problems. When there is no exact solution and you need to come up with an option as best you can. Such competitions usually last two weeks, a month. You can send different solutions and observe that, yeah, now my solution is better than the rest by 20%.


“Better” —in faster, uses less memory, and so on?

Yes. For example, you need to come up with a scheme for distributing the movement of buses on the map of Moscow in order to use as few buses as possible. That is, there is a parameter in the problem statement that needs to be optimized, but there is no single “right decision”, only some approximate algorithms.

The same Topcoder held competitions together with NASA, and they say that the solutions that were offered to them, then really adapted and used on the ISS. They solved some specific problem, it seems, how to turn the solar battery so that it receives more energy.

Where to begin

From the point of view of preparing a good algorithmic programmer and a participant in various contests - how to prepare yourself for this? If you imagine yourself in the place of a high school student or first-year students?

I think the most standard way is to try. All competitions have an archive of previous contests, there are thousands of tasks that can be solved at any time.


And if I take the task and do not know at all from which side to approach it?

So take it easier. They are different. There are tasks that every second school graduate can solve. There are completely different levels of difficulty. Reaching should be pretty easy. There is no other way, it seems to me. Plus, this way you will immediately understand whether you like this activity or not.


What should be done to gain an algorithmic base? It is hardly necessary to immediately rush to read Knut.

It seems to me that it is necessary to begin with tasks. Only later, when you realize that you cannot solve any particular of them, in these competitions everyone has an analysis. You can read the solution if you can’t handle it yourself. For example, in the analysis it is indicated that a certain algorithm is used in the solution of the problem. You can read what this algorithm is, where else it is used. So much better than reading the list, "yeah, I have an algorithm that I need to learn over the summer." It is better to build on a specific task that you could not solve, because you do not know any particular algorithm. This is more correct. You remember better, the motivation is stronger. This method of studying algorithms is probably longer than the list, but it leads to better results.


If you want to “pump” yourself precisely according to the algorithms, is there any literature, textbooks?

The most standard textbook - Kormen, Leyzerson, Rivest with a donkey on the cover. "Algorithms: Construction and Analysis" is called. I don’t know, I haven’t studied for a long time, for sure there are now new textbooks that can be better. But in my time, Cormen was used. A whip is rather a reference book. If something needs to be found and it is not found anywhere, most likely it will be there. But reading Knut in a row ... is pretty sad.


First published in the magazine "Hacker" from 05/2014.

Subscribe to "Hacker"

• Paper version
• Hacker on iOS / iPad
• "Hacker" on Android