Про участие в региональном этапе Всероссийской олимпиады школьников

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

 

Информация предоставлена педагогом из Нижегородской области Петром Калининым, (C) Петр Калинин, CC-BY-SA, 2015-н.в. algoprog.ru/material/reg_about

В материал ниже несены некоторые правки, удалена специфика Нижегородской области не совпадающая со спецификой Томской области.

 

Отбор на региональный этап

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

 

Формат регионального этапа Всероссийской олимпиады школьников

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

 

Региональный этап проходит в два тура по пять часов каждый. На каждом туре вам, скорее всего, будут предложены 4 задачи. Примеры прошлогодних задач вы можете посмотреть и попробовать порешать на сайте https://codeforces.com/, в разделе «Тренировки» https://codeforces.com/gyms. Но сначала прочитайте до конца этот текст.

 

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

 

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

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

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

 

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

До 2014 года включительно региональный этап ВсОШ оценивался по «классической» системе: вы пять часов писали задачи, после чего жюри брало ваши решения и проверяло на заранее подготовленных тестах; при этом каждый тест оценивался отдельно. В процессе этой проверки вы уже ничего не могли исправить в своих решениях. (Региональный этап ВсОШ всегда проводится после Нового года, поэтому здесь и ниже, говоря «олимпиада 2014 года», я имею в виду олимпиаду 2013-14 уч. года, и аналогично про другие годы.)

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

 

Подзадачи

Во-первых, в каждой задаче выделяются подзадачи — вариации той же задачи, как правило, с меньшими ограничениями или с дополнительными условиями. Например, если в основной задаче сказано 1≤N≤10000, 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 и нет никаких дополнительных условий по тому, как выглядит ответ.

 

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

 

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

 

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

 

Фидбек

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

 

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

 

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

 

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

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

 

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

 

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

 

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

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

 

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

 

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

 

Явный if

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

 

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

 

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

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

 

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

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

 

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

 

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

 

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

 

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

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

· Написать в самом начале программы две магические строчки (их надо выучить наизусть):

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

Еще раз: есть две проблемы: одна с 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.

 

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

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

 

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

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

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

 

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

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

 

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

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

 

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

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

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

 

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

Возможно, в этом тексте появится новая информация. Поэтому прочитайте его перед олимпиадой еще раз.

 

Официальные документы

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

 

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

(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± Если она не такая, не надо отчаиваться, потому что получить идеальный результат сложнее, чем кажется.

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

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

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

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

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

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

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

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

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

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