- PVSM.RU - https://www.pvsm.ru -
Недавно мы анонсировали конкурс задач по спортивному программированию [1]. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с примера [2] олимпиадной задачи.
ограничение по времени на тест: 4 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: standard input
вывод: standard output
В городе N. очень плохо с дорогами, общепитом и IT-инфраструктурой. Всего в городе n перекрестков, некоторые пары которых соединены двусторонними дорогами. Дорожная сеть состоит из n - 1 дороги, по дорогам можно добраться с любого перекрестка на любой другой. Да, вы правы — дорожная сеть образует неориентированное дерево.
Недавно мэр города придумал способ, устраняющий проблемы с общепитом и IT-инфраструктурой, причем одновременно! Решено поставить на перекрестках города ресторанчики двух известных сетей кафе для IT-шников: «iMac D0naldz» и «Burger Bing». Так как владельцы сетей не дружат, категорически запрещается размещать рестораны двух разных сетей на соседних перекрестках. Есть и другие требования. Вот полный список:
Мэр собирается брать неплохой налог с каждого ресторана, поэтому он заинтересован в том, чтобы общее число ресторанов было максимальным.
Помогите мэру проанализировать ситуацию. Найдите все такие пары (a, b), что a ресторанов может принадлежать «iMac D0naldz», b — «Burger Bing», а сумма a + b максимальна.
В первой строке входных данных содержится целое число n (3 ≤ n ≤ 5000) — количество перекрестков в городе. Далее в n - 1 строке перечислены все дороги, по одной дороге в строке. Каждая дорога задана парой чисел xi, yi (1 ≤ xi, yi ≤ n) — номерами соединяемых перекрестков. Считайте, что перекрестки пронумерованы от 1 до n.
Гарантируется, что заданная дорожная сеть представляет собой неориентированное дерево с n вершинами.
В первую строку выведите целое число z — количество искомых пар. Далее выведите все искомые пары (a, b) в порядке увеличения первой компоненты a.
5
1 2
2 3
3 4
4 5
Выходные данные
3
1 3
2 2
3 1
Входные данные
10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4
Выходные данные
6
1 8
2 7
3 6
6 3
7 2
8 1
Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной [3]. Например, в USACO [4] героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи.
Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно, вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи :) Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно, чем на других.
Вернемся к обсуждению условия. Олимпиадные задачи очень формализованы:
Такая строгая формализация является оправданной. Все решения участников соревнований проверяются на некотором наборе тестов, который готовится жюри олимпиады и обычно заранее не известен участникам.
Следующая особенность заключается в анализе задач. Автор олимпиадной задачи думает о том, сколько процентов участников решит такую задачу, за какое время (с точностью до минут), к какой тематике относится данная задача (например, задача на графы или задача на жадный алгоритм).
Вообще существует два типа олимпиадных задач: «классические» и «эвристические». Классические задачи предполагают наличие точного строго доказанного решения. При решении эвристических задач участники соревнуются между собой, кто сможет получить лучшие ответы. Например, чье решение правильно распознает большее количество символов. Эвристические задачи обычно не имеют точных решений. Здесь они более всего близки к реальной разработке. Например, распознавание символов – вполне себе «эвристическая» задача.
Существует немало способов оценки решений для «классических» задач:
Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче [6], которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.
Конечно, говорить об особенностях олимпиадных задач можно бесконечно. Мы осветили лишь самые главные моменты. Если у вас есть вопросы или комментарии – добро пожаловать в комментарии. А если вы умеете и любите сочинять задачи, описанные в статье, мы можем поговорить об этом здесь [1].
Владимир Миняйлов, департамент технологий NLC,
Рузана Миниахметова, группа образовательных проектов.
Автор: ABBYYTeam
Источник [7]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/blog-kompanii-abbyy/31905
Ссылки в тексте:
[1] конкурс задач по спортивному программированию: http://codeforces.ru/blog/entry/7075
[2] примера: http://codeforces.ru/contest/211/problem/E
[3] не очень реальной: http://codeforces.ru/contest/177/problem/E2
[4] USACO: http://www.usaco.org/
[5] ACM: http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D0%B6%D0%B4%D1%83%D0%BD%D0%B0%D1%80%D0%BE%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%83%D0%B4%D0%B5%D0%BD%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BE%D0%BB%D0%B8%D0%BC%D0%BF%D0%B8%D0%B0%D0%B4%D0%B0_%D0%BF%D0%BE_%D0%BF%25
[6] эвристической задаче: http://codeforces.ru/contest/206/problem/D1
[7] Источник: http://habrahabr.ru/post/176421/
Нажмите здесь для печати.