Programming Olympiad, view from NSU. Article 5 - how the team plays
During my previous articles, I have more or less described how a typical round of an ordinary programming contest from the inside goes. Someone was interested in this internal mechanic, 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 it does what, what tricks it uses and what comes out of it. I will tell you about trainings and personal contests later, although after this article there will be almost nothing to talk about.
I am waiting for comments from existing and former ACM-ovtsev, what new subtleties and methods can be gathered, because my last season is soon and I want to spend it extremely hard.
The first article is about drawing up 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.
')
A team is three people. More - no way, less (according to the current rules) - too. Last season, Misha and I were ultimately asked to look for a third, or no one goes anywhere. Fortunately, Kohl 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 we did not qualify for the semifinals once again. This year we will try to fix the interaction in the team.
In the best teams, each participant individually can take the entire tour (or most of the tasks from it). In lower level teams, individual participants often specialize in specific topics. So we have almost all the geometry falls on Misha’s shoulders, and to solve the theory of numbers or which combinatorial fabrications no one forwards climbs me. So, due to the specialization on different topics, you can get a team that has total knowledge at the level of stronger teams in the personalities.
Usually there are 3 roles in a team - a coder, a mathematician and an algorithmist. Each of the participants must perform at least 2 of them, and ideally, all 3. But not all cases are perfect, so sometimes some participants do not write a single line of code during the tour, while others do not read half of the tasks, while the team reaches a good result. You should not abuse it, it is better to let everyone know everything =)
10 minutes before the start of the team allowed to the computer. The fastest coder of the team gets behind the car and stuffs the templates in the languages ​​in which the letter is supposed to, adjusts the IDE (setting up your favorite perspective in Eclipse from scratch is already so worked out that it almost comes to automatism). The rest prepare the workplace - pens, notepads, nerves.
Tasks appear, usually on paper. Ideally - 3 copies, one per participant, but maybe less. Two - at least for convenient work. Then the tasks are eagerly snapped up by two team members who are not burdened with the keyboard at the moment and begin to look for a “comforter”. In 90% of the tours that I wrote, there is at least one task that must be solved immediately, quickly, without options and on the first attempt. After finding it (about 2 minutes), the algorithmist sits down at the coder and in general terms introduces him to the task, with the gist - so that he doesn't bother to read and translate the text (in most olympiads, the text is in English, so it’s better to avoid unnecessary plugs). Next, the coder is left alone with the keyboard and the condition of this task, and the other two rush to disassemble the entire tour.
The guys read the entire tour and are looking for a task that they will write next. Further, while the keyboard is busy, the code is carefully written in a notebook. Not schematically, namely the code ready for transfer. Then, as soon as a fast and dirty coder copes with one task (it is assumed that he will be able to do this without external intervention), someone from the remaining two sits in his place, the coder goes thoughtfully to read the tour. The third participant at this moment discharges to watch the writing of the code - pair coding in sports programming is very useful. At the same time, this participant makes 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 to know what people decide in order not to go into the wrong steppe. At the same time, a personal queue of writing tasks in a team is drawn up, based on the complexity / knowledge / wishes.
While there is something to solve, they decide exactly what they have :) Usually this 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 task of the first, manually calculating the result. If everything is bad and all the solved tasks are over, then the team sits down to storm. The technology of brainstorming is familiar to everyone, so I will not elaborate here.
When entering tasks in the “writing queue”, the following technology from team math tournaments is very useful. When someone in the head naturally gives birth to the correct and most good decision, he goes to the person who did not think about this task and explains the solution to the problem. It helps when eliminating delusions and lazhi.
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 hours cutoff, with all the advantages in the rating and proudly raised head. This we had only a couple-three training. And among Moscow and St. Petersburg teams is practiced in the quarterfinals =)
The second option is if there is still a lot of writing and there is not enough time. Then by voting on the team (about an hour before the end of the tour) it is decided which tasks to write, depending on their confidence and the likely speed of writing.
And the third way is “ballet”. When there are no ideas, and I want to do something. Then they begin to write various dirty head-on solutions, in the hope that the time limit will bypass us. Maybe even a circus.
So once on the CBOSS tour, we solved the problem of a binary search in the testing system. The task we wrote, and quite stupidly and in the forehead. For empirical reasons, it was suggested that if we don’t get stuck on the first ~ 2 millions, then nothing will break. Broken time limit. Put a limit of half a million - falls on accuracy. There was nothing to do, so we made a consistent approach to the solution. Have passed attempts from the 30th
While writing tours, various interesting and useful tricks are often used. Often, they look surprising to inexperienced teams, but are useful to everyone.
Many tasks are kosher to solve by preliminary miscalculation. As I wrote earlier, 5 minutes of the team’s work will allow solving the problem by the method
But often the task seems to be considered prekalkom or stupid in the forehead, but for the first there is not enough space in the code, and for the other - time-limit. Then you can use dirty hack number one.
Here is an example of a problem solved in this way. Kolya and I started solving it at the same time, he went by means of a matan, generated a tricky tablet and somehow from it calculated the solution at an arbitrary point. I acted straightforward, but no less creative. A cycle with a length of 100,000 in the allowed time is executed, and 1000 pre-calculated values ​​are included in the code. Thus, the grid of solutions was calculated, and then it was considered head-on from the nearest value. I coped faster, though the approach is much less scientific and scalable.
The technique that Dima Kovchin brought to our team. It is used mainly on integer problems. Quickly, a generator is written in 10 minutes that brazenly calculates the first values ​​of the 20 objective function. Then the best minds of the team sit down and try to reveal a general pattern using the method of glacial analysis. Often, the pattern of the first 2-3 values ​​may be erroneous, the values ​​of 20 already allow one to quite reliably believe a hypothesis. Miscalculation of hands on paper takes much more time. It is worth noting that the Newton method can be used to construct a curve of good order through any number of points, so you should not abuse the method.
I do not know how the commands of other universities, but we already have a proverb. We always write different 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 SIBSUTI, with whom our team constantly shared 1 place among the best KVN teams in ACM =), even for some time it was rumored that the NSU MOM and NSU NAN tasks in Excel solve and are sent to the testing system xls files . This, of course, is not the case, but it is better than simply to build max tests for bullying the task.
By a hint Orfest remembered that without Google it can be complicated. In large tournaments like the All-Siberian Olympiad, this luxury is, of course, no one will give into our hands, but at the same CBOSS it can be used without fail. In Google and Wikipedia, you can refresh the mathematical knowledge, so as not to bother with the conclusion of something that is not remembered offhand, and if you really really want to - go back to the finished algorithm. You should not consider this a panacea for all diseases, in many tournaments the external Internet is prohibited as such, but sometimes web services are useful. At least, even for the translation of incomprehensible words that may be significant in solving the problem. And at the stage of "ballet" it can come down to the next show.
About 3 years ago, our team solved some problem about the seating of elves in the Santa Claus team. It was already at the end of the tour, the degree of brain boiling 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 also moose in Lapland”. When the decision was made to look for an algorithm in Yandex, the collective mind gave birth to only such a request: "Elves are seated reindeer." The tour on this request was completed, and another cheerful moment was added to the track record of our team.
So far, alas, the topics about sports programming have dried up. If someone throws an idea about what you can write more, I will be very grateful.
I am waiting for comments from existing and former ACM-ovtsev, what new subtleties and methods can be gathered, because my last season is soon and I want to spend it extremely hard.
The first article is about drawing up 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.
')
Line-up
A team is three people. More - no way, less (according to the current rules) - too. Last season, Misha and I were ultimately asked to look for a third, or no one goes anywhere. Fortunately, Kohl 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 we did not qualify for the semifinals once again. This year we will try to fix the interaction in the team.
In the best teams, each participant individually can take the entire tour (or most of the tasks from it). In lower level teams, individual participants often specialize in specific topics. So we have almost all the geometry falls on Misha’s shoulders, and to solve the theory of numbers or which combinatorial fabrications no one forwards climbs me. So, due to the specialization on different topics, you can get a team that has total knowledge at the level of stronger teams in the personalities.
Usually there are 3 roles in a team - a coder, a mathematician and an algorithmist. Each of the participants must perform at least 2 of them, and ideally, all 3. But not all cases are perfect, so sometimes some participants do not write a single line of code during the tour, while others do not read half of the tasks, while the team reaches a good result. You should not abuse it, it is better to let everyone know everything =)
Tour start
10 minutes before the start of the team allowed to the computer. The fastest coder of the team gets behind the car and stuffs the templates in the languages ​​in which the letter is supposed to, adjusts the IDE (setting up your favorite perspective in Eclipse from scratch is already so worked out that it almost comes to automatism). The rest prepare the workplace - pens, notepads, nerves.
Tasks appear, usually on paper. Ideally - 3 copies, one per participant, but maybe less. Two - at least for convenient work. Then the tasks are eagerly snapped up by two team members who are not burdened with the keyboard at the moment and begin to look for a “comforter”. In 90% of the tours that I wrote, there is at least one task that must be solved immediately, quickly, without options and on the first attempt. After finding it (about 2 minutes), the algorithmist sits down at the coder and in general terms introduces him to the task, with the gist - so that he doesn't bother to read and translate the text (in most olympiads, the text is in English, so it’s better to avoid unnecessary plugs). Next, the coder is left alone with the keyboard and the condition of this task, and the other two rush to disassemble the entire tour.
The guys read the entire tour and are looking for a task that they will write next. Further, while the keyboard is busy, the code is carefully written in a notebook. Not schematically, namely the code ready for transfer. Then, as soon as a fast and dirty coder copes with one task (it is assumed that he will be able to do this without external intervention), someone from the remaining two sits in his place, the coder goes thoughtfully to read the tour. The third participant at this moment discharges to watch the writing of the code - pair coding in sports programming is very useful. At the same time, this participant makes 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 to know what people decide in order not to go into the wrong steppe. At the same time, a personal queue of writing tasks in a team is drawn up, based on the complexity / knowledge / wishes.
Mid Tour
While there is something to solve, they decide exactly what they have :) Usually this 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 task of the first, manually calculating the result. If everything is bad and all the solved tasks are over, then the team sits down to storm. The technology of brainstorming is familiar to everyone, so I will not elaborate here.
When entering tasks in the “writing queue”, the following technology from team math tournaments is very useful. When someone in the head naturally gives birth to the correct and most good decision, he goes to the person who did not think about this task and explains the solution to the problem. It helps when eliminating delusions and lazhi.
End of the tour
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 hours cutoff, with all the advantages in the rating and proudly raised head. This we had only a couple-three training. And among Moscow and St. Petersburg teams is practiced in the quarterfinals =)
The second option is if there is still a lot of writing and there is not enough time. Then by voting on the team (about an hour before the end of the tour) it is decided which tasks to write, depending on their confidence and the likely speed of writing.
And the third way is “ballet”. When there are no ideas, and I want to do something. Then they begin to write various dirty head-on solutions, in the hope that the time limit will bypass us. Maybe even a circus.
So once on the CBOSS tour, we solved the problem of a binary search in the testing system. The task we wrote, and quite stupidly and in the forehead. For empirical reasons, it was suggested that if we don’t get stuck on the first ~ 2 millions, then nothing will break. Broken time limit. Put a limit of half a million - falls on accuracy. There was nothing to do, so we made a consistent approach to the solution. Have passed attempts from the 30th
Grimaces and jumps
While writing tours, various interesting and useful tricks are often used. Often, they look surprising to inexperienced teams, but are useful to everyone.
Sly prekalk
Many tasks are kosher to solve by preliminary miscalculation. As I wrote earlier, 5 minutes of the team’s work will allow solving the problem by the method
read(a); write (res[a]);But often the task seems to be considered prekalkom or stupid in the forehead, but for the first there is not enough space in the code, and for the other - time-limit. Then you can use dirty hack number one.
Here is an example of a problem solved in this way. Kolya and I started solving it at the same time, he went by means of a matan, generated a tricky tablet and somehow from it calculated the solution at an arbitrary point. I acted straightforward, but no less creative. A cycle with a length of 100,000 in the allowed time is executed, and 1000 pre-calculated values ​​are included in the code. Thus, the grid of solutions was calculated, and then it was considered head-on from the nearest value. I coped faster, though the approach is much less scientific and scalable.
Goodness generator
The technique that Dima Kovchin brought to our team. It is used mainly on integer problems. Quickly, a generator is written in 10 minutes that brazenly calculates the first values ​​of the 20 objective function. Then the best minds of the team sit down and try to reveal a general pattern using the method of glacial analysis. Often, the pattern of the first 2-3 values ​​may be erroneous, the values ​​of 20 already allow one to quite reliably believe a hypothesis. Miscalculation of hands on paper takes much more time. It is worth noting that the Newton method can be used to construct a curve of good order through any number of points, so you should not abuse the method.
Excel is the best friend of the programmer
I do not know how the commands of other universities, but we already have a proverb. We always write different 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 SIBSUTI, with whom our team constantly shared 1 place among the best KVN teams in ACM =), even for some time it was rumored that the NSU MOM and NSU NAN tasks in Excel solve and are sent to the testing system xls files . This, of course, is not the case, but it is better than simply to build max tests for bullying the task.
Figured googling
By a hint Orfest remembered that without Google it can be complicated. In large tournaments like the All-Siberian Olympiad, this luxury is, of course, no one will give into our hands, but at the same CBOSS it can be used without fail. In Google and Wikipedia, you can refresh the mathematical knowledge, so as not to bother with the conclusion of something that is not remembered offhand, and if you really really want to - go back to the finished algorithm. You should not consider this a panacea for all diseases, in many tournaments the external Internet is prohibited as such, but sometimes web services are useful. At least, even for the translation of incomprehensible words that may be significant in solving the problem. And at the stage of "ballet" it can come down to the next show.
About 3 years ago, our team solved some problem about the seating of elves in the Santa Claus team. It was already at the end of the tour, the degree of brain boiling 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 also moose in Lapland”. When the decision was made to look for an algorithm in Yandex, the collective mind gave birth to only such a request: "Elves are seated reindeer." The tour on this request was completed, and another cheerful moment was added to the track record of our team.
So far, alas, the topics about sports programming have dried up. If someone throws an idea about what you can write more, I will be very grateful.
Source: https://habr.com/ru/post/64144/
All Articles