How to become the first in sports programming: ITMO University shares its 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 talk about what the future winner should know and be able to, and share their experiences and memories from participating in programming olympiads. Sebastiaan ter Burg / Flickr / CC




    About the course


    The course " How to Win in Programming Competitions: Secrets of Champions " started in October this year. The authors and instructors of the course were the champions of student olympiads who defended the honor of ITMO University in different years: Maxim Buzdalov , assistant professor of computer technology at ITMO University and champion ACM ICPC 2009, Pavel Krotkov, graduate of the ITMO University IT and programming department, 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 study the features and approaches used in sports programming. Participants will learn how competitions are held, analyze the most popular approaches to solving problems 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 not only “train” students for the olympiad tasks, but also talk about how to work in conditions of tough deadlines and find unusual and effective solutions.

    We learned from Maxim, Pavel and Daria what knowledge the future winner of programming olympiads should have, how important “chips” and life hacks are for victory, and what mistakes most newcomers to sports programming make.

    Minimum program: what you need to know to win the competition


    Pavel Krotkov calls the basic skills necessary to win the Olympiads: knowledge of mathematics, algorithms, and programming language. Without this knowledge, to succeed, of course, is impossible. 

    The second group of important skills: the right tactics, knowledge of "chips". In team competitions, this is the ability to optimally use time at the computer, the division of labor, the ability to debug your programs and teammate programs and look for errors in them. In personal competitions, these skills include, again, the ability to debug / test your programs, quickly test certain hypotheses. 

    Maxim Buzdalov supplements this list and immediately identifies seven skills necessary for successful participation in programming olympiads:

    1. The ability to come up with solutions to problems. This includes the ability to generate and test ideas, reduce one task to another and the like.
    2. A knowledge of algorithms and data structures, standard and not so. This knowledge about what algorithms / structures do exist, what tasks 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.
    3. The ability to effectively implement algorithms and data structures in practice. At the same time, the word “effectively” means two interrelated things - “efficiency” in terms of the functioning of algorithms / structures and “efficiency” in terms of the time they were written at a competition.
    4. Knowledge of a programming language and complexity models of operations of this language. So, some things for the required efficiency need to be written in different ways (using different approaches to data storage, code structuring) in C, C ++, Java and Python.
    5. Knowledge of various "hacks" that can speed up the already correctly written code.
    6. Ability to search for errors in the code and debug code.
    7. The ability to efficiently allocate resources - personal resources, team resources, computing resources - to achieve maximum results.

    Maxim emphasizes that different skills require different training. So, in his opinion, reading literature will help to better understand algorithms and data structures - but nothing more.

    Come up with solutions to problems will teach classes in mathematics. “Industrial” programming (that is, what programmers usually do as part of their business tasks) will provide 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 very difficult to develop without the practice of participating in competitions.

    Almost all of these points require constant development and constant work on yourself. For example, if you are new to the implementation of algorithms, but think of them well, you can solve (on paper) all the problems, but not solve (on a computer) practically none

    - Maxim Buzdalov

    Once again about the "chips"


    We asked the authors of the course whether a newcomer who is well versed in mathematics and programming, but is not familiar with chips, life hacks and other secret knowledge, can win the competition. The winners of the olympiads agreed that the “chips” are not everything: without the fundamental knowledge and hard work, the participant of the olympiad will be much more difficult to do:

    I would say that to succeed in competitions to a certain level, having only knowledge from the first category [knowledge of mathematics, algorithms, a programming language], is possible. Nevertheless, knowledge from the second category [understanding the right tactics, skills of competent resource allocation] greatly simplify life and work as a catalyst. As in any sport: there are physical skills, but there is a knowledge of technology, psychology, and so on. You can succeed only at the expense of the first, but the second will work as a catalyst

    - Pavel Krotkov

    It seems to me that those who are successful in the olympiads (take prizes in leading world competitions) can be moderately ignorant in paragraph 5 [from the list above] ("hacks"), and also, provided that they are genius in other areas - may not attach importance to item No. 7 (work with resources)

    - Maxim Buzdalov

    Daria Yakovleva noted that in the conditions of the Olympiad, the creative approach may 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 for solving problems, but it should be noted that the jury of the Olympiads tries to compose the tasks in such a way that the participants first 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 getting into the top 10 is real

    - Daria Yakovleva

    About teamwork


    Basic skills in single and team programming are different - though not significantly. Daria clarifies:

    In team competitions, a team has only one computer. Therefore, during the Olympiad, only one person writes a solution to a problem on a computer, the rest of the guys solve other problems on a piece of paper. Usually the team has: a mathematician, a programmer and an amateur to solve non-standard problems

    - Daria Yakovleva

    This means that a participant in team competitions can “emphasize” one or more areas - in this case, his weaknesses are compensated by colleagues. In this regard, Maxim recalls the 2009 ACM ICPC tournament:

    So, for example, in our team (we were world programming champions in 2009), Zhenya Kapun was an unsurpassed inventor of solutions, Slava Isenbayev was an excellent “universal fighter”, and tasks requiring large amounts of neat code (for example, tasks on computational geometry), I wrote best of all

    - Maxim Buzdalov

    Maxim and Pavel note: the separation of roles in a team often occurs naturally during the first ten training sessions. It happens that team members have slightly different interests, and as a result, different participants little by little specialize in different areas (as Maxim clarifies, it is not easy - for example, in computational geometry, tasks on flows, “tricky” data structures, suffix trees or suffix automata and so on Further). Someone implements the standard algorithm faster, or better navigates in a particular section of mathematics - all this affects the informal distribution of roles in the team.

    There are teams with a pronounced “mathematician” and a pronounced “encoder”. Of course, it is impossible to completely isolate these skills, since the encoder must understand mathematics and vice versa. In addition, if they also participate in personal competitions, inequality may decrease over time, as participants learn from each other.

    In any case, if you have a “mathematician”, or “encoder”, or “tester”, or a specialist in suffix automata in your team, this does not mean that you do not need to develop the appropriate skills.

    Quite the contrary - you have someone to learn from, and you need to use it - Maxim Buzdalov

    It happens that the teammates are approximately equal in strength and in the set of skills - as a result, the tactics 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 specialization in a particular field of knowledge: in most teams there is also a person who can make a decision in a difficult situation - he can be called a leader or captain.

    Pitfalls: what inexperienced participants fail on


    As the authors of the course note, the main problems of beginners are primarily related to the reassessment of their strengths and capabilities. Maxim Buzdalov calls their stunning confidence that the code they wrote works as the real scourge of inexperienced participants.

    Moreover, they practically do not distinguish [the difference between] “works” and “works on an example from the condition”. They don’t get the idea to check the code again, come up with a counterexample, try, finally, to prove the correctness of the solution. In particular, therefore, a verdict of the form “Wrong answer, test 2” leaves such participants extremely confused, and several such verdicts in a row - in a state of thorough bitterness.

    - Maxim Buzdalov

    As an example, Maxim cites one of the tasks from the course "How to Win in Programming Competitions: Secrets of Champions". Given a matrix of 3x3 numbers, you need to select three numbers from this matrix so that more than one number is not selected in any column or row, and the root of the sum of the squares of the numbers is maximum.

    The correct solution to this problem - at least one of them - is obvious: we sort through all possible triples of column numbers, and for each such triple we check the choice in which column a is selected in the first row, column b in the second, and column c in the third.

    However, many participants in the course sent such a solution: first we select the maximum of the numbers in the matrix, then cross out the corresponding row and column, then again select the maximum, and so on. This led to an incorrect answer on the sixth test. This solution is very easy to “kill”: just consider what will happen on such a matrix:

    9 8 1
    8 1 1
    1 1 1 1

    The correct decision will choose two eights and the remaining unit, while the sum of the squares will be 129. The “greedy” solution will choose the nine, then it will have nothing but units, and the sum of the squares will be 83. Extracting the root, of course, will not change that the first answer is more, and therefore better.

    Having received a similar example, many participants began to write all kinds of case analyzes, receiving incorrect answers on the same test or on other tests, while missing the main thing - having received a simple counterexample for the logic of the main part of their decision, we should stop and think. Instead of plugging holes, arranging props and making crutches, it would be nice to justify why the solution even works. And ideally - mathematically rigorously prove

    - Maxim Buzdalov

    Another common mistake that Daria notes is an int data type overflow:

    It [error] happens when you try to "put" in a variable a value greater than the permissible value. You need to be careful and evaluate the order of your values ​​in solving the problem, and everything will be fine

    - Daria Yakovleva

    Pavel Krotkov notes another important feature of experienced participants in the olympiads - stress resistance. Her beginners also lack - that's why the wrong decision can easily cause bewilderment and panic and lead to the 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 the right attitude play in the process of preparing for the competition, share their life hacks and little tricks, and also explain to whom (in addition to future Olympic winners) It may be of interest to ITMO University's How to Win Coding Competitions: Secrets of Champions course.

    Also popular now: