Programming Olympiads, a look from NSU. Article 5 - how the team plays

    During my previous articles, I more or less described how a typical tour of a regular Olympiad on programming from the inside goes. Someone was interested in this internal mechanics, and someone wanted to hear more about coding itself. In today's article I will talk about what exactly the team does during the tour, how and what it does, what tricks it uses and what comes of it. I’ll probably talk about training and personal contests later, although after this article there will be almost nothing to talk about.

    I am waiting for comments from current and former ACM sheep, I can learn some new subtleties and methods, because soon my last season and I want to spend it extremely shockingly.

    The first article is about drafting tasks.
    The second article is about testing systems.
    The third article is about the work of the organizing committee.
    The fourth article is about the tour itself.


    Command structure


    A team is three people. More - no way, less (according to current rules) - too. Last season, Misha and I were ultimatum asked to look for a third or no one is going anywhere. Fortunately, Kolya Orfest was free and we rushed. Alas, we did not have time to play at the level of the first 3 teams of our university, and therefore did not go to the semifinals again. This year we’ll try to repair teamwork.

    In the best teams, each participant individually can take the whole tour (well, or most of the tasks from it). In lower-level teams, individual participants often specialize in particular topics. So with us, almost all of the geometry rests on Misha’s shoulders, and nobody decides to decide number theory or what combinatorial fabrications. So, due to specialization on different topics, you can get a team with a total knowledge of the level of more powerful national teams in personalities.

    Usually, 3 roles can be distinguished in a team - encoder, mathematician, and algorithmist. Each of the participants should execute at least 2 of them, and ideally - all 3. But not all cases are ideal, so sometimes some participants do not write a single line of code during the tour, while others do not read half the tasks, while the team achieves a good result. It’s not worth it to abuse, it’s better to let everyone know everything =)

    Tour start


    About 10 minutes before the start of the team allowed to the computer. The fastest command encoder sits down at the machine and stuffs the templates in the languages ​​in which it is supposed to be written, adjusts the IDE (setting your favorite perspective in Eclipse from scratch has already been worked out so much that it almost comes to automatism). The rest prepare the workplace - pens, notebooks, nerves.

    Tasks appear, usually in paper form. Ideally - 3 copies, one per participant, but maybe less. Two - a minimum for convenient operation. Then two members of the team eagerly snapping up the tasks, not burdened with the keyboard at the moment, and begin to look for a "console". In 90% of the tours that I wrote, there is at least one problem that needs to be solved immediately, quickly, without options and on the first try. After finding it (minutes in 2), the algorithmist sits down at the encoder and, in general terms, introduces him to the task, with the essence - so that he does not bother himself with reading and translating the text (in most competitions, the text is in English, therefore it is better to avoid unnecessary plugs). Next, the encoder is left alone with the keyboard and the condition of this task, and the other two rush to disassemble the whole tour.

    The guys read the whole tour and look for the task that they will write next. Further, while the keyboard is busy, the code is carefully written in a notebook. Not schematically, namely, a code ready for transfer. Then, as soon as the fast and dirty encoder copes with one task (it is assumed that he will be able to do this without external interference), one of the remaining two sits in his place, the encoder carefully reads the tour. The third participant at this moment goes out to observe the writing of the code - pair coding in sports programming is very useful. At the same time, this participant draws up tests for the current task.

    Yes, I almost forgot to say. Around the time of writing the first or second task, the status of the tournament is periodically monitored in order to know what people are solving so as not to go to the wrong steppe. At the same time, a personal queue of writing tasks in the team is compiled based on complexity / knowledge / wishes.

    Mid Tour


    While there is something to decide, it is exactly what is decided :) It usually happens according to the following system - one person writes, the second observes, the third thinks about another task. + The second and third are tests for the first task, manually calculating the result. If everything is bad and all the tasks to be completed are over, then the team sits down to storm. The technology of brainstorming is already familiar to everyone, so I won’t elaborate here.

    When tasks enter the “writing queue”, the following technology from team math tournaments is very useful. When, of course, the right and the best solution is born in someone’s head, he goes to the person who did not think about this problem and explains the solution to the problem. It helps with screenings of nonsense and mess.

    Tour end


    The end of the tour takes place in 3 different ways. The first, most beautiful option is an hour and a half to two to 5 hour cut-off, with all the advantages in the rating and proudly raised your head. We only had this in a couple of training sessions. And among Moscow and St. Petersburg teams, this is also practiced at the quarter finals =) The

    second option is if there is still a lot of scribble, and there is not enough time. Then, by team vote (about an hour before the end of the tour), it is decided which tasks to write, depending on confidence in them and the likely speed of writing.

    And the third way is “ballet”. When there are no more ideas, but I want to do something. Then they start to write various dirty frontal decisions, in the hope that the time limit will bypass us. Maybe a circus at all.
    So once in the CBOSS tour we solved the problem with binary search in the testing system. We wrote the task, and quite stupidly and in the forehead. In it, for empirical reasons, it was suggested that if in the first ~ 2 million nothing is fixed on us, then nothing will break further. The time limit has broken. They put a limit on half a million - it falls in accuracy. There was nothing to do, so we reached the solution by successive approximations. Failed on the 30th

    Tricks and Jumps


    When writing tours, various interesting and useful tricks are often used. Often they look amazing for inexperienced teams, but are useful to everyone.

    Sly precalc

    Many tasks are kosher to solve by preliminary miscalculation. As I wrote earlier, 5 minutes of the computer’s work, the teams will solve the problem by the method.
    read(a); write (res[a]);
    But often the task seems to be considered cool or dumb in the forehead, but for the first there is not enough space in the code, and for the other - time limit. Then you can apply the dirty hack number one.

    Here is an example tasksolved in this way. Kolya and I began to solve it at the same time, he went the way of matan, generated a tricky tablet and somehow from it calculated the solution at an arbitrary point. I did the most straightforward, but no less creative. A cycle with a length of 100,000 is executed in a permissible time, and 1000 pre-calculated values ​​are included in the code. Thus, the grid of solutions was calculated, and then it was counted forehead from the nearest value. I managed faster, although the approach is much less scientific and scalable.

    Good generator

    The technique that Dima Kovchin brought to our team. It is mainly used on integer problems. Quickly, in about 10 minutes, a generator is written that brazenly calculates the first 20 values ​​of the objective function. Then the best minds of the team sit down and try to reveal the general pattern by the method of glazed analysis. Often, the pattern in the first 2-3 values ​​can be erroneous, the values ​​of 20 already allow you to fairly reliably believe the hypothesis. Handwriting on paper takes much more time. It is worth noting that the Newton method can build a good-order curve through any number of points, so you should not abuse the method.

    Excel is a programmer's best friend

    I don’t know how the teams of other universities have, but with us this is a proverb. We always write various vile and filthy tests in Excel (more precisely in OpenOffice Calc). Excel helps us in graphical analysis of input data. And the funny guys from SibGUTI, with whom our team constantly shared 1st place among the best KVN teams in ACM =), even rumored for some time that NSU MOM and NSU NAN solve problems in exel and send xls files to the testing system . This, of course, is not so, but it’s better than in exel to build makstest for bullying the task simply nowhere.

    Figured googling

    Orfest also hinted at the fact that without Google it can be complicated. In large tournaments of the type of the All-Siberian Olympiad, such luxury, of course, will not be given to us, but at the same CBOSS you can use it without a hitch. In Google and Wikipedia, you can refresh mathematical knowledge, so as not to bother with the conclusion of something that is unremarkable offhand, and if you really want to - break into a ready-made algorithm. You should not consider this a panacea for all diseases, in many tournaments the external Internet is prohibited as such, but sometimes the services of web services are useful. At least even for the translation of obscure words that may be significant in solving the problem. And at the stage of "ballet" this may come down to the next show.
    About 3 years ago, our team was solving some problem about the elf seating in the Santa Claus team. It was already at the end of the tour, the degree of boiling of the brain was reached even earlier. The show began with the fact that the variables for the deer array were named “loses” with the comment “Moose - they are moose in Lapland.” When the decision was made to search for an algorithm in Yandex, the collective mind gave birth to only such a request: “Elves to plant deer elves”. The tour on this request was completed, and another fun moment was added to the track record of our team.

    So far, alas, I have run out of topics about sports programming. If someone throws an idea, what else can I write about, I will be very grateful.

    Also popular now: