362A - Встреча полуконей

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

362B - Петя и лестницы

Обратим внимание на то, что число грязных ступенек  ≤ 3000. Для того, чтобы решение существовало, необходимо проверить, что ступенька с номером 1 и ступенька с номером n чистые, а также что в отсортированном массиве не встречается больше двух подряд идущих ступенек. Отсортируем массив, и проходом по нему узнаем нет ли трех подряд идущих номеров грязных ступенек, а также проверим, не являются ли ступеньки 1 и n грязными.

362C - Сортировка вставками

Количество выполнений функции swap — это количество инверсий во входной перестановке. Несложно заметить, что менять местами имеет смысл только такие элементы a_i, a_j, что i < j и a_i > a_j (иначе количество инверсий только увеличится). Пусть d_i, j — количество таких элементов перестановки с индексами от 0 до i включительно, которые строго меньше j. Тогда при обмене элементов c индексами i и j количество инверсий станет равным old - 2 * (d_i, ai + d_j, aj - d_i, aj - d_j, ai) - 1, где old — количество инверсий в исходной перестановке. Достаточно перебрать все пары элементов и выбрать из них те, которые позволяют минимизировать количество инверсий. Доказательство этой формулы оставим читателю в качеству упражнения.

362D - Дураки и дороги

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

Асимптотика — O(n + m + plogn).

362E - Петя и трубопровод

Представим данную задачу как задачу нахождения максимального потока минимальной стоимости. Построим следующую сеть. Истоком будет 1-ый резервуар, стоком — n-ый резервуар. Каждая труба из резервуара u в резервуар v в сети будет представлена двумя дугами из вершины u в вершину v — первое ребро будет иметь пропускную способность c_uv и стоимость 0, второе — бесконечную пропускную способность и стоимость 1. Таким образом, ответом на задачу будет величина максимального потока в этой сети стоимости не более чем k. Ее можно найти стандартным алгоритмом увеличивающих путей.

UPD1. Добавлен разбор задач A и B. UPD2. Добавлен разбор задачи C.

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

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

Приехав 5-го числа на место, оказалось, что я добрался туда первым из всех Саратовских ребят, но по территории уже ходили участники из других городов, осматривая окрестности. Мне выдали ключ от первого домика, куда я скинул свои вещи и сразу достал ноутбук. И тут выяснилось, что электричества нет :) К счастью, его достаточно быстро включили и особых проблем это не доставило. Больше напрягало то, что 3G фактически не было, и даже обычный EGDE грузил инет с трудом (потом выяснилось, что у меня ситуация лучше, чем у остальных — у многих он вообще не работал). С другой стороны, это позволило меньше отвлекаться от, собственно, процесса обучения. Особо отдыха нам не дали, и в день заезда уже был первый нетематический контест. Первое, что меня удивило почти сразу — насколько лучше пишется код на открытом воздухе и насколько приятнее думается над задачами, когда смотришь на Волгу. И порадовало то, что многие задачи были на английском — лишний раз немного прокачать язык никогда не бывает лишним.

Контесты писали в основном в корпусе в двух комнатах, где стояли столы и на полу валялись куча удлинителей и пилотов для подключения ноутбуков участников. Там же, в одной из комнат (имеющей кодовое имя "Красный уголок") был сервер и Wi-Fi точка. Некоторые команды, живущие в корпусе, писали контест прямо из своих комнат, приходя только за условиями и распечатками. В жаркие дни я им немного завидовал, потому что в общей комнате было довольно душно. Правда, спасал кулер с водой. Вообще, первые дни погода была достаточно прохладной, и купаться в Волге я не решался. Но где-то на пятый день потеплело и после контестов было чертовки круто пойти и залезть в воду.

В целом расписание было достаточно плотным — каждый день 5-часовой контест + каждые 2-3 дня разбор задач + нам прочитали, если не ошибаюсь, 6 лекций + дорешивания. Вечера после ужина были относительно свободными — они были оставлены на дорешивание задач, а в некоторые дни на сауну. В целом же участники были вольны заниматься тем, чем хочется. И этим усиленно пользовались некоторые Саратовские участники :). Вообще, я не очень знаю, как проводили вечера другие ребята, так что буду рад если они в комментариях раскроют мне эту тайну.

По поводу лекций. Не знаю мнения других, но мне они очень понравились — мне кажется, при должном желании можно было достаточно легко понять материал, который нам читали — лекторы (MikeMirzayanov, Fefer_Ivan и Gerald) объясняли все достаточно подробно, давали примеры кода и охотно отвечали на вопросы, за что им большое спасибо :) Тематические контесты по материалам лекции приносили еще большее понимание материала (думаю, я не скоро забуду, как неправильно переписал код в реализации алгоритма Укконена с доски, который убивает ассимптотику до N^2, и потом минут 40 дебагал его на листочке, параллельно поняв, как он работает). Нетематические контесты были тоже очень удачно составлены и давали возможность как слабым участникам, так и сильным показать все, на что они способны.

Ну и несколько слов о последнем дне. Вообще, еще до последнего контеста было понятно, что в общем зачете Уральскую команду уже не обогнать никому, а вот за 2е место была очень жесткая борьба, которую я с удовольствием наблюдал. Сразу после контеста разрыв между двумя Саратовскими командами, занимающими 2е и 3е места была около 0,5 балла, и на обеде было объявлено, что дорешивание закрывается через 30 минут и таблица результатов замораживается. После этого эти две команды сели и начали пытаться дорешать хоть что-то, чтобы добавить себе баллов. И обе команды сдали по одной задаче, получив итоговый разрыв всего в 0,15 балла. Следить за этим было круче, чем смотреть какой-нибудь ЧМ по футболу :)

Ну а после было награждение команд-победителей, раздача футболок и грамот, после чего начали готовить к вечернему банкету — ходить за углем и шампурами, закупаться в магазине и т.п. После ужина начали жарить шашлыки, играть в волейбол и пить пиво. Отдельное спасибо тем, кто готовил шашлыки и вообще помогал организовывать банкет. Было круто :) Правда, разошлись все довольно рано — видимо, за десять дней все довольно-таки измотались.

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