В проект перечня олимпиад школьников, которые могут давать льготы при поступлении в вуз, вновь добавлена олимпиада "Бельчонок", которая уже когда-то была в перечне, потом оттуда её убрали. Олимпиада проводится Сибирским федеральным университетом (Красноярск). Раньше это была "бланковая" олимпиада, то есть решения задач пишутся на бумаге, а потом проверяются жюри, хотя все широко известные олимпиады по информатике из перечня РСОШ проводятся исключительно в компьютерной форме. Мне стало интересно, что же представляет эта олимпиада сейчас, если её повторно включили в перечень. Благо сайт олимпиады http://dovuz.sfu-kras.ru/belchonok/ должен содержать массу материалов для анализа.

Конечно же, интерес прежде всего представляют задания заключительного этапа для 11 класса.

Первые четыре задачи — задачи по математике (безыдейная вычислительно муторная комбинаторика, задача на системы счисления, просто задача уровня маткружка и только в задаче 4 есть слово "бит", а сама задача в стиле известной задачи из ЕГЭ по информатике). Но есть и пятая задача, которая внешне выглядит, как адекватная задача по программированию. Приведём условие задачи полностью:

Дано N натуральных чисел. Написать программу, находящую минимальное натуральное число, не представимое в виде суммы никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза. Также сумма может состоять из одного числа.

Входные данные: первой строкой подается количество чисел N, второй строкой сами числа через пробел.

Выходные данные: искомое число.

Пример:

На первый взгляд задача уже выглядит похоже на задачу по программированию, достойную олимпиады. Правда, задача не блещет оригинальностью (хотя задания для заключительных этапов олимпиад РСОШ должны быть оригинальными), я даю эту задачу в школе 8-классникам (см. например задача Q). Это несложное упражнение на сортировку, нужно упорядочить список чисел, считать суммы всех чисел на префиксах, если какое-то число будет больше, чем сумма всех предыдущих чисел, увеличенная на 1, то ответом будет как раз сумма предыдущих чисел, увеличенная на 1. Сложность решения: O(N * log(N)). Вот, например, моё решение этой задачи. Обосновать этот алгоритм несложно индукцией по количеству чисел после их сортировки.

Предлагаемое авторами олимпиады решение этой задачи содержится в архиве с условиями в файле "Информатика_11_Ответы.pdf" на страницах 4-5. Во втором варианте заданий заключительного этапа эта задача точно такая же.

Для удобства скопировал код авторского решения на pastebin. Авторский алгоритм решения — посчитаем сумму всех чисел (sum), затем будем делать перебор по ответу: для каждого числа от 1 до sum будем проверять, можно ли представить его в виде подмножества данных чисел, что в свою очередь будем делать перебором всех подмножеств N чисел. То есть сложность авторского решения O(sum * N * 2^N).

Но если не получилось придумать хитрое решение с сортировкой, то можно один раз перебрать все подмножества и отметить в массиве числа, которые можно получить, затем найти первое неотмеченное число. Это будет решение сложности O(sum + 2^N). А можно решить эту задачу стандартным рюкзаком, это будет решение сложности O(sum * N). Составители заданий олимпиады, похоже, просто не в курсе вопросов сложности алгоритмов и написали самое худшее из очевидно приходящих в голову решений.

Также авторское решение содержит ошибки. В строке 7 объявлена переменная sum, которая не инициализируется. В строке 19 есть вывод переменной sum, но это не ответ, это отладочный вывод. Ответ выводится позже. Авторское решение всегда выводит два числа: сначала сумму всех чисел, потом ответ, то есть в тестирующей системе это всегда будет PE.

Итак, решение а) крайне неэффективно, б) содержит ошибку в реализации, в) содержит отладочный вывод в stdout.

Кроме того, решение ещё и крайне плохо написано.

Например, в строках 27-28 в цикле считается сумма в переменную sum1, а переменная sum1 обнуляется после этого цикла в строке 31. Так писать можно, но плохо, т.к. запутывает код. У своих учеников я такое решение не приму, инициализация должна быть сделана перед циклом. Об этом можно почитать в блоге Петра Калинина.

В строках 42-44 авторского решения нужно вывести найденный ответ i, он выводится, после чего делается break из цикла. А чтобы ответ не был выведен повторно ещё раз после цикла, увеличивается переменная flag1, которая проверяется после цикла (если flag1 == 0, то нужно выводить sum + 1). Вместо использования флагов и break в языке C++ нужно сделать return из середины функции main. Названия переменных (a, b, c, sum. sum1, flag, flag1) я бы никогда не принял у своих учеников.

Наконец, перебор всех подмножеств реализован путём увеличения двоичной записи числа, хранящегося в массиве b, это строки 32-38. Про битовые операции и как их использовать для перебора подмножеств авторы не в курсе, пишут сами алгоритм увеличения двоичной записи на единицу.

Ну и теперь переходим к самому главному — проверке решений. Уже понятно, что о тестирующей системе речи не идёт, как же они проверяли работы участников? Максимальный балл за вариант составляет 100, из них эта задача оценивается в 30 баллов. Кстати, в начале файла с решениями ошибка, там написано "Общее количество баллов 100. Решение первой задачи оценивается Жюри из 10 баллов, пятой задачи из 30 баллов и из 30 баллов остальных.", на самом деле задачи 2-4 оцениваются в 20 баллов, посчитайте сами сумму. Допустимо ли Жюри (не стесняющемуся писать себя с заглавной буквы) делать столь банальные ляпы в официальных текстах, равно как оставлять отладочный вывод в решении? Но все-таки посмотрим на то, как были проверены работы участников.

Вот работы победителей и призёров олимпиады. Работы учащихся 11-х классов начинаются со страницы 74.

Все более-менее адекватные решения задания 5, предложенные призёрами олимпиады, используют именно сортировку, но содержат ошибки в реализации и оценены не более, чем в 5 баллов из 30 возможных. До крайне неэффективного авторского решения задачи не додумался ни один из призеров олимпиады.

Но есть решение Кирилла Курдюкова (см. страницу 98), в котором я не нашёл никаких ошибок и изъянов. Вот это же решение на pastebin. Решение проходит все тесты в моей тестирующей системе и имеет сложность O(N*log(N)). То есть оно правильное, полное, имеет гораздо меньшую алгоритмическую сложность, короче и проще в реализации, то есть за него нужно ставить никак не меньше 30 баллов из 30 (а следовало бы поставить больше, ибо оно гораздо лучше авторского решения).

Жюри оценило это решение в 5 баллов из 30. Дальше есть ещё одна работа, в которой за это задание поставлено целых 10 баллов (во всех остальных работах — не более 5 баллов, как у Кирилла) — это работа Валерии Тягуновой (см. страницу 102). Это решение тоже с сортировкой, но в нём есть ошибки — выход за границу вектора, т.к. в векторе из n элементов идёт обращение по индексам от 1 до n, и также Валерия путает префиксный и постфиксный инкремент, она выводит sum++, а это не увеличенное значение sum, нужно вывести sum + 1. Во всём остальном — алгоритм решения такой же, как у Кирилла, но при наличии ошибок, оно оценено большим числом баллов, чем безошибочное решение Кирилла. Есть и другие решения этой задачи с правильной идеей, но с ошибками в реализации, за них тоже стоит 5 баллов.

Жюри олимпиады по-видимому не поняло правильное решение, которое написали эти школьники, а также не смогло найти банальные ошибки в программах на C++.

Выводы. Организаторы олимпиады "Бельчонок" по информатике не могут организовать автоматическую проверку решений, не понимают проблемы сложности решений, не могут придумать эффективное решение задачи, не могут реализовать решение без ошибок, не поняли правильного решения, найденного участниками, не могут найти ошибки в программах на C++, оценки за задания выставляются произвольным образом, допущены ляпы в текстах. При этом участники олимпиады являются куда более компетентными, чем жюри.

Ну и организационные вопросы. Заключительный этап проходит в разные дни в разных городах, разница по срокам в неделю. Но у организаторов олимпиады есть два варианта заданий для проведения заключительного этапа! В первом варианте составляем слова из слова "олимпиада", во втором варианте составляем слова из слова "информатика". В первом варианте закрашиваем 15 клеточек, во втором варианте — закрашиваем 11 клеточек точно такой же конструкцией. Ну а задача по программированию везде одинаковая. Вся страна мучается во время регионального этапа, когда Калининград начинает туры в 8 утра, а Чукотка и Камчатка должны детей держать взаперти час после окончания тура, пока Калиниград не запрёт своих участников, а на олимпиаде "Бельчонок" совсем не заморачиваясь просто дают одну и ту же задачу в разных городах через неделю.

Непонятно, зачем СФУ проводит такую олимпиаду и хочет учитывать её результаты при поступлении в вуз. Задания этой олимпиады ничем не лучше заданий ЕГЭ по информатике, а качество работы жюри просто неудовлетворительное. Не знаю, как в Красноярске проверяют ЕГЭ по информатике, но в ЕГЭ по крайней мере на полный балл ожидается именно наиболее эффективное решение, и качество составления заданий ЕГЭ и проработки критериев оценивания заведомо лучше, чем у олимпиады "Бельчонок".

Также отдельным вопросом является качество экспертизы олимпиад, проводимой РСОШ. Каждый год перечень олимпиад и их уровни вызывает недоумение. В перечень попадают олимпиады типа "Бельчонок", "Инфознайка" или "Надежда знергетики", хотя неадекватность проведения этих олимпиад видна после беглого изучения их заданий. Или повторяющаяся история с присвоением первого уровня олимпиаде "Информационные технологии", которая ну никак не дотягивает до других олимпиад РСОШ ни первого, ни второго уровня (в этом году в перечне нет олимпиад второго уровня по информатике, но в те годы, когда Всесибирская олимпиада школьников или олимпиада "Высшая проба" по информатике были второго уровня, олимпиада "Информационные технологии" всегда была первого уровня, хотя они совершенно несопоставимы по сложности заданий). На мой взгляд, "Информационным технологиям" нужно дать третий уровень, а то множество олимпиад по информатике, которым всем сейчас дали первый уровень, вполне можно разделить по сложности на первый и второй уровень. Нынче олимпиада "Информационные технологии" стала называться "Открытая олимпиада школьников", по видимому, чтобы её начали путать с достойнейшей "Открытой олимпиадой школьников по программированию".

Или олимпиада "Надежда энергетики", которую то включают в перечень, то выкидывают. Тут достаточно бегло взглянуть на задания, авторские решения, критерии проверки и работы призеров. Это тоже бланковая олимпиада, но тут сложно понять, чего же жюри хочет получить от участников? В заданиях написано, что "Для заданий 1, 2, 4, 5 требуется разработать алгоритм на языке блок-схем, псевдокоде или естественном языке". Да, именно так, не программу, а алгоритм! За разработанную программу, оказываются, снижают баллы — это в критериях написано: "Если представлена правильная реализация на языке программирования вместо разработки алгоритма, то максимальная оценка – 7 баллов". И, действительно, снижают: раз, два, три.

Откроем авторские решения, чтобы понять, что такое "алгоритм", который должен быть оценён максимальным баллом, в отличие от программы. А там написано несколько слов с описанием решения а дальше текст программы на русском алгоритмическом языке, известном как "Кумир". Это вполне себе язык программирования, у него даже есть консольный компилятор, который можно прикрутить к тестирующей системе. Но с точки зрения жюри программа на Кумире — это разработанный "алгоритм", а программа на другом языке программирования алгоритмом не является, и полный балл не получит. Те, кто рисуют блок-схемы — молодцы, они алгоритм разработали, а те, кто программу написал — нет, они алгоритм не разработали.

Благодаря требованиям к олимпиадам в части публикации заданий, критериев оценивания, работ победителей и призёров, все могут оценить достоинства той или иной олимпиады, квалификацию методической комиссии и жюри олимпиады. Но непонятно, как олимпиады "Бельчонок" и "Надежда энергетики" прошли экспертизу РСОШ. Не следует ли сделать открытыми ещё и результаты экспертизы, чтобы все желающие могли ознакомиться ещё и с мнением экспертов относительно той или иной олимпиады?