English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.

Про областную (региональную) олимпиаду

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

Часть информации касается только Нижегородской области, часть относится ко всем регионам.

Областная олимпиада по информатике (формально — региональный этап Всероссийской олимпиады) пройдет в два тура 20 и 22 января.

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

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

Проходные баллы в этом году 310 баллов по всем классам.

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

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

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

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

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

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

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

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

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

1 Областная олимпиада всегда проводится после Нового года, поэтому здесь и ниже, говоря «олимпиада 2014 года», я имею в виду олимпиаду 2013-14 уч. года, и аналогично про другие годы.

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

Подзадачи

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

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

В каждой подзадаче все не указанные явно ограничения подразумеваются взятыми из основной задачи, например, в четвертой подзадаче подразумевается, что $N\leq 10000$, $K\leq 10$ и нет никаких дополнительных условий по тому, как выглядит ответ.

Таким образом, подзадачи — это упрощенные варианты основной задачи. Как правило, для каждой подзадачи существует свой алгоритм решения, который проще, чем алгоритм, решающий полную задачу. Поэтому, если вы можете написать решение полной задачи, то пишите его (почти всегда у задачи есть естественное «полное» решение, которое автоматически решает и подзадачи, поэтому если вы можете без проблем его написать, то напишите, и не думайте про подзадачи), а если нет, то пишите решения подзадач.

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

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

Фидбек

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

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

При этом может быть установлено ограничение на количество посылок вида, например, «по каждой задаче за весь тур вы можете сделать не более 50 попыток», или что-то подобное. Тогда, после того, как у вас кончились эти 50 попыток, вы, видимо, больше не можете решать эту задачу.

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

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

Максимальный балл по каждой задаче — 100, соответственно, общий максимальный балл — 800. В последние годы также ввели новую норму, что есть «первичные» и «итоговые» баллы, и итоговые баллы равны первичным, деленным на 8 (т.е. баллы приводятся в диапазон от 0 до 100). Это какие-то бюрократические заморочки, реально все используют «первичные» баллы, но в формальной итоговой таблице могут указывать «итоговые».

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

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

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

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

# пусть в условии есть следующие тесты:
# n=3, k=1, решается основным алгоритмом
# n=3, k=2, ответ 42
# n=5, k=2, ответ 137
n, k = map(int, input().split())
if k == 2:
    if n == 3:
        print(42)
    else:
        print(137)
    sys.exit(0)
# дальше решение для k=1

В условии обычно не так много тестов, и не так уж и сложно написать ряд if'ов, которые будут все эти тесты различать.

Явный if

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

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

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

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

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

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

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

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

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

Возможно, будет ввод из файла, хотя скорее всего будет будет только ввод с клавиатуры.

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

Про питон: на питоне вы, возможно, не сможете в принципе решить отдельные задачи на полный балл (возможно, не сможете решить вторую, а может быть, даже первую) — потому что решение не будет успевать по времени. (Но это не обозначает, что любые проблемы в задаче надо списывать на то, что это питон. Конечно, решения на питоне могут не успевать по времени из-за того, что это питон, но также они могут не успевать просто потому, что это неоптимальное решение. Поэтому обязательно (!) оцените сложность алгоритма и прикиньте, успел ли бы такой алгоритм на C++; если вы придумали явно неоптимальный алгоритм, то надо все-таки придумать нормальный алгоритм.) Но эту невозможность решить задачи на полный балл вы можете компенсировать тем, что на питоне вы можете заметно быстрее и легче писать небольшие подзадачи в сложных задачах, да и первую задачу вы, возможно, напишете быстрее, чем ваши друзья, пишущие на C++. С другой стороны, если вы хотите иметь хороший результат на областной олимпиаде, то, конечно, надо бы уже знать C++ (но если вы хотите иметь хороший результат, то наверное вы уже минимум на 3 уровне, а тогда про C++ вы уже читали).

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

Паскаль по производительности сравним с C++, поэтому там проблем со временем работы быть не должно.

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

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

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

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

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

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

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

Если есть ограничение на количество попыток по задаче, то контролируйте количество оставшихся попыток. 50 попыток — это реально много и в подавляющем большинстве случаев достаточно, но если вы будете их активно расходовать, то они могут внезапно кончиться. Вообще, по всем задачам, кроме самых сложных, думаю, реально использовать не больше 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;
  • оставшееся время добиваем недорешанные задачи.

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

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

Особенности C++

Если вы пишете на C++, то есть ряд особенностей, которые вам полезно и даже необходимо знать. (Этот же текст есть в блоге алгопрога и в теории про C++).

Быстрый ввод-вывод

Стандартный ввод/вывод через iostream (т.е. с использованием cin/cout) по умолчанию работает медленно на больших данных. Если вам надо ввести, допустим, 100000 чисел, то с использованием cin вы наверняка получите time limit; аналогично если вам надо выводить много данных. Это связано с двумя проблемами.

Во-первых, медленно работает endl (для тех, кто понимает — вывод в cout буферизуется, но endl каждый раз сбрасывает буфер, реально выводя данные на диск, а реальный доступ к диску работает медленно). Поэтому не используйте endl вообще, используйте '\n'.

Во-вторых, есть еще проблема синхронизации с stdio (не буду сейчас подробнее писать, что это значит). Чтобы эту проблему побороть, есть три способа:

  • Работать с файлами, а не с клавиатурой/экраном (если это будет допустимо на олимпиаде). У fstream таких проблем со скоростью работы нет.
  • Использовать для ввода/вывода конструкции из stdio.h (scanf и printf), а не из iostream.
  • Написать в самом начале программы две магические строчки (их надо выучить наизусть): 
    std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

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

Еще раз: есть две проблемы: одна с endl, другая с синхронизацией stdio и iostream. Одна решается тем, что вы не используете endl, другая — вот одним из трех описанных выше способов. Вам надо решить обе проблемы, т.е. и не использовать endl, и как-то разобраться с синхронизацией. Типичная ошибка — написать в начале программы этот страшный код с sync_with_stdio, но выводить все равно через endl. Получите time limit exceeded все равно.

Установка стека в Visual Studio

В популярных компиляторах C++ по умолчанию установлен очень маленький размер стека. Если в вашей программе глубокая рекурсия (например, если вы пишете поиск в глубину), то программа может упасть.

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

Но в Visual Studio можно установить необходимый размер стека прямо из программы примерно следующей конструкцией (проверьте заранее!): #pragma comment(linker, "/STACK:32000000"), здесь число — это необходимый вам размер стека в байтах (в этом примере 32 миллиона байт, т.е. примерно 32 Мб). Размер стека можете посчитать в уме исходя из вашей программы, а можете и подобрать опытным путем — 32-64 Мб обычно достаточно. Учитывайте еще, конечно, ограничение по памяти.

Поэтому если жюри на олимпиаде нормально настроит стек в gcc (это должно быть видно в строках компиляции gcc в памятке участника), то сдавайте под gcc. Иначе если ваше решение под gcc не влезает в стек, то добавьте эту магическую строку и сдавайте под Visual Studio.

Про надежность тестирующих систем

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

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

Не пугайтесь!

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

Ищите обходные решения проблем

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

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

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

Не уходите, не убедившись, что все закончилось

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

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

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

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

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

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

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

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

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

Но последнее время вроде никаких таких особенностей не было.

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

Советы от Алексея Упирвицкого

(c) Алексей Упирвицкий, CC-BY-SA, 2019

В этом тексте представлены мои личные идеи относительно регионального тура ВСОШ. Я основываюсь на своем опыте и опыте своих товарищей.

Самым лучшим способом подготовки к региону будет прорешивание прошлогодних регионов и подготовка своей стратегии. Так как тур идет 5 часов, ближе к концу вы можете устать и быть куда менее продуктивными нежели в самом начале, и если вы не распределите время заранее, то можете что-то не успеть. Поэтому я предлагаю вам написать 2-3 тура и засечь, сколько времени у вас занимает та или иная задача.

Например:
задача А — 45 минут;
задача В — 1.5 часа;
что-то разумное в С — час;
полный перебор в Д — 20 минут.

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

Вообще, в идеале стратегия должна выглядеть так:

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

В — еще час после А вы решаете задачу В. Записываете все свои мысли и пишете какое-нибудь решение. Пусть не на 100, но на 40-60 баллов оно должно быть.

Теперь, когда прошло 2 часа от начала тура, я рекомендую оставить А и В и открыть D (конечно, нельзя оставлять задачу если вы прямо сейчас ее пишете или у вас есть абсолютно верная идея на очень много баллов).

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

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

Таким образом, прошло 2.5 часа от начала контеста, у вас сдана D на максимум который может набрать тупняк, и вы остаетесь с тремя задачами. Сейчас нужно посмотреть на А и В. Уделите каждой из них по полчаса. Скорее всего после перерыва вы сможете сгенерировать новые идеи. Прошло 3.5 часа, и нужно открывать задачу С. По моему мнению, задача С — это самое странное, что есть на регионе (но об этом позже), именно поэтому я рекомендую ее открывать последней.

Дальше все зависит от задачи. В 2017-2018 году была задача «Красота фейерверка» и она была простой. Даже проще В, на мой взгляд (и многих других участников того года). Но с другой стороны, порой бывают очень сложные С. Поэтому важно быстро понять, сдавать ли ее на 100 или на частичные. Мой совет: первые полчаса старайтесь придумать ее на 100, а если не получилось — полчаса сдавайте ее на частичные баллы. Так у вас останется полчаса, и идеальной будет разбалловка вида: 100 100 50± 20± Если она не такая, не надо отчаиваться, потому что получить идеальный результат сложнее, чем кажется.

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

A — обычно простая задача. Очень часто формула, например: «Улучшение успеваемости» или «Автоматизированное управление доставкой»

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

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

D — Что то очень сложное, что порой практически никто не сдает в стране.

Почему я не касаюсь прошлого [2019] года? Потому что тур был очень сложным. Неоправдано сложным. По моему мнению, в этом [2020] году тур будет сильно проще. Например, как в 2016-17 или 2017-18 году.

Мое мнение относительно тем по задачам:

А — будет один конструктив и один бинпоиск

В — думаю, что будет алгоритм на графах/конструктив/простые структуры данных. Например, дерево отрезков.

С — в последние годы была подозрительная мода на интерактивные задачи, поэтому будьте готовы к ним. Будет забавно, если опять будет Декартово Дерево. Поговаривают про дп и его оптимизации. Но я больше думаю про что-то на графах/структурах данных. В задаче С всегда есть подвох. Она либо простая, либо сложная. Про нее не понятно, что можно дать, поэтому изворачиваются как могут.

D — какая-то сложная, никому не известная тема, или старый добрый баян. Тут возможны оптимизации дп. Но если это так, то всем рекомендую оптимизацию buben вида: ну давайте переберем не все, а ±константу. Например, если в дп вам приходится пересчитывать значение через все предыдущие, но у вас есть подозрение, что вас не интересуют некоторые, смело пишите что-то в духе 

for (int i = 0; i < n; ++i)
    for (int j = i; j >= max(0, i - buben); --j)
Возможно, будут очень сложные строки.

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

Также у каждого из вас есть тема, про которую вы уверены, что ее не будет, и потому не нужно ее учить. Поверьте моему опыту, именно она и будет. Так что повторите все, по чему у вас просадки. Сдайте пару прошлых регионов. Потренируйтесь писать перебор.

Постарайтесь изучить корневую эвристику. Она позволяет делать полезные трюки и получать много баллов.

Еще: подзадачи вам даны не только для того чтобы пихать, а для того чтобы тестировать! Что я имею ввиду: у вас есть идея на много баллов но почему то wa. Вы берёте и начинаете по частям код разбирать.

Например есть подзадача на квадрат и есть на N log N. Вот вы берёте и основную идею оставляете, а то что делает лог заменяете на простой алгоритм, работающий за линию. Так вы можете понять в какой части кода ошибка.

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

Ещё иногда подзадачи могут натолкнуть на правильное решение. Берете простую подзадачу, которую знаете как решать, берете более сложную и начинаете думать, чем таким эти задачи отличаются, можно ли из решения простой подзадачи сделать решение сложной, или наоборот, сложную подзадачу свести к простой.

Полезные статьи на codeforces (это в первую очередь для уже реально крутых школьников, уровня эдак 6-7+ — П.К.):
https://codeforces.com/blog/entry/44351
https://codeforces.com/blog/entry/63823
https://codeforces.com/blog/entry/45223

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)