October 2, 2014 at 09:57Interview with the legend of sports programming Peter Mitrichev
They say that when he was born, Donald Knut himself looked at 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 following the progress of quantum computing with a smile, because when they see his numbers, they themselves factor in fear. But we definitely know one thing: Peter is the real god of sports programming.
- Winner of numerous championships, Peter won twice in TopCoder and twice took second place in ACM ICPC.
- In his free time, Peter writes a blog about regular contests “Algorithmic Problems for Dummies”: petr-mitrichev.blogspot.ru.
- Now Mitrichev works at Google, where he is engaged in search quality. Peter also helps in preparing for the Google Code Jam competition.
Many people think that sports programmers are cool guys, real geeks who understand algorithms and solve complex problems. But they also say that it is very difficult for them to apply themselves somewhere later. This is true?
Sports programming, and in general what we do at the Olympics, is really not a thing that you can make a living from. On the other hand, programming, like any other sport, is a development for a person. Thanks to him, a person becomes smarter, better programs, better looking for errors in programs. After such preparation it is easier to work and do other interesting things.
Algorithms are definitely applicable in the practice of a programmer, although at work I met with algorithms that are more complicated than those that can be found in olympiads. But at the Olympics, we are limited to algorithms that, roughly speaking, can be written in half an hour or an hour. Therefore, there in tasks a very specific, limited set of algorithms is used. In real life, everything is just more ... vast.
In what language did you write solutions for problems?
In Java. At school I wrote in Pascal because I knew nothing more then. And then, when it was necessary to choose what to switch to, Java turned out to be 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 most use, is different in that it is quite easy to write the wrong program on it. You can accidentally forget something, assign the wrong type to a variable, but all this will somehow compile and work somehow. Most likely not the way you expect.
In Java, if you make a mistake or a typo, the program most likely just does not compile. Everything is stricter here, as is the case with Pascal. It seemed to me more suitable. The flip side - Java programs often run one and a half times slower than C ++ programs. Sometimes just these one and a half times are not enough for the program to fit into the task condition.
Everyone can choose a programming language, right?
There are limitations. Of course, there are different competitions ... take the Google Code Jam, for example. When we decided how to make it better, we came up with the idea that you can work in any language. You download the input file with the task data to the computer, run your program on the computer, and then send the result to the server. What compiler / interpreter you have on your computer, you can use it. The disadvantage of this system is that people have different computers. Someone has a computer ten times more powerful than another. Therefore, it is necessary to create tasks where the wrong solution from the right one differs by at least a hundred times in speed. So that if a person has a computer ten times slower, the correct solution works for him, or the wrong solution doesn’t work on the computer ten times faster.
Topcoder, Codeforces and ACM use a standard system where you send the source code and they run it on their server. Here you are limited by what they have on the server. Most participants, 70–80% use C ++, another 20% use Java, very few other languages. This, it seems to me, is such a cycle - new people who come to the 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 that particularly suitable for competitions, it just happened historically.
That is, in life all this applies? 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 any bank?
It seems to me that this is a very useful part of the skill, the part that is responsible for the ability to write a program the first time, without errors, or find an error in a friend's program. I myself did not work in a bank, but it seems to me that such skills would be useful there too. 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 history, everything was the same as the others. Now I am engaged in search (its general part, which does not depend on the country and language), but, unfortunately, I can not tell anything about it, since this is a very confidential part.
Sports Programming: Pros and Cons
Let me try to ask you a stupid question :). Why do you need to do sports programming, what 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 come up with a reason why you should not spend time on sports programming?
I think you need to be aware that this is not the main thing in life. Have any other goals besides this. If something starts to occupy absolutely your whole life, probably this is an occasion to think about at least taking 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 professionally train new sports programmers - coaches. Andrey Stankevich, Misha Mirzayanov and others. They all teach at universities, but they spend a substantial part of their working time on preparing students and schoolchildren for programming competitions. For them, this is really a job and, one might say, a career.
Have you ever thought about this? Nowhere do you participate in the jury or as a task compiler?
I tried to teach schoolchildren at the 57th school, where I studied. I tried to prepare teams for the Olympics. Now in Moscow this topic is very active - MSU, Fiztekh, and the Higher School of Economics have teams. But with the teaching I somehow did not work out.
As for the contests, first of all, I help to do tasks for the 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 teams and teams of the former USSR for the finals.
Can I earn money in competitions? After all, they give cash prizes for the victory.
Too small a chance. One prize for ten thousand participants? .. I would not call it earnings. Counting on this as the main source of income ... it seems to me, without a chance.
But, as I said, there are many different competitions. The same Topcoder holds competitions in software development. Suppose you want to develop a component for a program that does this. Based on the results, they evaluate whoever succeeded and they use the best - the client buys this decision and pays money to the one who made this decision. The people who do this full time, as I understand it, earn pretty well.
Contests today
Tell me in more detail what kind of competition is happening now, how is all this happening?
Today there are two types of contests. There are weekly, regular competitions. They are carried out by two main sites - TopCoder and Codeforces. Each contest takes one and a half to two hours. There, participants are given several tasks that need to be solved and the program sent to the server. The organizers check if the program is working.
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. Three hours are allotted for one hour and fifteen minutes.
Tasks are usually divided into very simple, medium and complex. The organizers try to pick them up so that, say, five people solve all the problems, one hundred people - two, and all the rest solve at least one. Moreover, for each task it is important when you submit it - the later, the less points you get. So those people who solved the same number of tasks are divided. Then the points are added up. A common task costs 250 points. Average 500. Complex 1000. On average, people from the first places get a thousand points with something for the competition.
Then they take a break for five minutes and another fifteen minutes are allotted for the search for errors from others. You can open the decision of any person, for any task in your "room". A “room” is when people participating in a competition accidentally break into groups of twenty people. They are divided into "rooms". You can open any decision of any person from your "room". If the decision seems wrong to you, then you can drive in the input data on which it will be incorrect. 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. Still, the main points are awarded for solving problems, and not for finding errors.
After all this, the tasks are checked on the tests that the jury prepared. If the task does not work, the person gets 0 points.
There is another second site, Russian, - Codeforces. Their rules are slightly different, but the format is approximately the same - two hours and several tasks. If you like, this format can be called entertaining, unlike student contests, which last five hours.
But there are still large, annual contests?
Yes, in addition to the two described competitions, which take place weekly, there are many more annual competitions. Usually they are arranged like this: a large company (Google, Yandex, TopСoder, IBM) holds a competition with several stages of selection. The first stages go through the Internet. And the final stage is already being held in a specific place where all the finalists are taken. There are five to ten such competitions, but they are long, so some of them happen all the time.
Are all these competitions individual?
Most competitions are now individual. Team - this is mainly a student competition, the main one is ACM ICPC. And other student competitions are also usually made team, because, roughly speaking, the team is already there. It’s easier to get people interested. Here, veteran competitions are usually personal.
Almost all competitions have some ratings, the most famous among TopСoder. What it is?
Weekly competitions have a rating, like in chess, which is updated after each competition. Those who performed better get a plus, while worse - a minus. If you did not participate at all, the rating does not change. The system is designed in such a way as to equalize people who are frequent and rare. Pressure "you need to participate constantly" is not there. There are many people who are much older than me, they appear very rarely - once every two months - and still they still have a good rating, because they continue to solve problems well.
Are you second in TopCoder rankings?
Yes, in the first place Gena Korotkevich, a very smart student from Gomel, now he is studying at ITMO. On Codeforces, I’ve gotten worse results recently, now I’m sixth or fifth. There is also Gena in the first place.
Perhaps playing online and offline is a completely different feeling and experience?
Of course. It seems to me that a very important positive side of sports programming is that all competitions end onsite-round, where all the best come. Thanks to this I met many cool people from around the world. In general, the main “prize” in such competitions, as it seems to me, is precisely a meeting with people. Spend time with them, communicate, learn something new. It is very funny that people from other countries, who often do not speak English well, 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 may not solve anything and be upset. In competitions with the selections, it is usually simpler, at least in the first stages. Their main idea is for everyone to 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.
It happens that companies then try to use in life the achievements of the decisions submitted by the contestants?
Pretty rare. The main goal of the companies that conduct such competitions is simply to popularize programming. The second goal is to find new employees. But the second is not even so important. Usually a company arranges a competition just so that more people 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.
Do competitions change over time? Are they getting harder or, conversely, easier?
They are getting harder. More and more algorithms are considered to be something of the category "everyone should be able to do this," "everyone knows that." You need to think as much as you did ten years ago. The steps to build a solution will require the same number, but the basic blocks that make up the solution have become more complicated. People learned more algorithms. Take, for example, the suffix tree: when it appeared, I went to school, and it seemed like a very cool algorithm, everyone who knows it is very smart and this is generally a revolution. Now the same tasks are solved using a suffix machine, and this is a very simple algorithm that takes ten lines. That is, standard things have learned to simplify great. Therefore, they are now solving more complex problems.
About tasks and their preparation
What are the tasks for the competition? Are there compilers, people who already know how to do this, or is it some kind of crowdsourcing, where everyone can offer something of their own?
In the mentioned weekly competitions, it’s just like this: everyone can offer their task. But there is a requirement that a person before that participated in a sufficient number of competitions. It’s a kind of check whether a person understands what the tasks should be. After you can send your assignments, and the jury will answer whether they can be used, whether they are suitable. If the tasks are suitable, then they are given at competitions, and the author is paid money for this - not very big, but still.
Come up with such tasks - is this a special skill?
Oh yeah. You can come up with tasks, starting from solutions. Let's say you read some article in a scientific journal about an interesting algorithm. Or just found a certain algorithm and remembered that I had come across it before, but recently I hadn’t seen it for a long time. You can come up with a task that requires its use.
The second way: when a problem arises in work or in life, and you understand 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.
Do 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 the competition is not given in any formal terms, such as "given: solve the equation such and such." Usually just a background is given, a story. As in school math textbooks: “Ten liters of water per minute flows 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. At TopCoder, this is called Marathon Match, and other companies also run similar contests. They are arranged a little differently. This is not a competition in algorithms, but in solving approximate problems. When there is no exact solution and you need to come up with the option as best as possible. Such competitions usually last two weeks, a month. You can send different solutions and observe that, yeah, right now my solution is 20% better than the others.
“Better” - meaning faster, uses less memory, and so on?
Yes. For example, you need to come up with a distribution scheme for the movement of buses on a map of Moscow in order to use as few buses as possible. That is, in the problem statement there is a certain parameter that needs to be optimized, but there is no single “right solution”, only some approximate algorithms.
The same Topcoder held competitions with NASA, and they say that the solutions that they were offered were then really adapted and used on the ISS. They solved a specific problem, it seems, how to turn the solar panel so that it receives more energy.
Where to begin
From the point of view of preparing a good algorithmic programmer and 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?
It seems to me that the most standard way is to try. All competitions have an archive of previously held contests available, there are thousands of tasks that can be solved at any time.
And if I take a task and don’t know at all which side to approach it with?
So take it easier. They are different after all. There are tasks that every second graduate of the school can solve. There are completely different levels of difficulty. Getting involved should be pretty easy. There seems to be no other way. Plus, in this way you will immediately understand whether you like this activity or not.
What needs to be done to gain an algorithmic base? It is hardly necessary to immediately rush to read Knut.
It seems to me that you need to start with the tasks. Later, when you realize that you cannot solve a particular one of them, in these competitions each has a debriefing. You can read the solution if you can’t manage it yourself. For example, the analysis indicates that a certain algorithm is used in solving the problem. You can read what kind of algorithm it is, where else it is used. It’s better than reading from 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 specific algorithm. This is more correct. You remember better, motivation is stronger. This method of learning algorithms is probably longer than the list, but it leads to better results.
If you want to "pump" yourself precisely by algorithms, is there any literature, textbooks?
The most standard textbook is Cormen, Leiserson, Rivest with a donkey on the cover. “Algorithms: Construction and Analysis” is called. I don’t know, I haven’t studied for quite a while, now there are probably new textbooks that could be better. But in my time they used Cormen. The 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 ... it's pretty sad. First published in the Hacker magazine from 05/2014. Subscribe to Hacker
