How to become the first in sports programming: ITMO University shares experience. Part 1
In this article we will talk about a new course that was launched by ITMO University on the edX platform this year. Under the cut - a story about the project “How to Win Coding Competitions: Secrets of Champions” and a large interview with the authors and instructors of the course, in which they discuss what the future winner should know and be able to, and share their experiences and memories from participating in programming contests.
Sebastiaan ter Burg / Flickr / CC
The course “ How to win in programming competitions: the secrets of champions ” started in October of this year. The course was created by the champions of student competitions that defended the honor of ITMO University at different times: Maxim Buzdalov , Associate Professor of Computer Technologies at ITMO University and ACM ICPC 2009 Champion, Pavel Krotkov, graduate of ITMO University, participant and organizer of many contests programming in Russia and abroad, including the ACM ICPC NEERC (Paul is now working in Facebook) and Daria Yakovleva , senior assistant of the Department of information systems at the University ITMO, in fl year entered the top ten in international competition on programming Google Code Jam for Women.
')
The course is designed for 5 weeks and aims to explore the features and approaches used in sports programming. Participants will learn how competitions take place, analyze the most popular approaches to problem solving and examples of their use, train to solve Olympiad tasks in conditions close to real ones (the final exam is held in the format of a real international programming competition).
The authors of the course do not just “train” students for olympiad tasks, but also talk about how to work under tight deadlines and find unusual and effective solutions.
We learned from Maxim, Pavel and Darya what knowledge the future winner of programming olympiads should have, how important “chips” and life hacks are for winning, and what mistakes beginners most often make in sports programming.
Pavel Krotkov calls the basic skills needed to win at olympiads: knowledge of mathematics, algorithms, programming language. Without this knowledge to succeed, by itself, is impossible.
The second group of important skills: the right tactics, knowledge of "chips." In team competitions, this is the ability to make optimal use of time at the computer, the division of labor, the ability to debug your programs and the programs of teammates and look for mistakes in them. In personal competitions, such skills include, again, the ability to debug / test your programs, to quickly test certain hypotheses.
Maxim Buzdalov complements this list and highlights at once the seven skills necessary for successful participation in programming competitions:
Maxim stresses that different skills require different training. So, in his opinion, reading the literature will help to better understand the algorithms and data structures - but no more.
Coming up with problem solving will teach math lessons. “Industrial” programming (that is, what programmers usually do as part of performing work tasks for a business) will provide development of skills # 4, # 5, and # 6. But the ability to effectively implement algorithms and data structures in practice and the ability to efficiently allocate resources are, according to Maxim, typically “sports” skills - those that are extremely difficult to develop without the practice of participating in competitions.
We asked the authors of the course whether a beginner who is knowledgeable in mathematics and programming, but who is not familiar with "chips", live hacking and other secret knowledge, could win the competition. The winners of the Olympiad agreed that the “chips” is not all: the participant of the Olympiad will be much more difficult to do without fundamental knowledge and diligence:
Daria Yakovleva noted that in the conditions of the Olympiad, creativity can be more important than the knowledge of "chips", so talented newcomers can count on a decent result:
Basic skills in single and team programming differ - however, slightly. Daria specifies:
This means that a participant in a team competition can focus on one or several areas - in this case, his weaknesses are compensated by colleagues. Maxim recalls the 2009 ACM ICPC tournament in this regard:
Maxim and Pavel note: the division of roles in a team often occurs naturally during the first ten training sessions. It happens that teammates have slightly different interests, and as a result, different participants gradually specialize in different areas (as Maxim specifies difficult ones, for example, computational geometry, flow problems, “tricky” data structures, suffix trees, or suffix automata, and so on. Further). Someone is faster implementing a standard algorithm, or better oriented in a particular section of mathematics - all this affects the informal distribution of roles in a team.
It happens that teammates are about equal in strength and skill set - as a result, the tactic of working in a team comes down to the fact that the task is written by the one who first solved it. However, as Pavel notes, the distribution of roles is not always associated with a specialization in a particular area of ​​knowledge: most teams also have a person who can make a decision in a difficult situation - he can be called a leader or a captain.
According to the authors of the course, the main problems of newcomers are primarily related to the overestimation of their strength and capabilities. Maxim Buzdalov calls the real scourge of inexperienced participants their stunning confidence that the code they wrote works.
As an example, Maxim gives one of the tasks from the course “How to win in programming competitions: the secrets of champions”. Given a matrix of numbers of size 3x3, it is necessary to choose three numbers from this matrix so that no more than one number is chosen in any column or line, and the root of the sum of squares of numbers is maximum.
The correct solution to this problem - at least one of them - is obvious: we iterate over all possible triples of the column numbers <a, b, c>, and for each trip, we check the choice in which the column a is selected in the first row and the column in the second row b, and in the third column c.
However, many course participants sent this solution: first select the maximum number from the numbers in the matrix, then cross out the corresponding row and column, then select the maximum again, and so on. This led to an incorrect answer on the sixth test. This solution is very easy to "kill": it is enough to consider what happens on such a matrix:
9 8 1
8 1 1
1 1 1
The correct solution will choose two eights and the remaining unit, while the sum of squares will be equal to 129. The “greedy” solution will choose nine, then it will have nothing left but units, and the sum of squares will be 83. Removing the root, of course, does not change what The first answer is more, and therefore better.
Another common mistake Daria notes is the overflow of the int data type:
Pavel Krotkov notes another important feature of experienced Olympiad participants - stress resistance. It is also not enough for its beginners - that is why the wrong decision can easily cause bewilderment and panic and lead to loss of precious time.
The ability to overcome stress will be discussed in the second part of our conversation: the authors and instructors of the course will tell you what role psychology and correct attitude play in the preparation for the competition, share their life hacks and little tricks, and also explain to whom (besides future winners of the Olympiads) The course “How to Win Coding Competitions: Secrets of Champions” at ITMO University might be interesting.
Sebastiaan ter Burg / Flickr / CC
About the course
The course “ How to win in programming competitions: the secrets of champions ” started in October of this year. The course was created by the champions of student competitions that defended the honor of ITMO University at different times: Maxim Buzdalov , Associate Professor of Computer Technologies at ITMO University and ACM ICPC 2009 Champion, Pavel Krotkov, graduate of ITMO University, participant and organizer of many contests programming in Russia and abroad, including the ACM ICPC NEERC (Paul is now working in Facebook) and Daria Yakovleva , senior assistant of the Department of information systems at the University ITMO, in fl year entered the top ten in international competition on programming Google Code Jam for Women.
')
The course is designed for 5 weeks and aims to explore the features and approaches used in sports programming. Participants will learn how competitions take place, analyze the most popular approaches to problem solving and examples of their use, train to solve Olympiad tasks in conditions close to real ones (the final exam is held in the format of a real international programming competition).
The authors of the course do not just “train” students for olympiad tasks, but also talk about how to work under tight deadlines and find unusual and effective solutions.
We learned from Maxim, Pavel and Darya what knowledge the future winner of programming olympiads should have, how important “chips” and life hacks are for winning, and what mistakes beginners most often make in sports programming.
Minimum program: what you need to know to win the competition
Pavel Krotkov calls the basic skills needed to win at olympiads: knowledge of mathematics, algorithms, programming language. Without this knowledge to succeed, by itself, is impossible.
The second group of important skills: the right tactics, knowledge of "chips." In team competitions, this is the ability to make optimal use of time at the computer, the division of labor, the ability to debug your programs and the programs of teammates and look for mistakes in them. In personal competitions, such skills include, again, the ability to debug / test your programs, to quickly test certain hypotheses.
Maxim Buzdalov complements this list and highlights at once the seven skills necessary for successful participation in programming competitions:
- Ability to invent problem solving. This includes the ability to generate and test ideas, reduce one task to another, and the like.
- Erudition in the field of algorithms and data structures, standard and not very. This is knowledge of what algorithms / structures exist at all, what problems they solve, what properties they require from the problem being solved, what is the asymptotic complexity of these algorithms or operations with these data structures.
- The ability to effectively implement algorithms and data structures in practice. In this case, the word "effectively" refers to two interrelated things - "efficiency" in terms of the functioning of algorithms / structures and "efficiency" in terms of the time they were written in a competition.
- Knowledge of programming language and model of the complexity of the operations of this language. So, some things for the required efficiency need to be written differently (using different approaches to data storage, code structuring) in C, C ++, Java and Python.
- Knowledge of various “hacks” capable of speeding up well-written code.
- The ability to search for errors in the code and debug the code.
- The ability to effectively allocate resources - personal resources, team resources, computing resources - to achieve maximum results.
Maxim stresses that different skills require different training. So, in his opinion, reading the literature will help to better understand the algorithms and data structures - but no more.
Coming up with problem solving will teach math lessons. “Industrial” programming (that is, what programmers usually do as part of performing work tasks for a business) will provide development of skills # 4, # 5, and # 6. But the ability to effectively implement algorithms and data structures in practice and the ability to efficiently allocate resources are, according to Maxim, typically “sports” skills - those that are extremely difficult to develop without the practice of participating in competitions.
Almost all of these items require constant development and continuous work on themselves. For example, if you are new to the implementation of algorithms, but you come up with them well, you can solve (on paper) all the tasks, but not solve (on the computer) almost any
- Maxim Buzdalov
Once again about the "chips"
We asked the authors of the course whether a beginner who is knowledgeable in mathematics and programming, but who is not familiar with "chips", live hacking and other secret knowledge, could win the competition. The winners of the Olympiad agreed that the “chips” is not all: the participant of the Olympiad will be much more difficult to do without fundamental knowledge and diligence:
I would say that it is possible to succeed in competitions to a certain level, having only knowledge from the first category [knowledge of mathematics, algorithms, programming language]. Nevertheless, the knowledge from the second category [understanding the right tactics, skills of competent allocation of resources] greatly simplifies life and works as a catalyst. As in any sport: there are physical skills, and there is knowledge of technology, psychology, and so on. You can only succeed at the expense of the former, but the latter will work as a catalyst.
- Pavel Krotkov
It seems to me that those who are successful in olympiads (win prizes at the world's leading competitions) can be moderately ignorant in paragraph 5 [from the list above] (“hacks”), and also - subject to genius in other areas - may not attach importance to item number 7 (working with resources)
- Maxim Buzdalov
Daria Yakovleva noted that in the conditions of the Olympiad, creativity can be more important than the knowledge of "chips", so talented newcomers can count on a decent result:
Of course, it is important to know the various methods of solving problems, but it should be noted that the jury of the Olympiad tries to make the tasks so that the participants first of all come up with an idea, a solution on their own. However, complex tasks, of course, require additional knowledge. Therefore, I think it will be difficult to win, but to get to the top 10 is really
- Daria Yakovleva
About teamwork
Basic skills in single and team programming differ - however, slightly. Daria specifies:
In team competitions, the team has only one computer. Therefore, during the Olympiad, only one person writes a solution to the problem on the computer, the other guys solve other problems on the leaflets. Usually the team has: a mathematician, a programmer and an amateur to solve non-standard problems
- Daria Yakovleva
This means that a participant in a team competition can focus on one or several areas - in this case, his weaknesses are compensated by colleagues. Maxim recalls the 2009 ACM ICPC tournament in this regard:
So, for example, in our team (we were world champions in programming in 2009) Zhenya Kapun was an unsurpassed solution inventor, Slava Isenbaev was an excellent “universal fighter”, and tasks that require large amounts of neat code (for example, problems in computational geometry), I wrote the best
- Maxim Buzdalov
Maxim and Pavel note: the division of roles in a team often occurs naturally during the first ten training sessions. It happens that teammates have slightly different interests, and as a result, different participants gradually specialize in different areas (as Maxim specifies difficult ones, for example, computational geometry, flow problems, “tricky” data structures, suffix trees, or suffix automata, and so on. Further). Someone is faster implementing a standard algorithm, or better oriented in a particular section of mathematics - all this affects the informal distribution of roles in a team.
There are teams with a pronounced "mathematician" and a pronounced "coder". Naturally, it is impossible to completely isolate these skills, since the coder must understand mathematics and vice versa. In addition, if they also participate in individual competitions, inequality may decrease with time, as participants learn from each other.
In any case, if you have a “mathematician,” or “coder,” or “tester,” or suffix machine specialist in your team, this does not mean that you do not need to develop relevant skills. Just the opposite - you have someone to learn from, and this should be used.
- Maxim Buzdalov
It happens that teammates are about equal in strength and skill set - as a result, the tactic of working in a team comes down to the fact that the task is written by the one who first solved it. However, as Pavel notes, the distribution of roles is not always associated with a specialization in a particular area of ​​knowledge: most teams also have a person who can make a decision in a difficult situation - he can be called a leader or a captain.
Reefs: what inexperienced participants fail
According to the authors of the course, the main problems of newcomers are primarily related to the overestimation of their strength and capabilities. Maxim Buzdalov calls the real scourge of inexperienced participants their stunning confidence that the code they wrote works.
And they practically do not distinguish [the difference between] "works" and "works on the example of the condition." They don’t come up with the idea to check the code again, think up a counterexample, try to finally prove the correctness of the solution. In particular, therefore, the verdict of the form “Invalid answer, test 2” leaves such participants in utter confusion, and several such verdicts in a row are in a state of profound bitterness.
- Maxim Buzdalov
As an example, Maxim gives one of the tasks from the course “How to win in programming competitions: the secrets of champions”. Given a matrix of numbers of size 3x3, it is necessary to choose three numbers from this matrix so that no more than one number is chosen in any column or line, and the root of the sum of squares of numbers is maximum.
The correct solution to this problem - at least one of them - is obvious: we iterate over all possible triples of the column numbers <a, b, c>, and for each trip, we check the choice in which the column a is selected in the first row and the column in the second row b, and in the third column c.
However, many course participants sent this solution: first select the maximum number from the numbers in the matrix, then cross out the corresponding row and column, then select the maximum again, and so on. This led to an incorrect answer on the sixth test. This solution is very easy to "kill": it is enough to consider what happens on such a matrix:
9 8 1
8 1 1
1 1 1
The correct solution will choose two eights and the remaining unit, while the sum of squares will be equal to 129. The “greedy” solution will choose nine, then it will have nothing left but units, and the sum of squares will be 83. Removing the root, of course, does not change what The first answer is more, and therefore better.
Having received a similar example, many participants began to write all sorts of case studies, getting wrong answers on the same test or on other tests, while losing the main thing - having received a simple counterexample for the logic of the main part of their decision, you should stop and think. Instead of plugging holes, laying out supports and making crutches, it would be good to at least justify why the solution works at all. And ideally - to prove mathematically rigorously.
- Maxim Buzdalov
Another common mistake Daria notes is the overflow of the int data type:
It [an error] happens when you try to “put” in a variable the value more than the allowable one. You need to be careful and evaluate the order of your values ​​when solving a problem, and everything will be fine
- Daria Yakovleva
Pavel Krotkov notes another important feature of experienced Olympiad participants - stress resistance. It is also not enough for its beginners - that is why the wrong decision can easily cause bewilderment and panic and lead to loss of precious time.
The ability to overcome stress will be discussed in the second part of our conversation: the authors and instructors of the course will tell you what role psychology and correct attitude play in the preparation for the competition, share their life hacks and little tricks, and also explain to whom (besides future winners of the Olympiads) The course “How to Win Coding Competitions: Secrets of Champions” at ITMO University might be interesting.
Source: https://habr.com/ru/post/318444/
All Articles