Форум DL

Мой профиль

Областная и республиканская олимпиады оказывают существенное влияние на отбор сборных Гомельской области и Республики Беларусь соответственно, кроме того (и это мне кажется еще более важным) - они ЗАДАЮТ направление - чему обучаться в рамках подготовки к последующим олимпиадам соответствующего ранга.

Естественно возникают вопросы:

Какими должны быть олимпиадные задания для областных и республиканских олимпиад?
- по объему, содержанию, структуре, количеству тестов, их разбаловке. Что эти тесты должны проверять.
- Какие темы должны быть охвачены?

Мой профиль

Вот мое мнение (очень надеюсь почитать здесь мнения и других людей)
Сначала о тематике
Здесь есть несколько отправных точек:
1) Можно опираться на международные олимпиады прошлых лет и на основании этого делать выводы какие темы превалируют
- динамическое программирование
- графы
- геометрия
...
2) Есть IOI Syllabus - то есть как раз список тем, которые включены (и исключены) в перечень теоретической подготовки участника IOI.
3) Есть Российский теор-минимум

В то же время, мне кажется, задачи должны быть НЕОЖИДАННЫМИ - то есть не просто сообразил, какая теория и пиши ...
Более того, в идеале задачи должны быть такими, что никакая старая теория не подойдет - нужно ПРИДУМЫВАТЬ новую. Или писать эвристические алгоритмы.

"Случайно в кустах оказался рояль ..."
Сейчас перевожу Usaco 2006 October Gold.
В двух задачах из трех встречается фраза

It is not promised that it is possible to write a program that can
solve a large case within the allotted time limit.

Что означает примерно следующее:

"Не гарантируется, что возможно написать программу, которая сможет решить самый большой тест в отведенное время."

Хотя очевидно, чем больше человек знает теории, тем больше шансов свести задачу к ней или ее производным, равно как и тем больше шансов придумать новую теорию.

Что касается тестов, то я думаю требования здесь такие
- тесты должны быть полными, соответствовать условиям задачи
- и желательно чтобы они были не больше 100 Мгбт

- тесты должны обеспечивать ПРОПОРЦИОНАЛЬНОЕ качеству решения количество баллов

Качество задач также обеспечивается наличием АВТОРСКИХ и ПЕРЕКРЕСТНЫХ решений, неполных авторских решений (для более точного выставления разбалловки) а также ОПИСАНИЙ авторских полных и неполных решений

Все это может быть обеспечено, по-моему, только в том случае, если задачи готовятся БЫВШИМИ победителями олимпиад - республиканских или международных.

Мой профиль

В Литве начал издаваться на английском языке журнал "Olympiads in Informatics"
http://www.i-journals.org/olympiads_in_informatics

Первый выпуск журнала - материалы конференции IOI 2007.
Среди прочих, там опубликована статья польских авторов об организации их национальных олимпиад и подготовке задач.
Далее приводятся переводы выдержек из нее, посвященные подготовке задач к олимпиадам.

"2. Подготовка задач"

Основная цель подготовки задач - обеспечить их высокое качество. Но что это значит? Что делает задачу хорошей? Мы рассматриваем следующие аспекты задач:

Формулировка задачи - она должна быть понятной, современной и не очень длинной

Различия в уровне подготовки контестантов- должно существовать множество способов решения задачи различной сложности, более того, должна быть возможность различать эти решения во время тестирования

Полнота анализа- анализ задачи должен принимать во внимание широкий спектр решений, покрывающий все способы решения задачи доступные контестантам, и различные языки программирования, включая С++/STL

Полнота тестирования- тесты должны различать правильные и неправильные решения, они также должны различать классы решений, вне зависимости от использованных участниками языков программирования (и возможности использовать STL)

Корректность - все авторские решения должны соответствовать спецификациям ввода-вывода и должны формировать корректный вывод. В случае необходимости, должен быть и чекер для проверки результатов.

Далее описывается процесс подготовки задач к Польским олимпиадам по информатике, обеспечивающий достижение поставленных целей.

Процесс подготовки задач состоит из следующих фаз: обзор идей задачи, формулировка, анализ, верификация, калибровка.

Обзор идей задачи

Изначально мы рассматриваем только идею задачи. Она только определяет алгоритмическую проблему, которую необходимо решить. Когда мы рассматриваем идею задачи, мы должны ответить на следующие вопросы:
- Может ли задача быть сформулирована кратким и исчерпывающим способом? Если он слишком сложна в формулировке, или требует объяснения множества терминов, она не подходит для олимпиады
- Является ли задача "стандартной"? Если да, то она тестирует знание конкретного алгоритма, но не креативности, следовательно она не подходит.
- Не является ли задача известной (обозревателю хотя бы)?
- Может ли она быть решена за полиномиальное время? Если нет, то ее скорей всего будет невозможно протестировать в разумное время. Однако возможны исключения.
- Существует ли множество способов решения задачи различной сложности и производительности? Если нет, то вероятней всего она не подходит для олимпиады. Она также не подходит, если невозможно различить тестами различные классы решений.
- Может ли она быть решена контестантами? На этот вопрос нет универстального ответа. Наши требования к контестантам достаточно высоки (на уровне знания учебника Кормена)

Формулировка задачи

При формулировке задачи все элементы, пропущенные в идее задачи должны быть добавлены. В частности, нужно добавить краткую легенду, дабы сделать задачу более привлекательной. Язык должен быть простой. Необходимо избегать сложных предложений. Все новые понятия должны быть объяснены до их использования. Специфкации ввода и вывода должны быть точными (можно без указания предельных размеров). Предпочтительно, чтобы вывод был коротким, но трудным к угадыванию (не просто да/нет, а целое число). Формулировка должна содержать пример, желательно с рисунком. Условие должно помещаться на одной или двух страницах. Три страницы - абсолютный предел. Формулировка задачи должна сопровождаться кратким описанием (один или два параграфа) авторского решения - оно будет рассматриваться на стадии анализа задачи.

Анализ задачи

Анализ задачи - это самая трудоемкая часть подготовки. Результат - документ - отчет о проведенном анализе, некоторое количество программ и тесты. В случае необходимости в формулировку задачи вносятся изменения и добавления (например вносятся или уточняются предельные размеры данных).

Отчет об анализе - внутренний документ, поэтому он может быть написан на профессиональном языке. Он должен обсуждать различные решения: оптимальное решение (с точки зрения контестантов), другие возможные решения и несколько некорректных решений, которые можно ожидать от участников. Он также должен обсуждать все решения, предложенные автором задачи, но может быть не ограничен только этими решениями. Описание решения для учеников делается отдельно.

Все корректные решения должны быть реализованы и на С/С++ и на Паскале. Более того, если возможно решение, использующее библиотеку STL, то для С должны быть разработаны ОБА решения - с использованием STL и без использования STL. Это необходимо для того, чтобы знать точно ВРЕМЯ работы соответствующих программ. Для неполных решений достаточно разрабатывать решения на любом одном из языков.

Для "пакетных" (обычных) задач готовятся тесты (от 10 до 20 штук). Главная цель тестов - различать правильные и неправильные решения. Однако они также должны различать и классы корректных решений, которые различаются в сложности реализации. Как правило, у нас время на тесты выставляется так, что решения, которые работают не более чем в два раза раза медленнее авторских, получают полный балл. Необходимо обеспечивать, чтобы результат тестирования не зависел от выбранного языка программирования или использования STL.
30%-60% тестов должны проверять корректность решения. Иными словами корректные, но не эффективные решения (отрабатывающие в разумное время) должны брать 30-60% баллов. Остальные баллы определяются эффективностью решения. Выполнение всех этих требований достигается разумным сочетанием ограничений на входные данные, оперативную память и время на тест. В случае необходимости, тесты могут группироваться.

Тесты могут быть подготовлены либо в форме файлов, либо в форме программ, которые их генерируют. Однако такие программы должны при каждом запуске генерировать ОДНИ и ТЕ ЖЕ тесты. Тесты должны сопровождаться программой, которая проверяет их корректность.

Верификация

Основная цель этапа верификации - обеспечение корректности. Есть два способа достижения этой цели - инспекция отчета об анализе и "перекрестные" решения и тесты.

Калибровка

- На этом этапе выставляется ТОЧНОЕ время на тест, запуском авторских решений на машине, на которой предполагается тестирование соревнования.

Мой профиль

В том же сборнике своим опытом проведения олимпиад и подготовки задач делятся и словаки.
Они до сих пор используют не только практические, но и теоретические туры на олимпиадах всех уровней вплоть до национальной. Ниже приводятся их аргументы в пользу такого подхода.

"... Мы твердо убеждены, что процесс мышления (иными словами процесс решения задач)- это наиболее важное умение, которое мы хотим видеть в наших контестантах. Именно это понадобится им в будущем, если они выберут компьютерные технологии в качестве профессии. С нашей точки зрения IOI имеет нынешний практический формат только по причине невозможности провести (проверить)теоретический тур в рамках времени, отводимого на IOI. Мы в состоянии провести (проверить) теоретический тур для Словакии - и потому проводим его. И с нашей точки зрения такие соревнования гораздо полезнее для контестантов."

Мой профиль

В связи с катастрофически низкими результатами на городской олимпиаде 2006 года, предлагается изменить состав задач для школьной и городской олимпиад 2007 года (старшая группа: 9-11 класс). Вместо трех задач уровня республиканских олимпиад, предъявить 11 задач, на следующие темы с указанной разбалловкой:

Баллы  Тема 
   5     1. Одномерный массив
  10     2. Двумерный массив
  15     3. Геометрия
  20     4. Строки
  50     5. Очередь
  50     6. Рекурсия
  50     7. Рекуррентные соотношения
  50     8. Графы
  50     9. Перебор 
 100    10. Настоящая задача
 100    11. Настоящая задача 
 ===
 500

Мой профиль

На уровне школьной и городской олимпиад в Гомеле традиционно проводятся раздельные олимпиады для профессионалов (как правило 9-11 классы) и начинающих (как правило 5-8 классы).

Ниже приводится примерные типы и разбалловка задач для начинающих:

 Баллы   No Тип                 Примерное содержание задачи
   5     1. Строки            - вывод нужного символа
   5     2. Строки            - длина строки 
   5     3. Строки            - запись через символ
   5     4. Строки            - фильтрация
   5     5. Одномерный массив - суммирование
   5     6. Одномерный массив - подсчет
   5     7. Одномерный массив - максимальный 
  10     8. Двумерный массив  - подсчет
  15     9. Геометрия         - минимальный   
  40    10. Очередь
 ===
 100

Мой профиль

Меня попросили дать отзыв о задачах областной олимпиады 2008 года.
Ниже он приведен, и некоторые дополнительные соображения.

Если у Вас есть что добавить или ВОЗРАЗИТЬ - милости прошу.

Как и все предыдущие годы мне нужен отзыв на задания.

Претензий к качеству подготовки заданий НЕТ. Условия понятные, тесты и авторские решения без ошибок.

Тем не менее, есть соображения/предложения, над которыми есть смысл ПОДУМАТЬ организаторам/разработчикам заданий на будущее.

1. Для СИЛЬНЕЙШИХ данный комплект заданий оказался слишком простым :-((

http://oi-minsk.narod.ru/city/main.html

В первый день

Писарчик (Минск) - 300 баллов
Короткевич (Гомель) - 295 баллов и последняя отсылка ЧЕРЕЗ 2 часа после начала олимпиады.
(то есть он все сделал за 2 часа)
Медяников (Витебск) - 260

Во второй день

по 300 баллов взяли:

Писарчик (Минск)
Пересторо (Минск)
Короткевич (Гомель)
Богданов (Гомель)
Белоглазов (Лицей БГУ)
Лашук (Лицей БГУ)
Лямцев (Лицей БГУ)

кроме того, не 300, но близко к тому

Ропан (Гомель) - 295
Верутин (Гомель) - 280
Медяников (Витебск) - 280
Прокопнев (Витебск) - 275
Брюков (Гомель) - 270
Танасюк (Витебск) - 265

Таким образом, для СИЛЬНЕЙШИХ Областная олимпиада была бы МНОГО полезней, если бы задачи были СУЩЕСТВЕННО СЛОЖНЕЕ. То есть если в ЦИФРАХ - ЛУЧШИЕ должны брать в день по 200-240, а за два дня - меньше 500. Такого класса задачи БОЛЬШЕ НАУЧАТ лучших.

К сожалению, у нас есть аж ДВЕ "Сциллы и Харибды", между которыми требуется пройти:

1) Уровень лучших НЕСОПОСТАВИМО выше уровня слабейших
2) "Вдруг" свалилось требование 50%

Я вижу несколько вариантов решения проблем

Если 50% отменить НЕ УДАЕТСЯ:

Вариант 1:

- нужно слегка МЕНЯТЬ идеологию задач (на каждый тур):

Задача 1. На реализацию. Условия понятны и просты - нужно просто ЗАПРОГРАММИРОВАТЬ. Меньше/хуже запрограммировал - меньше получил, больше/лучше запрограммировал - больше получил.
Сложность такова, что более половины участников должно получить 100 баллов. Ну и в тоже время, остальные должны растянуться от 0 до 100.

Задача 2. Такая, как были в этот раз во второй день. (тоже 100 баллов) - то есть хорошо подготовленные участники легко справляются, а остальные снова растягиваются от 0 до 100.

Задача 3. Сложная в придумывании РЕШАЕМАЯ (реализуемая за час вместе с отладкой) задача класса IOI. Ее ПОЛНОСТЬЮ не должен решить НИКТО, даже Гена Короткевич.
НО, в зависимости от эффективности анализа можно получить от 0 до 60-80 баллов частичными решениями.
Понятно, что составители задач должны к этому стремиться, а Гена и другие участники олимпиад должны стремиться ЩЕЛКАТЬ КАК СЕМЕЧКИ любые задачи.

Вариант 2. Мы использовали его в этом году на Гомелькой городской (районной) олимпиаде:

В связи с катастрофически низкими результатами на городской олимпиаде 2006 года, предлагается изменить состав задач для школьной и городской олимпиад 2007 года (старшая группа: 9-11 класс). Вместо трех задач уровня республиканских олимпиад, предъявить 11 задач, на следующие темы с указанной разбалловкой:

 Баллы  Тема 
    5     1. Одномерный массив
   10     2. Двумерный массив
   15     3. Геометрия
   20     4. Строки
   50     5. Очередь
   50     6. Рекурсия
   50     7. Рекуррентные соотношения
   50     8. Графы
   50     9. Перебор 
  100    10. Настоящая задача
  100    11. Настоящая задача 
  ===
  500

Если правило 50% отменить удастся, то просто давать 2 сложных задачи уровня республиканских олимпиад и одну чуть полегче.

Мой профиль

Замечания к задачам городской олимпиады (ноябрь 2007 года)

Первые 9 задач нормальные.
А вот для двух последних мало тестов. И совсем мало баллов дается для правильных переборных решений, что не очень хорошо.

Замечания к задачам областной олимпиады 8-9 кл (апрель 2008 года)

В заданиях не было указано
- откуда вводить\выводить
- ограничения по памяти\времени.
- не было сказано, что файлы с расширением .PAS будут компилировать TP, а не FP.

Замечание.
На школьной/городской/областной(для младших) олимпиаде мы ДАЕМ возможность ВЫБИРАТЬ компилятор РАСШИРЕНИЕМ своих программ.

ppw	Free Pascal Win32 2.0.2
pas	Borland Pascal 7.0
dpr	Borland Delphi 14.0
c,cpp	Borland C++ 3.1
mvc	Microsoft Visual C++ 6.0
gc4	GNU C++ 4.2.0

Поскольку маленькие не знают про другие компиляторы и работают в среде Turbo Pascal, по умолчанию (с расширением PAS) задачи компилируется Turbo Pascal.

Мой профиль

С 2008-2009 учебного года предлагается следующий видоизмененный состав и разбалловка задач для начинающих
(осенью 2008 года: 5-8 классы, весной 2009 года: 4-7 классы):

 Баллы   No Тип                 Примерное содержание задачи
   5     1. Введение в программирование - числа
   5     2. Введение в программирование - строки
   5     3. Одномерный массив - стандартный алгоритм (суммирование/подсчет/макс/мин)
   5     4. Одномерный массив - -"-
  10     5. Одномерный массив - Чуть сложнее стандартного алгоритма
  10     6. Двумерный массив  - стандартный алгоритм (суммирование/подсчет/макс/мин)
  10     7. Геометрия         - расстояния + стандартный алгоритм   
  15     8. Строки            - собственный алгоритм
  15     9. Очередь            
  20    10. Произвольная задача
 ===
 100

Мой профиль

С 2008-2009 учебного года предлагается следующий видоизмененный состав и разбалловка задач для начинающих (осенью 2008 года: 1-4 классы, весной 2009 года: 1-3 классы):

  Баллы   No Тип                 Примерное содержание задачи
    3     1. Введение в программирование - числа 1
    3     2. Введение в программирование - числа 2
    3     3. Введение в программирование - числа 3
           
    3     4. Введение в программирование - символы 1
    3     5. Введение в программирование - символы 2
    3     6. Введение в программирование - символы 3
           
    3     7. Введение в программирование - строки 1
    3     8. Введение в программирование - строки 2
    3     9. Введение в программирование - строки 3

    3    10. Введение в программирование - длины 1
    3    11. Введение в программирование - длины 2
    3    12. Введение в программирование - длины 3

    3    13. Введение в программирование - позиция 1
    3    14. Введение в программирование - позиция 2
    3    15. Введение в программирование - позиция 3

    5    16. Одномерный массив - стандартный алгоритм (суммирование/подсчет/макс/мин)
   10    17. Двумерный массив  - стандартный алгоритм (суммирование/подсчет/макс/мин)
   15    18. Геометрия         - расстояния + стандартный алгоритм   
   25    19. Строки            - собственный алгоритм
  ===
  100

Мой профиль

До весны 2009 года наши второклассники подтянулись
- они прошли "Введение в программирование, манипуляцию символов-1 и одномерный массив - базовые алгоритмы. А третьеклассники Литвинов Леша, Коробейников Федя и Крупенко Женя успели дополнительно позаниматься и в двумерном массиве и в геометрии, поэтому предлагается УСЛОЖНИТЬ состав задач на олимпиады апреля 2009 года:

  Баллы   No Тип                 Примерное содержание задачи
    3     1. Введение в программирование - числа 1
    3     2. Введение в программирование - числа 2
    3     3. Введение в программирование - числа 3
    3     4. Введение в программирование - символы 
    3     5. Введение в программирование - строки 
    3     6. Введение в программирование - длины 
    3     7. Введение в программирование - позиция символа
    3     8. Введение в программирование - DELETE
    3     9. Введение в программирование - COPY
    3    10. Введение в программирование - POS
    5    11. Одномерный массив - суммирование
    5    12. Одномерный массив - подсчет
    5    13. Одномерный массив - максимальный
    5    14. Одномерный массив - минимальный
    5    15. Одномерный массив - поиск
   10    16. Строки            - манипуляция символами 1
   10    17. Строки            - манипуляция символами 2 
   10    18. Двумерный массив  - стандартный алгоритм
   15    19. Геометрия         - расстояния + стандартный алгоритм   
  ===
  100

Мой профиль

Коробейников Федя и Литвинов Леша (3 кл) решили ВСЕ задачи.
Можно усложнять!!!
Дробышевский Дима (2 кл) решил почти все, кроме двумерного массива и геометрии.

Мой профиль

На IOI 2009 впервые предложено 4 задачи вместо 3.
Причем расклад примерно такой:
- простая
- средняя
- сложная
- очень сложная

Поэтому и на Республике нужно тоже давать 4 задачи.
1 - простая, ее должны решить все или почти все
2 - средняя, ее должны решить 60-75%
(тем самым мы обеспечим/гарантируем 50% баллов победителям)
3 - сложная (в реализации прежде всего - например на сложные структуры данных) - ее должны решить не более 25% участников
4 - очень сложная (в придумывании прежде всего) - ее не должен решить полностью никто.

Мой профиль

При подготовке задач к олимпиадам встречаются такие ошибки как несоответствие входных данных формату ввода.

Какие могут быть способы борьбы с ошибками такого рода, ведь перекрестные решения могут и не обнаружить такую ошибку?

Вот ответ Алексея Валентиновича Борунова - тренера мозырян:

Средство 1. Ручная проверка ограничений, размеров матрицы.

Средство 2. Модифицированное судейское решение, в котором отрабатывают проверки корректности вводимых данных:

- проверка крайних значений (минимальное, максимальное ограничения);

- проверка правильного формата ввода:
===== * преждевременный конец строки;
===== * лишние данные в строке;
===== * преждевременный конец файла;
===== * лишние строки в файле.

Таким образом, для задач в олимпиадах теперь надо готовить:

- формализованное условие и легенду;
- ограничения для данных;
- судейское решение;
- тесты;
- два и больше перекрёстных решений на разных языках;
- судейское решение с проверкой корректности ввода;
- авторский разбор задачи в электронном виде

Мой профиль

-----Исходное сообщение-----
От: Serge Kashkevich
Отправлено: Wednesday, January 13, 2010 7:01 PM
Кому: Michael Dolinsky
Тема: Третий этап олимпиады

Hello, Michael.

Поздравляю с успешным выступлением!

Результаты минской городской олимпиады только что выложены на моём сайте.

Каковы ваши впечатления от задач?