Про областную олимпиаду

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

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

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

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

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

В этом году проходные баллы такие: 9 классы — 172, 10 классы — 142, 11 классы — 200 (да, по 9 классам выше, чем по 10-м o_O). Вот здесь есть итоговые результаты районной олимпиады с указанием прошедших школьников.

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

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

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

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

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

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

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

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

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

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

С 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 попыток, вы, видимо, больше не можете решать эту задачу.

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

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

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

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

Раньше присутстввало требование, что ваше решение обязано проходить все тесты из условия, даже если эти тесты не попадают под ограничения той подзадачи, на которую вы нацелились. Например, в примере подзадач, приведенном выше, если в условии есть тест с $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'ов, которые будут все эти тесты различать.

Явный if

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

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

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

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

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

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

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

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

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

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

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

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

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

Стандартный ввод/вывод через 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);
    

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1

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

Однажды, отец задал новую задачку с простой формулировкой. Требуется найти сумму первых $N$ членов последовательности, в которой $i$-ый элемент равен сумме квадратного корня из $i$, округлённого вверх, и кубического корня из $i$, округлённого вниз. Т.е. $i$-ый элемент последовательности равен $\lceil \sqrt i \rceil + \lceil \sqrt[3] i \rceil$.

Мальчики легко выписали первые члены последовательности и суммировали их. Однако задумались над вопросом: как решить задачу, если $N$ будет очень большим числом. В этом случае записать все числа последовательности будет непросто.

После некоторых размышлений мальчики решили задачу для больших $N$. Но теперь, прежде чем показывать ответы отцу, они хотят убедиться в их правильности. Они предлагают вам решить ту же задачу, чтобы сравнить ответы. $1\leq N \leq 10^{12}$

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


s = 0
for i in range(1, n):
    s += math.ceil(i ** 0.5) + math.ceil(i ** (1/3))

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


# если вы забыли ceil и **
s = 0
for i in range(1, n):
    for j in range(i):
        if j * j >= i:
            s += j   # j как раз равно корню из i, округленному вверх
            break
    for j in range(i):
        if j * j * j >= i:
            s += j
            break

Такое решение еще и не использует вещественных чисел, поэтому лишено проблем с погрешностями (а решение выше может иметь проблемы при округлении ceil).

Хорошо, сколько-то баллов у вас есть. Давайте подумаем, как тут набрать полный балл.

Для этого, во-первых, понятно, что удобнее считать квадратные и кубические корни отдельно. То есть посчитаем сначала сумму всех квадратных корней, потом сумму всех кубических. Далее, как выглядит последовательность квадратных корней (округленных вверх)? 1 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 5 ... Видно (ну и это понятно), что идут большие группы равных чисел. Давайте подумаем, сколько на каких позициях в этой последовательности у нас будет число $x$? Ясно, что на позициях с номерами от $(x-1)^2+1$ до $x^2$ включительно (собственно, из второго решения выше это тоже довольно понятно). Отлично, давайте их сразу все учтем: s += x * (x * x - (x-1) * (x-1) - 1) -- умножаем $x$ на количество вхождений. Теперь осталось это завернуть в цикл и аккуратно обработать последний (неполный) интервал. Аналогично с кубическими корнями. Сложность $O(\sqrt N)$, вполне успевает.

Задача 2

Учёные Байтландии давно знают, что ДНК (ДезоксирибоНуклеиновая Кислота) содержит генетическую информацию организма. В настоящее время нетрудно извлечь ДНК любого организма, расшифровать этот код и рассмотреть интересующий сегмент для дальнейших исследований. В научных кругах под расшифровкой понимается представление генетического кода в виде строки, состоящей из символов A, C, T и G. Подобная строка полностью описывает код ДНК.

Учёным предстоит ещё очень много работы, чтобы понять все секреты природы, спрятанные в ДНК. Тем не менее, уже имеются большие успехи в этом направлении. Например, не так давно мир узнал о возможности определения уровня эволюции организма по отдельным участкам кода ДНК. Для этого берётся ДНК и выбирается участок из $N$ нуклеотидов, по которому считается степень сложности. Чем выше степень сложности выбранного сегмента, тем большее количество стадий эволюции прошёл организм.

Степень сложности сегмента ДНК определяется следующим образом:

Для сегмента из $N$ нуклеотидов рассматриваются все подсегменты из $K$ последовательных нуклеотидов;

Для каждого подсегмента подсчитывается количество содержащихся в нём нуклеотидов каждого типа (иными словами, вычисляются четыре числа, которые определяют количественную композицию нуклеотидов в подсегменте);

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

После этого открытия учёные начали собирать информацию о степенях сложности ДНК различных организмов. У них уже имеются все необходимые коды ДНК, однако исследование каждой цепочки ДНК вручную занимает очень много времени. Поэтому они попросили вас написать программу, которая позволила бы быстро определять степень эволюции организма. $1\leq N \leq 100\,000$.

Первое, что тут надо сделать -- это понять условие. Когда вы его поняли, задача становится сильно проще. Дана строка из $N$ символов, рассмотрим все ее подстроки из $K$ символов, для каждой подстроки посчитаем, сколько раз в ней встречается каждый символ (тем более что символов бывает всего четыре разных). Надо определить, сколько есть разных подстрок в смысле вот именно количества вхождений отдельных символов.

Ну так уже проще. Давайте сначала, естественно, для каждой такой подстроки посчитаем эти количества вхождений. В итоге должен получиться двумерный массив "в подстроке с номером $i$ буква с номером $j$ входит столько-то раз".


res = []
for i in range(n-k+1):  # именно столько есть подстрок длины k
    a = 0
    c = 0
    t = 0
    g = 0
    for j in range(k):
        if s[i+j] == 'A': 
            a += 1
        if s[i+j] == 'C': 
            c += 1
        if s[i+j] == 'T': 
            t += 1
        if s[i+j] == 'G': 
            g += 1
    res.append([a, c, t, g])

На самом деле это медленно (сложность $O(NK)$), лучше не считать каждый раз заново, а пользоваться результатом для предыдущей строки (будет сложность $O(N)$), но если не придумали ничего лучше, то и так сойдет (но максбалла вы не получите).

Дальше надо понять, сколько в массиве res различных массивов второго уровня. Тут есть три способа. Во-первых, если вы ничего не знаете, то напишите просто тупое попарное сравнение. Сколько-то баллов это наберет.

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

В-третьих, если вы знаете структуру set (есть и в питоне, и в c++), то берете и используете ее без размышлений вообще :)

Конечно, есть и извращенные элементы типа использовать хеширование, но зачем?

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


# в решении выше было
    res.append([a, c, t, g])
# а можно так
    res.append(str(a) + str(c) + str(t) + str(g))
# но это немного рискованно из-за отсутствия разделителей,
# хотя я и не удивлюсь, если это пройдет все тесты.
# Но лучше все-таки добавить разделители:
    res.append(str(a) + " " + str(c) + " " + str(t) + " " + str(g))

Во-вторых, можно просто отсортировывать каждую подстроку, а не считать вхождения:


res = []
for i in range(n-k+1):  # именно столько есть подстрок длины k
    res.append(sorted(s[i:i+k]))

Это скорее всего не прошло бы по времени максимальные тесты, но тем не менее.

Задача 3

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

На первом занятии М-р Тринидад сообщил учащимся, что последовательность чисел $a_1$, $a_2$, …, $a_N$ называется сортированной, если для любого индекса $i < N$ выполняется условие $a_i \leq a_{i+1}$. Затем учитель объяснил наиболее известные алгоритмы сортировки последовательностей. Т.к. учащиеся довольно быстро усвоили материал занятия, учитель решил рассказать о менее известном методе сортировки.

Суть метода проста: последовательность чисел $a_1$, $a_2$, …, $a_N$ делится на $M$ сегментов. Первый сегмент содержит числа с индексами от $1$ до $k_1$, второй – от $k_1 + 1$ до $k_2$, ..., последний – от $k_{M-1} + 1$ до $k_M$. Далее, в процессе сортировки, числа не меняют своего положения в пределах сегментов. Сортировка производится перестановкой сегментов целиком.

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

Вы, как самый продвинутый ученик, решили написать программу, решающую задачу для любой числовой последовательности. $1 \leq N \leq 500\,000$

Это почти что задача "Москва-Сортировочная" из "продвинутых задач на массивы" с уровня 1В, причем это одна из простых задач того уровня. Правда, в Москве-Сортировочной все числа различны, а здесь могут совпадать. Но решение несложно адаптируется, надо только аккуратно учесть одну подставу -- что в тестах типа 1 2 1 2 ответ не 2, а 3.

Задача 4

В Институте Информационной Безопасности (ИИБ) Байтландии учёные разрабатывают новые способы защиты передаваемой и хранимой информации.

Недавно в ИИБ разработан метод безопасной передачи числовых последовательностей, названный «Статистическое шифрование». Идея метода проста: числовая последовательность подвергается процессу шифрования, в итоге получается две последовательности: шифр и ключ.

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

В ИИБ вам сообщили детальную информацию о декодере. На вход поступают следующие данные:

шифрованная числовая последовательность;

ключ шифрования $k_i$ ($1 \leq i \leq K$), который тоже является числовой последовательностью;

параметр $M$, который задаёт размер обрабатываемых блоков последовательности. Блок – это непрерывный участок последовательности из $M$ элементов.

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

Напишите декодер, который будет расшифровывать зашифрованную информацию. $1\leq N \leq 250\,000$

Это уже довольно сложная задача, ее на максбалл решил только один человек. Поэтому я не буду тут писать решение на максбалл (я его с ходу и не знаю), но лишь отмечу, что частичные баллы тут набирались легко -- берете и пишите что вас попросили (хотя условие понять, конечно, довольно сложно, но там есть примечания, в которых все немного подробнее рассказывается). Берете все $M$ блоков и сортируете. Дальше берете максимум из всех первых чисел в блоках, максимум из всех вторых, и т.д. Дальше по последовательности $k_i$ восстанавливаете ответ.

Весь вопрос в том, как сортировать массивы. Если сортировать быстро, то по таблице похоже, что будет 60 баллов, если сортировать квадратичной сортировкой, то, похоже, будет 40 баллов.

Итог

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