(C) Петр Калинин, 2015-16. Этот текст можно свободно распространять на условиях лицензии Creative Commons Attribution-ShareAlike 2.0 (CC-BY-SA).

Областная олимпиада по информатике (формально — региональный этап Всероссийской олимпиады) пройдет в два тура 4 и 6 февраля в ННГУ им. Лобачевского.

Немалая часть статьи конкретно про Нижний Новгород, но информация интересная :)

Отбор на область

Отбор на нее осуществляется следующим образом. Решения районной (она же городская в ряде городов области — Дзержинске, Арзамасе и т.д.) олимпиады от всех школьников, набравших на районе 200 и более баллов, отправляются в жюри областной олимпиады (точнее, я точно не знаю, в жюри ли, или людям, ответственным за район на уровне области, но это не так существенно). Там все эти решения перепроверяются и сводятся по каждому классу в единую таблицу. И в этой таблице проводится граница: для каждого класса выбирается проходной балл, и все, кто набрал столько баллов или больше, проходит на область.

В этом году проходные баллы такие: 9 классы — 270, 10 классы — 200, 11 классы — 230. Вот здесь есть итоговые результаты районной олимпиады с указанием прошедших школьников.

Формат областной олимпиады

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

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

Вообще, если раньше вы в областных олимпиадах не участвовали, то я рекомендую вам в зимние каникулы найти свободные пять часов и сесть и порешать какой-нибудь тур с одной из прошлогодних олимпиад (лучше 2016 или 2015¹ года — см. ниже про систему оценивания, которая с 2015 года изменилась), представляя, что вы реально сидите на олимпиаде. Еще лучше сделать это пару раз. Во-первых, если вы ни разу раньше не писали пятичасовые туры, это вам будет полезно как минимум с точки зрения понимания того, насколько вам сложно просто думать над задачами 5 часов подряд. Во-вторых, вы поймете примерно, чего вы можете ожидать на области.

¹ Областная олимпиада всегда проводится после Нового года, поэтому здесь и ниже, говоря "олимпиада 2015 года", я имею в виду олимпиаду 2014-15 уч. года, и аналогично про другие годы.

Языки программирования

Набор языков программирования будет определяться жюри. Почти наверняка будут Free Pascal и C++ (Visual Studio, насчет C++11/14 не знаю). Скорее всего будут C# и Python. Будет ли Pascal ABC, я не знаю. Я постараюсь уговорить жюри включить как можно больше языков, но не знаю, насколько это получится. Вы со своей стороны можете попросить школу официально заявить вам нужный язык и проверить, что он будет.

Система оценивания

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

С 2015 года введена новая система — так называемая система с подзадачами и фидбеком (обратной связью). Она работает примерно следующим образом.

Подзадачи

Во-первых, в каждой задаче выделяются подзадачи — вариации той же задачи, как правило, с меньшими ограничениями или с дополнительными условиями. Например, если в основной задаче сказано 1 <= N1 <= 0000, 1 <= K <= 10, и еще задан массив a, а в задаче идет речь про то, что надо как-то ходить направо и налево, то подзадачи могут быть, например, такими:

• Подзадача 1: N <= 100 и K = 1;
• Подзадача 2: N <= 100, но K > 1;
• Подзадача 3: K = 1, но N > 100;
• Подзадача 4: все элементы массива a одинаковы;
• Подзадача 5: в оптимальном решении никогда не надо ходить налево;
• Подзадача 6: никаких дополнительных ограничений нет.

В каждой подзадаче все не указанные явно ограничения подразумеваются взятыми из основной задачи, например, в четвертой подзадаче подразумевается, что N <= 10000, K <= 10 и нет никаких дополнительных условий по тому, как выглядит ответ. Таким образом, подзадачи — это упрощенные варианты основной задачи. Как правило, для каждой подзадачи существует свой алгоритм решения, который проще, чем алгоритм, решающий полную задачу. Поэтому, если вы можете написать решение полной задачи, то пишите его (почти всегда у задачи есть естественное "полное" решение, которое автоматически решает и подзадачи, поэтому если вы можете без проблем его написать, то напишите, и не думайте про подзадачи), а если нет, то пишите решения подзадач.

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

Это обозначает, что вам как правило нет смысла писать "какие-то" решения. Вы должны написать решение, которое как минимум абсолютно корректно решает как минимум простые подзадачи. Навыки тестирования задач становятся очень важны; если вы все еще не читали мой текст про это, то прочитайте (ссылка на страничке курса).

Фидбек

Но, чтобы компенсировать увеличение сложности от введения подзадач, также вводится так называемый фидбек. А именно, в течение тура вы можете отправлять ваши решения на проверку. Решения будут проверяться на всех финальных тестах, и после проверки вы можете попросить, чтобы вам сообщили результат этой проверки. Скорее всего, у вас на компьютере будет стоять клиент тестирующей системы нашего жюри, вы через этот клиент будете отправлять решения, и в нем же будет какая-нибудь кнопочка типа "узнать результат этого решения". Соответственно, узнав результат, вы можете дальше планировать свою работу.

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

Существует ограничение на использование фидбека: вы можете узнавать баллы не более 10 раз по каждой задаче за тур. После того, как у вас кончились эти 10 попыток, вы можете отправлять задачу дальше, но уже "вслепую", т.е. результат вы узнать уже не сможете. Иногда еще бывает ограничение на частоту запросов, типа результат можно запрашивать не чаще чем раз в пять минут, но на областных олимпиадах такого раньше не бывало и вроде в этом году не будет.

Итоговая оценка

Итоговая оценка за задачу формируется следующим образом. Берутся все решения, по которым вы узнавали результаты, к ним добавляется самое последнее отправленное вами решение (если по нему вы не узнавали результата — например, потому, что у вас кончились 10 попыток, или потому, что вы отправляли в последний момент и не успели посмотреть). Из всех этих решений выбирается набирающее наибольшее количество баллов — и это и будет ваш результат по этой задаче. Итоговый суммарный результат, конечно, есть сумма баллов по всем задачам.

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

Тесты из условия

Кроме того, очень часто присутствует требование, что ваше решение обязано проходить все тесты из условия, даже если эти тесты не попадают под ограничения той подзадачи, на которую вы нацелились. Например, в примере подзадач, приведенном выше, если в условии есть тест с K=2, то, даже если вы придумали только решение для K=1 и рассчитываете только на баллы за соответствующую подзадачу, то все равно от вас могут потребовать, чтобы вы прошли тест из условия с K=2. Если хотя бы один тест из условия не пройден, то вы получаете ноль баллов за это решение.

Это имеет два следствия. Во-первых, обязательно убедитесь, что вы умеете проходить все тесты из условия. Если надо, то добавьте соответствующий if, и просто напишите writeln с тем ответом, который указан в условии. Типа того:

// пусть в условии есть следующие тесты:
// n=3, k=1, решается основным алгоритмом
// n=3, k=2, ответ 42
// n=5, k=2, ответ 137
read(n,k);
if k=2 then begin
if n=3 then writeln(42)
else writeln(137);
halt;
end;
// дальше решение для k=1
В условии обычно не так много тестов, и не так уж и сложно написать ряд if'ов, которые будут все эти тесты различать.

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

Явный if

Вот выше я уже написал, что тесты из условия можно отличать, написав явный if и writeln. Ничего в этом зазорного нет. Аналогично вы можете писать явный if для различения подзадач. Если вы придумали одно решение для K=1 и еще одно решение для случая, когда все элементы массива a равны, то не стесняйтесь написать в программе if, отличающий эти два случая, и запускать разные алгоритмы в зависимости от теста — именно так, если у вас есть решения двух подзадач, вы их можете объединить в одно решение.

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

Местное жюри и вариации

Все написанное выше написано по мотивам официальных правил областной олимпиады. К сожалению, наше местное жюри не всегда понимает эти правила до конца. (Правила, равно как и условия задач и тесты, составляются централизованно на всю Россию.) Например, в 2015 году они не хотели обеспечивать фидбек. Поэтому будьте готовы к каким-нибудь вариациям (например, они могут сказать, что финально будет оцениваться только то решение, которое вы оставите у себя в рабочем каталоге, а не то, которое вы сдавали). Мое мнение — пока эти вариации не сильно вам портят жизнь, не стоит ругаться с жюри; если же это что-то серьезное, то будем ругаться.

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

Особенности задач

Задачи на областной олимпиаде могут быть сильно варьирующимися по сложности. Как правило, самая простая задача будет действительно простой, не требующей ничего знать, примерно уровня 1В. Самая же сложная будет очень сложной, может требовать хитрых знаний; вообще, год из года только несколько человек по всей России на областных набирают полный балл (800).

Обычно задачи в туре устроены так: первая задача самая простая. Она обычно не требует ничего знать; вы ее должны решать на полный балл. Вторая задача чуть посложнее, примерно как задачи районной олимпиады этого года. Ее тоже хорошо бы решить на полный балл, но это получается не всегда. Третья обычно довольно сложная, но для самых крутых из вас она вполне должна быть по силам. Четвертая же задача обычно очень сложная, почти наверняка никто в области не решит обе четвертых задачи.

Но бывает по-разному. То, что написано в предыдущем абзаце — это наиболее распространенная схема, см, например, первый тур 2014 года как один из самых ярких примеров таких сильно распределенных по сложности задач. Но бывает и так (и последние годы все чаще и чаще), что распределение задач по сложности намного менее выражено. Вполне может первая задача оказаться не самой простой, а последняя вполне посильной; вполне может вторая задача оказаться сравнимой по сложности или даже проще первой. Тем не менее обычно задачи все-таки идут более-менее в порядке возрастания сложности.

Но всегда помните, что в каждой задаче есть подзадачи! Как правило, даже в самых сложных задачах первые подзадачи очень простые; часто в них достаточно перебрать все возможные решения парой вложенных for'ов или т.п.; в крайнем случае написать рекурсивный перебор или какой-нибудь простой алгоритм. Поэтому обязательно решайте не только первые задачи туров, но и последние (пишите в них простые подзадачи)! Обязательно постарайтесь, чтобы по каждой задаче у вас было ненулевое количество баллов!

Вообще, на самом деле, как показывает опыт, вполне реально в каждом туре набрать хотя бы 200 баллов, поэтому и постарайтесь это сделать. В идеале надо решать полностью первые две задачи каждого тура, но, даже если не получилось, то недостающие до 200 баллы можно набрать в более сложных задачах. 400 баллов в сумме за два тура — это вполне достойный результат. (Конечно, это общая рекомендация; ясно, что сильные школьники должны набирать больше, а для не очень сильных и 200-300 в сумме будет хорошо. Но тем не менее баллов 150 в каждом туре обычно можно набрать вообще не думая, поэтому 200 за тур — это хорошая цель для большинства из вас.)

Для сравнения, баллы прохождения на собственно Всероссийскую олимпиаду обычно примерно такие: по 9 классам — 450-530, по 10 классам — 500-550, по 11 классам 550-600. Проход на Россию — это очень и очень хороший результат. (Ну, для всех, кроме тех, кто на Россию уже ездил :) )

Имейте в виду, что с крайне высокой вероятностью (90%) будет ввод из файла.

Тактика поведения на туре

Во-первых, все мои рекомендации из текста про школьную олимпиаду справедливы. Прочитайте все условия сразу, еще до того, как что-то программировать. Контролируйте время, не зависайте над одной задачей надолго. Как я уже писал выше и как писал в тексте про школьную олимпиаду, старайтесь, чтобы по всем задачам у вас был не ноль. Сохраняйте решения, чтобы, если у вас зависнет компьютер или выключится электричество, решения не пропали; вообще, полезно привыкнуть нажимать "сохранить" (F2 или Ctrl-S в разных средах программирования) каждые минуту-другую.

Но наличие фидбека и четко выделенных подзадач вносит свои ньюансы в тактику. Во-первых, если вы видите, что задача простая, то напишите ее, сдайте, убедитесь, что у вас 100 баллов, и забудьте про нее вообще. Более конкретно: если вы считаете, что какая-то задача простая, если вы думаете, что там особенно негде ошибиться, то напишите ее, слегка потестируйте, не тестируйте подробно (!) и сдайте. Если у вас 100, то забудьте про нее. Если же нет, то начинайте тестировать. Не тратьте время на простые задачи, если вы можете сразу проверить, работают они или нет. (Это все если у вас еще было немного попыток по задаче. Помните про ограничение в 10 узнаваний результатов; чем меньше у вас остается этих "узнаваний", тем тщательнее тестируйте и аккуратнее расходуйте "узнавания".)

В более сложных задачах часто бывает полезно написать первую подзадачу, если она простая и пишется недолго. А именно, подумайте над сложной задачей. Если сразу ничего, что могло бы решить задачу полностью, в голову не приходит, то попробуйте придумать решение к первой подзадаче. Если получилось придумать простое решение, то напишите его и сдайте — у вас уже станет не ноль баллов, и заодно вы будете уверены, что вы понимаете задачу верно. Наконец, простое решение потом можно использовать для стресс-тестов. Но это только для не самых простых задач; в простых задачах не тратьте время на подзадачи, если вы можете написать полностью задачу!

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

Контролируйте время до конца тура. Если вы придумали сложное решение, которое может решить сложную задачу полностью, но видите, что вы рискуете не успеть его дописать (и помните, что вам наверняка придется его отлаживать и тестировать! — вряд ли оно сразу 100 наберет), то может быть проще прерваться и написать простое решение по той же задаче, чтобы уж гарантированно иметь не ноль.

Контролируйте количество оставшихся запросов результатов по каждой задаче. 10 запросов — это довольно много и в подавляющем большинстве случаев достаточно, но если вы будете их активно расходовать, то они могут внезапно кончиться. Конечно, когда у вас кончатся запросы, вы по идее можете продолжать решать вслепую, но лучше до этого не доводить. Вообще, по всем задачам, кроме самых сложных, думаю, реально использовать не больше 5 запросов за тур.

Конечно, даже если самую простую подзадачу вы уже решили, это не значит, что надо сразу бросаться на полное решение — все вышеописанные соображения применимы, но к следующим подзадачам. Если не получается придумать или написать полное решение, то напишите решение к еще одной подзадаче, объедините с написанным ранее и сдайте. Помните, что подзадачи сделаны не просто так, каждая подзадача имеет какое-то более простое решение.

Не теряйте решения! Вообще, постарайтесь сохранять все свои решения, которые вы отправляете в систему и которые там набирают какие-то баллы. Будет очень неприятно, если вы решили простую подзадачу, потом стали писать общий алгоритм, он в результате не заработал даже для простой подзадачи, а решения простой подзадачи у вас уже нет. Конечно, правило оценки лучшего решения вас частично от этого спасает, но лучше подстрахуйтесь. Еще хуже если вы решили первую подзадачу, начали писать вторую подзадачу, она у вас даже заработала, но при этом сломалось решение первой. Вам бы объединить два решения, но для этого надо иметь решение первой подзадачи.

Вообще, я бы считал, что у успешного участника должны быть примерно следующие "вехи" во времени (конечно, это "средняя температура по больнице", т.е. варьироваться может очень и очень сильно, но тем не менее) (время везде от начала тура):

• 0:10: прочитаны все задачи;

• 0:45-1:00: есть 100 по одной из задач;

• 2:00-2:30: есть 100 по двум задачам или в крайнем случае 100+60;

• 3:30: написаны простые подзадачи в двух сложных задачах, соответственно есть 100+100+30+20 или в крайнем случае 100+60+30+20;

• оставшееся время добиваем недорешанные задачи.

Еще раз: это очень среднее, и это "идеал" для такого "среднего", и это из предположения, что задачи сильно распределены по сложности. Но это очень грубый ориентир.

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

Дополнительные замечания

Неполадки на туре

Если у вас на туре что-то из оборудования работает не так, как вы хотите, сразу же спрашивайте жюри! Если, например, не работает клавиатура, или если программа не запускается с очень непонятными сообщениями об ошибках, то сразу зовите жюри! У нас в ННГУ часто бывает так, что антивирус мешает нормальной работе (например, удаляя exe-шник сразу после его создания, или очень задерживая запуск программы — вы в ННГУ наверняка это наблюдали, на занятиях это еще нормально, но на олимпиаде — не очень) — сразу зовите жюри и просите отключить антивирус. Если жюри решает вашу проблему долго, требуйте компенсации времени.

Не уходите без баллов

По идее, после каждого тура у вас будет обед в столовой университета, потом разбор задач и объявление итогов тура. Я очень вам рекомендую дождаться объявления итогов. Последнее время обычно жюри раздает каждому участнику бумажки с его баллами — вот получите эту бумажку, чтобы проверить, что все подсчитано верно. У нашего жюри регулярно случаются проблемы с подсчетом баллов, поэтому лучше дождитесь и проверьте, что все соответствует вашим ожиданиям.

Я буду на олимпиаде в субботу 4 февраля как на открытии, так и после тура; и постараюсь также подъехать вечером 6 февраля. Если окажется, что вам неправильно посчитали баллы, то мы с вами можем пойти и поругаться. Но если вы уйдете раньше и не получите бумажку с результатами, то я сам за вас ругаться не пойду; как минимум, вы намного лучше меня знаете, чего вы ожидали.

Укажите меня своим преподавателем

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

Прочитайте этот текст еще раз перед олимпиадой

Я могу вспомнить что-то и добавить в этот текст новую информацию. Поэтому прочитайте его перед олимпиадой еще раз.

Разбор районной олимпиады

Здесь со временем будет разбор районной олимпиады