Конкурси, олимпиади, състезания
АНАЛИЗ НА НАЦИОНАЛНОТО ОНЛАЙН СЪСТЕЗАНИЕ ПО ИНФОРМАТИКА „Д-Р МЛАДЕН МАНЕВ“
Резюме. Тази статия описва процеса на провеждане на националното онлайн състезание по информатика в памет на д-р Младен Манев. Описанието включва някои важни технически и научни аспекти съответно на състезателната система и на задачите. Представеният анализ на събраните данни по време на състезанието, като статистика за участниците, сложност на задачите, резултати и системно натоварване, е използван за оценка степента на постигане на заложените цели.
Ключови думи: състезание; информатика; онлайн.
I. Представяне на състезанието
Състезанието е посветено на Младен Манев (1970 − 2017) – преподавател с дългогодишен принос към развитието на цялата българска състезателна информатика, а също и подготвил много ученици от ПМГ „Акад. Иван Гюзелев“ – Габрово. Идеята за създаване на това състезание възниква в Съюза на математиците в България и през есента на 2018 г. Бе проведено пилотно пробно издание за ученици от VI клас. През следващата година се състоя първото издание за всички възрастови групи. Настоящата статия анализира второто издание, проведено на 10 май 2020 г. с начало 9 часа. Организатор на състезанието беше ПМГ „Акад. Иван Гюзелев“ – Габрово. Журито се състоеше от Цветана Кюмюрджиева, Емил Келеведжиев, Зорница Дженкова, Галя Неделчева, Ивайло Карабойков, Пламен Динев и Добрин Башев. За участие бяха поканени всички ученици, получили ненулев брой точки на областния кръг на Националната олимпиада по информатика. Състезанието беше проведено със средствата на състезателната система (CMS), използвана на всички присъствени национални състезания по състезателно програмиране за ученици. Към момента това е единственото ежегодно онлайн състезание в България, което съответства на формата на Националната олимпиада. Пълна информация за състезанието (условия на задачите, авторски решения, тестове за оценяване, класиране и решения на състезателите) е публикувана в сайта на състезанието: https://info-gabrovo.com/
II. Подготовка на състезанието
Подготовката на състезанието може да бъде формално разделена на две части – научна (поверена на Добрин Башев) и техническа (поверена на Пламен Динев), които протичат паралелно и често зависят една от друга. Състезателната система беше разположена на 9 компютърни машини, работещи под „Линукс“, които осигуряваха необходимата изчислителна мощ за проверка на решенията в реално време. Спецификата на състезанието изискваше използването на различни защитни мерки – срещу хакерски атаки, изтичане на информация, прекъсване на електроподаването и др.
Следващата таблица съдържа някои важни характеристики на задачите от темите за различните възрастови групи, като например информация за фийдбека – процента тестове, резултатът от които е известен преди края на състезанието.
* задачи, в които тестовете са разделени в подзадачи ** задачи с релативно оценяване на тестовете
III. Анализ
A. Участие
184 от 309-те поканени ученици взеха участие в състезанието. На графиката може да се види разпределението на участниците по групи. Найвисок процент на участие се наблюдава в група D (69%), а най-нисък – в група А (54%). Очаквано най-голям брой участници има в младшата възрастова група Е.
Б. Резултати
Петте графики за всяка възрастова група показват връзката между точките, които даден участник е спечелил на състезанието, и неговата позиция в класирането на втория кръг на Националната олимпиада.
Резултатите в групите А и В показват, че задачите са били особено трудни. Повече от половината участници са получили по-малко от 100 точки. Също така се наблюдава остра разлика между първите състезатели и останалите.
Максималният резултат в група С е сравнително нисък – малко над 200 точки. Първите няколко състезатели в групата имат подобни резултати, което ги прави трудно различими. Въпреки това повече от половината участници са събрали повече от 100 точки.
Класиранията в групите D и Е са добре балансирани. Не е изненадващо, че се откриват голям брой размествания спрямо класирането от втория кръг на Националната олимпиада. Полученият висок коефициент на размествания (броят на действителните размествания, разделен на всички възможни такива) показва, че процесът на подготовката е продължил въпреки преминаването в дистанционна форма на обучение.
B. Трудност на задачите
В тази част ще класифицираме задачите според това колко участници са получили определен брой точки, попадащ в един от следните интервали: {0}, (0, 25), [25, 75], (75, 100), {100}. В графиките за всяка задача е показан средният брой точки.
На три от четирите задачи в група А е най-висок броят на участниците с 0 точки. Изключение прави задача cover, която имаше тривиално решение за 20 точки. Задача pebbles беше решена от трима участници, което заедно с високия среден брой точки я прави най-лесна в темата. За голяма изненада само 9 състезатели се опитаха да решат задача puzzle, въпреки възможността за частични решения.
Сложността на задачите в група B също беше висока, но имаше 15 пълни решения за разлика от само 5 в група А. Впечатление прави задача house, на която 2/3 от състезателите имат 0 точки. Това е обяснимо, защото повечето от тях за пръв път срещат интерактивна задача.
Преобладаващата част от състезателите в групи C, D и Е са получили между 25 и 75% от точките, което е задоволително. Въпреки това средните резултати в тези групи остават сравнително ниски. Няма нито един участник с пълен брой точки, но за щастие, процентът на получилите 0 точки също е доста нисък.
Участниците в група С бързо се ориентираха и разпознаха най-лесната задача (circles). Макар да беше най-трудна в темата, задачата (xoror) позволяваше да се получат голям брой точки с частични решения. Състезателите демонстрираха неочаквано слаби резултати на задача farm. В групите D и Е повечето състезатели са решили лесните задачи (snails и cats). Задачите, включващи повече програмиране (coins и distance), се оказаха по-трудни за състезателите от тези, изискваха по-нестандартни наблюдения (stable и recovery).
C. Системно натоварване
Измереното средно натоварване на системата по време на състезанието е 8,35%. Общото процесорно време, изразходвано за проверка на решенията на участниците, е 18521,3 s, или измерено в реално време – 26748,2 s. Следователно можем да изчислим ефективното системно натоварване чрез следната формула:
\(W=\cfrac{A}{T*N}=\cfrac{18521.3 s}{5h*28}=\cfrac{18521.3s}{18000s*28}=0.0367=3.67\%\)
където A е общото време, T е продължителността на състезанието и N – броят на използваните процесорни ядра. Останалото процесорно време (8,35% – 3,67% = 4,68%) отговаря за операциите, извършвани от състезателната система, операционната система и други процеси. Оттук, само около 43,9% от използваното време е пряко обвързано с изпълняването на решенията на състезателите. Този процент може да бъде по-висок, ако общото натоварване на системата е по-високо, защото останалото натоварване е сравнително константно.
D. Предадени решения
Следващата графика комбинира информация за използваното време за оценяване, броя на решенията и времевия лимит за всеки тест. Очевидно, времето за оценяване зависи от тези фактори, но освен това се влияе от броя на тестовете, който се различава значително за различните задачи (може да бъде намерен в част II). Трите задачи, които изискваха най-голямо процесорно време, са databases, farm и cover. Тестовите данни за всяка от тези задачи включваха близо 100 теста.
Последната графика показва броя състезатели, които са изпратили определен брой решения към състезателната система. Максималният допустим брой решения по всяка задача беше 30 за всяка задача. Само трима участници достигнаха това ограничение – съответно на задачи B1, B2 и C1. Най-голяма част от участниците използваха между 1 и 10 решения и общият брой решения беше 2633.
E. Нарушения на регламента
По време на планираната проверка след края на състезанието, журито откри случаи на нарушения на 10-а точка от регламента, която забранява споделяне на решения между състезателите. Проверката беше извършена върху всички предадени решения със скрипт, който търси прилики в кодовете на програмите. По този начин беше осигурена обективността на класирането от състезанието.
F. Разпределение на грамотите
*Показаният процент включва всички участници, които са получили това или по-високо отличие.
IV. Заключение
Въз основа на направения анализ можем да отбележим, че второто издание на състезанието беше изключително успешно. Заложените цели бяха постигнати и дори надхвърлени. Участниците имаха възможността да покажат уменията си, да се състезават със своите връстници, и се надяваме, че са научили нещо ново. Всички материали от състезанието са публикувани за свободен достъп на официалния уебсайт и биха били полезни за подготовка на бъдещи състезатели по информатика.