The results of the Olympiad on programming among schoolchildren
From 16 to 22 January, the III International Programming Contest among schoolchildren was held at Moscow University of Steel and Alloys. The event was organized by NITU "MISiS" and Cognitive Technologies. Frankly, it took almost three weeks to persuade the organizers to open at least a couple of conditions for the tasks proposed at the event and to get permission to publish their analysis.
Believe me, it was not easy. Although they can be understood.
As is known, the compilation of the conditions of the tasks is considered one of the most difficult stages of the preparation of programming competitions.
Upon their completion, they are usually used during the training of teams, as well as external contests.
Groups of trainers from different universities regularly exchange contests.
In general, the reuse of tasks is taken in the olympiad movement.
')
But first things first.
More than 70 schoolchildren from 8 to 11 classes from different regions of Russia and the Republic of Belarus who successfully participated in the correspondence round of the Olympiad were invited to participate in the full-time round of the Olympiad.
Recall the format of the event implies two phases: absentee (held in the fall; last year it took place on November 16, 2014; you can learn more about it: http://ug.ru/news/13584 ) and in-person (held in early January) .
At the same time, the organizers note that they do not rely on geniuses and geeks from special schools in Moscow and St. Petersburg.
The purpose of the Olympiad is to search for promising and talented children, mainly from the regions of Russia and the near abroad, who want to get a good education and realize themselves in the field of information technology.
Starting with the 2nd course of study, students of the Department of Engineering Cybernetics practice in university laboratories and the best of them are invited to take part in real research and applied projects in the field of AI implemented jointly with Cognitive Technologies.
Full-time tour of the Olympiad was conducted according to the following rules.
When ranking participants and identifying winners, the main factor was the number of solved problems.
When they were equal, the amount of time from the beginning of the tournament to the decision-making system for solving all solved problems, plus 20 minutes penalty for each rejected decision was taken into account.
Penalties for wrong decisions were imposed only on those tasks that were ultimately accepted by the testing system.
For automated solution testing, the ejudge system was used ( https://ejudge.ru/ ).
As a result, no one solved the 10 tasks.
The winner of the competition was the silver medalist of the International Olympiad in Informatics (International Olympiad in Informatics) Alexey Vistyazhik from Ivye secondary school of the Republic of Belarus, who solved 9 problems.
With a noticeable separation from him (5 solved problems), Alexander Zoykin (Orenburg) and Yury Bondarchuk (Belarus) shared the second place.
Pavel Beschetnov (Togliati), Dmitry Galov (Moscow) and Alexey Dovgal (Belarus) were in third place with four solved tasks.
16 schoolchildren recognized as winners and prize-winners received valuable prizes and additional points to the overall results of the Unified State Exam when entering NITU “MISiS”.
The greatest difficulty was caused by task I. “Mirror in the corridor”.
Surprisingly, the participants did not do well with the geometry problems.
The organizers considered them relatively simple.
Time limit: 0.5 seconds
Memory Limit: 64 Megabytes
Input: Standard input stream (stdin)
Output: Standard Output Stream (stdout)
Petya caught a cold in bed, when suddenly someone opened the door. Petya was too lazy to get up and he looked in the mirror to see who came. The coordinates of the person entered are known (it can be considered a material point), it is necessary to find out whether Petya will be able to see the reflection of the person who entered in the mirror. The mirror has the shape of a circle with the center at the origin of coordinates and is located in the plane ax + by + cz = 0. Petya can also be considered a material point. It is guaranteed that Peter and the stranger do not lie in the plane of the mirror and that Peter always sees the reflecting side of the mirror. If the image falls on the border of the mirror, then Petya sees the person who has entered. Since both Petya and the one who has entered can be considered material points, Petya can see the reflection of the one who has entered, both through the one who has entered and through his own reflection.
The first line contains a natural number n - the number of tests not exceeding 500. Each test consists of four lines. The first of them recorded the radius of the mirror. In the second - the coefficients a , b , c . Next come the coordinates of Petit. The fourth line of each test contains the coordinates of the person logged in. All numbers are integers and do not exceed 1000 by absolute value.
Print n lines. In each line - the answer to the next test. “Yes” if Peter sees the person logged in and “No” otherwise.
Reflect Petya relative to the plane of the mirror.
Let's draw a straight line through the reflected Petya and the stranger and cross it with the plane of the mirror. Let's see if the intersection point is in the mirror. Consider separately the case when Peter and the stranger lie on opposite sides of the mirror - then Peter does not see him exactly.
Task text H "Axis of symmetry"
Time limit: 1 second
Memory Limit: 64 Megabytes
Input: Standard input stream (stdin)
Output: Standard Output Stream (stdout)
Friends brought from a trip to China Vova as a gift set for making a kite.
The next day, the weather was good, and he decided to glue the snake and run it.
Instructions for making, of course, was only in Chinese, so Vova decided that he would understand without it.
A little fiddling, he built a snake in the form of a flat polygon, it remained only to glue the tail to it.
And here Vova had to think about to which point of the border of the polygon the tail of the serpent should be glued.
Intuition told him that in order for the flight of the snake to be stable, its tail must lie on some axis of symmetry of the polygon.
The pictures below show two kites flying steadily and all options for attaching the tail to them,
as well as one kite flying unstable.
How many points are there on the border of a polygon, such that, if you stick a tail to them, the result is a kite flying steadily?
Initial data
The first line contains a single integer N (3 ≤ N ≤ 1000). The following N lines contain two integers separated by a space, not exceeding modulo 10000 - the coordinates of the vertices of the polygon in traversal order.
Result
Print a single number - the number of points on the border of the polygon, to which you can glue the tail of a snake.
The axis of symmetry of a polygon can pass only through its vertices and through the middle of its sides.
We write down the coordinates of the 2N points — the vertices of the polygon and the midpoints of its sides in traversal order and number them from 0 to 2N-1 .
Consider all applicants for the axis of symmetry - straight lines passing through the points i and i + N, 0 ≤ i ≤ N -1.
In order for such a straight line to be the axis of symmetry of a polygon, it is necessary and sufficient that each pair of points i + j and (ij) mod 2N, 1 ≤ j ≤ N-1, be located symmetrically with respect to this straight line.
It is easiest to check the symmetry of the points C and D with respect to the straight line AB , having established that the straight lines AB and CD are orthogonal and their intersection divides the segment CD in half.
In order not to go beyond the limits of the calculation with integers, it is enough to increase all the coordinates of the points by 4 times.
The complexity of this solution is O (N 2 ).
Two participants A.Vistyazh and P.Beschetnov coped with the task H “Axis of symmetry”.
During the full-time tour for children, the winter school of programming was also conducted.
Within the framework of the competition, well-known scientists and IT specialists gave lectures, held master classes and training contests.
Participation in the winter school and the in-person round of the Programming Olympiad was free for invited participants. They were provided with transfer, food and accommodation.
Each participant was greeted at the station and escorted to the venue of events. For the duration of their stay, professional counselors who had been trained in the counseling school by the organized tourist company OST-WEST worked with schoolchildren.
Tasks and tests for the face-to-face tour of the Olympiad were developed by a team of sports programming coaches at NITU “MISiS” and Cognitive Technologies headed by a corresponding member. RAS V.L. Arlazarov Among them: PhD. I.A. Faradzhev, Ph.D. V.V. Postnikov, Ph.D. Ib Mamay, V.V. Sokolov. As well as graduate students of NITU "MISiS": K. Bulatov, T. Chernov and N. Skoryukina.
Believe me, it was not easy. Although they can be understood.
As is known, the compilation of the conditions of the tasks is considered one of the most difficult stages of the preparation of programming competitions.
Upon their completion, they are usually used during the training of teams, as well as external contests.
Groups of trainers from different universities regularly exchange contests.
In general, the reuse of tasks is taken in the olympiad movement.
')
But first things first.
More than 70 schoolchildren from 8 to 11 classes from different regions of Russia and the Republic of Belarus who successfully participated in the correspondence round of the Olympiad were invited to participate in the full-time round of the Olympiad.
Recall the format of the event implies two phases: absentee (held in the fall; last year it took place on November 16, 2014; you can learn more about it: http://ug.ru/news/13584 ) and in-person (held in early January) .
At the same time, the organizers note that they do not rely on geniuses and geeks from special schools in Moscow and St. Petersburg.
The purpose of the Olympiad is to search for promising and talented children, mainly from the regions of Russia and the near abroad, who want to get a good education and realize themselves in the field of information technology.
Starting with the 2nd course of study, students of the Department of Engineering Cybernetics practice in university laboratories and the best of them are invited to take part in real research and applied projects in the field of AI implemented jointly with Cognitive Technologies.
Full-time tour of the Olympiad was conducted according to the following rules.
- Duration: 5 hours .
- Number of tasks: 10 .
- Working language: Russian .
When ranking participants and identifying winners, the main factor was the number of solved problems.
When they were equal, the amount of time from the beginning of the tournament to the decision-making system for solving all solved problems, plus 20 minutes penalty for each rejected decision was taken into account.
Penalties for wrong decisions were imposed only on those tasks that were ultimately accepted by the testing system.
For automated solution testing, the ejudge system was used ( https://ejudge.ru/ ).
As a result, no one solved the 10 tasks.
The winner of the competition was the silver medalist of the International Olympiad in Informatics (International Olympiad in Informatics) Alexey Vistyazhik from Ivye secondary school of the Republic of Belarus, who solved 9 problems.
With a noticeable separation from him (5 solved problems), Alexander Zoykin (Orenburg) and Yury Bondarchuk (Belarus) shared the second place.
Pavel Beschetnov (Togliati), Dmitry Galov (Moscow) and Alexey Dovgal (Belarus) were in third place with four solved tasks.
16 schoolchildren recognized as winners and prize-winners received valuable prizes and additional points to the overall results of the Unified State Exam when entering NITU “MISiS”.
The greatest difficulty was caused by task I. “Mirror in the corridor”.
Surprisingly, the participants did not do well with the geometry problems.
The organizers considered them relatively simple.
Task I Text
Time limit: 0.5 seconds
Memory Limit: 64 Megabytes
Input: Standard input stream (stdin)
Output: Standard Output Stream (stdout)
Petya caught a cold in bed, when suddenly someone opened the door. Petya was too lazy to get up and he looked in the mirror to see who came. The coordinates of the person entered are known (it can be considered a material point), it is necessary to find out whether Petya will be able to see the reflection of the person who entered in the mirror. The mirror has the shape of a circle with the center at the origin of coordinates and is located in the plane ax + by + cz = 0. Petya can also be considered a material point. It is guaranteed that Peter and the stranger do not lie in the plane of the mirror and that Peter always sees the reflecting side of the mirror. If the image falls on the border of the mirror, then Petya sees the person who has entered. Since both Petya and the one who has entered can be considered material points, Petya can see the reflection of the one who has entered, both through the one who has entered and through his own reflection.
Initial data
The first line contains a natural number n - the number of tests not exceeding 500. Each test consists of four lines. The first of them recorded the radius of the mirror. In the second - the coefficients a , b , c . Next come the coordinates of Petit. The fourth line of each test contains the coordinates of the person logged in. All numbers are integers and do not exceed 1000 by absolute value.
Result
Print n lines. In each line - the answer to the next test. “Yes” if Peter sees the person logged in and “No” otherwise.
Example
| Initial data | Result |
|---|---|
| 2 2 0 1 0 0 2 0 0 1 0 one 0 1 0 2 -2 0 1 1 0 | Yes No |
Analysis of the task I "Mirror in the corridor"
Reflect Petya relative to the plane of the mirror.
Let's draw a straight line through the reflected Petya and the stranger and cross it with the plane of the mirror. Let's see if the intersection point is in the mirror. Consider separately the case when Peter and the stranger lie on opposite sides of the mirror - then Peter does not see him exactly.
Task text H "Axis of symmetry"
Time limit: 1 second
Memory Limit: 64 Megabytes
Input: Standard input stream (stdin)
Output: Standard Output Stream (stdout)
Friends brought from a trip to China Vova as a gift set for making a kite.
The next day, the weather was good, and he decided to glue the snake and run it.
Instructions for making, of course, was only in Chinese, so Vova decided that he would understand without it.
A little fiddling, he built a snake in the form of a flat polygon, it remained only to glue the tail to it.
And here Vova had to think about to which point of the border of the polygon the tail of the serpent should be glued.
Intuition told him that in order for the flight of the snake to be stable, its tail must lie on some axis of symmetry of the polygon.
The pictures below show two kites flying steadily and all options for attaching the tail to them,
as well as one kite flying unstable.
How many points are there on the border of a polygon, such that, if you stick a tail to them, the result is a kite flying steadily?
Initial data
The first line contains a single integer N (3 ≤ N ≤ 1000). The following N lines contain two integers separated by a space, not exceeding modulo 10000 - the coordinates of the vertices of the polygon in traversal order.
Result
Print a single number - the number of points on the border of the polygon, to which you can glue the tail of a snake.
Example
| Initial data | Result |
|---|---|
| 6 3 3 6 2 6 -1 3 -2 0 -1 0 2 | four |
| 3 -2 2 2 4 0 0 | 2 |
| four 0 6 6 0 0 -3 -20 | 0 |
Analysis of task H "Axis of symmetry"
The axis of symmetry of a polygon can pass only through its vertices and through the middle of its sides.
We write down the coordinates of the 2N points — the vertices of the polygon and the midpoints of its sides in traversal order and number them from 0 to 2N-1 .
Consider all applicants for the axis of symmetry - straight lines passing through the points i and i + N, 0 ≤ i ≤ N -1.
In order for such a straight line to be the axis of symmetry of a polygon, it is necessary and sufficient that each pair of points i + j and (ij) mod 2N, 1 ≤ j ≤ N-1, be located symmetrically with respect to this straight line.
It is easiest to check the symmetry of the points C and D with respect to the straight line AB , having established that the straight lines AB and CD are orthogonal and their intersection divides the segment CD in half.
In order not to go beyond the limits of the calculation with integers, it is enough to increase all the coordinates of the points by 4 times.
The complexity of this solution is O (N 2 ).
Two participants A.Vistyazh and P.Beschetnov coped with the task H “Axis of symmetry”.
Winter school
During the full-time tour for children, the winter school of programming was also conducted.
Within the framework of the competition, well-known scientists and IT specialists gave lectures, held master classes and training contests.
Participation in the winter school and the in-person round of the Programming Olympiad was free for invited participants. They were provided with transfer, food and accommodation.
Each participant was greeted at the station and escorted to the venue of events. For the duration of their stay, professional counselors who had been trained in the counseling school by the organized tourist company OST-WEST worked with schoolchildren.
Tasks and tests for the face-to-face tour of the Olympiad were developed by a team of sports programming coaches at NITU “MISiS” and Cognitive Technologies headed by a corresponding member. RAS V.L. Arlazarov Among them: PhD. I.A. Faradzhev, Ph.D. V.V. Postnikov, Ph.D. Ib Mamay, V.V. Sokolov. As well as graduate students of NITU "MISiS": K. Bulatov, T. Chernov and N. Skoryukina.
Source: https://habr.com/ru/post/250349/
All Articles