421A - Паша и хомяки

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

420A - Стартап

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

420B - Онлайн митинг

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

1) Есть участник с номером i такой, что первое сообщение с его участием  - i.

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

2) Для всех участников первая запись о них начинается с « + ».

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

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

Хитрыми тестами в этой задаче оказались тесты 33 и 34, на которых упали решения многих участников. Тест 33 выглядит так.

4 4

+ 2

- 1

- 3

- 2

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

Тест 34 следующий.

3 3

- 2

+ 1

+ 2

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

420C - Баг в коде

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

Сделаем следующее. Сохраним граф в виде списков смежности, а также создадим массив степеней всех вершин графа и отсортируем его. Будем перебирать одну вершину и считать, сколько существует вершин в пару ей, чтобы получилась нужная пара вершин. Первое, что приходит в голову — это для каждой вершины v добавить к ответу количество вершин u таких, что d[u] + d[v] ≥ p (количество таких вершин можно просто посчитать бинарным поиском, например). К сожалению, это неправильно, поскольку в сумме d[u] + d[v] ребра между v и u учитываются два раза.

Но, давайте посчитаем ответ неправильно, а потом учтем все то, что мы неправильно посчитали. А именно, для каждой вершины пройдемся по списку ее соседей и для каждого уникального соседа вычтем его из ответ, если он добавился туда (если d[v] + d[u] ≥ p). Теперь осталось учесть в ответе все вершины, которые смежны в графе. Это делается простым проходом по ребрам.

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

420D - Фокус со стаканчиками

Решение состоит из двух этапов.

1) Определим возможную исходную перестановку.

Будем идти по заданным запросам. Пусть текущий запрос утверждает, что число a стоит на позиции b. Если a уже раньше встречалось, то пропустим такой запрос. Иначе определим, на какой позиции находится a в искомой перестановке.

Пусть мы уже знаем, что в искомой перестановке число a₁ стоит на позиции b₁, a₂ на позиции b₂, ..., a_k на позиции b_k (b₁ < b₂ < ... < b_k). Так как после объявления позиции числа оно перемещается в самое начало перестановки, то значит до того как мы объявили о позиции a все a_i (1 ≤ i ≤ k) уже находятся перед a. Но при этом некоторые из этих a_i уже находились раньше a в искомой перестановке, а остальные находились позже, но переместились вперед. Найдем их количество. Для этого нужно найти такую свободную позицию p в исходной перестановке, что p + x = b, где x — количество b_i таких, что b_i > x.

Это можно найти с помощью дерева отрезков следующим образом. Будем хранить в вершине дерева отрезков количество уже занятых позиций искомой перестановки на соответствующем подотрезке. Предположим, мы хотим найти p в некотором поддереве. Посмотрим на минимальную позицию в правом поддереве p_rg и на количество занятых там позиций x_rg. Тогда если p_rg + x_rg ≤ b, то нужно продолжать искать в правом поддереве. Если же p_rg + x_rg > b, то нужно продолжать искать в левом поддереве, уменьшив при этом b на величину x_rg. Когда мы нашли p, проверим выполнение условия p + x = b. Если оно не выполняется, то ответ  - 1.

2) Проверим, что последовательность операций корректная.

Пусть мы рассматриваем i-ый запрос, утверждающий, что число a стоит на позиции b. Нужно проверить, что он верен. Если a раньше не встречалось в запросах, то запрос верен, так как мы проверили b еще на первом этапе. Если оно раньше встречалось, найдем такое максимальное j < i, что j-ый запрос также объявляет, в какой позиции находится a. После j-го запроса a перемещается в начало перестановки, а далее другие числа могут передвигать его вправо. Найдем количество различных таких чисел на отрезке запросов [j + 1, i - 1], их должно быть ровно b - 1.

420E - Игра в мяч

Скажем, что в данной задаче у нас есть луч, на котором есть бесконечное число шариков, находящихся на расстояниях, кратных d от начала луча. Заметим, что хотя бы один шарик, который будет посчитан в ответе должен упираться в границу какого-нибудь круга. Также заметим, что если мы рассмотрим любой круг, то количество углов a на которые нужно повернуть наш луч так, чтобы какой-нибудь из шариков лежал на границе этого круга не превосходит 4 * r / d. Назовем такие углы критическими.

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

Заведем массив C такой, что C_i — ответ, если мы повернули луч на угол B_i. Тогда после того как мы нашли k и позиции углов в B, нужно сделать прибавление на отрезке в массиве C. После того как мы обработаем все критические углы всех кругов нужно найти максимум в массиве C.

412A - Плакат

В данной задаче одно из оптимальных решений следующее. Если k - 1 ≤ n - k, то подвинем сначала лестницу на k - 1 позицию влево. Затем n - 1 раз проделаем пару операций: нарисуем i-ый символ названия и подвинем лестницу вправо. После этого нарисуем последний символ названия. Если же k - 1 > n - k, то подвинем сначала лестницу вправо на n - k позиций. Далее также будем рисовать символ и передвигать лестницу влево, и последним действием нарисуем первый символ названия. Суммарное количество требуемых операций равно min(k - 1, n - k) + 2·n - 1.

412B - Настройка сети

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

412C - Строка-шаблон

Будем искать требуемый шаблон посимвольно. Рассмотрим i-ый символ. Если в заданных строках на i-ых позициях есть хотя бы два различных символа, отличных от «?», то в ответе на i-ой позиции должен стоять «?». Если на i-ой позиции во всех строках стоят «?», то мы можем записать в ответ любой символ в качестве i-го. Очевидно, лучше записать не «?», а какую-нибудь букву, например «x». Остается случай, когда на i-ых позициях стоят «?» и какая-то одна и та же буква. Тогда нужно определить, что это за буква и добавить ее в ответ.

412D - Выдача премий

Будем строить искомую перестановку по индукции добавляя по одному сотруднику. Пусть мы уже определили порядок первых k сотрудников: a₁, a₂, ..., a_k. Скажем, что k + 1-ый будет идти за a_k-ым. Если a_k-ый сотрудник должен денег k + 1-ому, то поменяем им местами (получим перестановку a₁, a₂, ..., a_k - 1, k + 1, a_k). Если и a_k - 1-ый сотрудник должен k + 1-ому, то поменяем и их местами, и так далее. Если же все из первых k сотрудников должны k + 1-ому, то он окажется в самом начале перестановки. При аккуратной реализации данный алгоритм будет работать за время O(m), где m — количество отношений долга.

412E - Е-mail адреса

Переберем позицию i такую, что s_i = «@». Посчитаем количество подстрок, являющихся корректными адресами, у которых символ «@» — это s_i. Будем идти влево от i до тех пор, пока не встретим «@» или «.» — символы, которые недопустимы слева от «@». Посчитаем cnt сколько букв на пройденном отрезке — с них могут начинаться корректные адреса. Теперь будем двигаться вправо от i пока будут идти цифры или буквы. Если после этого строка закончилась или следует "@" или "_", то корректные адреса уже не могут получиться. Если же далее идет «.», то пройдем вправо от нее до тех пор, пока встречаются буквы. В каждой из этих букв может закончится корректный адрес, поэтому каждый раз нужно прибавлять к ответу cnt. В описанном выше решении "пройдемся" означает "перебираем циклом". Это можно делать, т.к. в результате по каждому символу мы пройдем не более 2 раз. Итого асимптотика решения O(n).

404A - Валера и X

В данной задаче нужно было проверить, выполняются ли ограничения, описанные в условии. Чтобы это сделать, можно было завести два множества. В одно множество сложить диагональные элементы матрицы, в другое — остальные. Элемент a_i, j стоит на главной диагонали, если i = j, и стоит на побочной, если i = n - j + 1. После того, как мы сложили все элементы в множества, нужно проверить, что размеры обоих множеств равны единице, и элементы этих множеств различны.

404B - Марафон

В этой задаче нужно было заметить, что пройдя расстояние 4·a, Валера окажется в той же точке, откуда стартовал. В момент, когда Валера получит i-ое питание, он пробежит расстояние i·d. Давайте посчитаем величину — сколько полных кругов пробежит Валера по стадиону. Тогда на своем последнем кругу Валера уже пробежал L = i·d - c·4·a метров. В зависимости от этого L можно легко определить позицию Валеры. Например, если 2·a ≤ L ≤ 3·a, то Валера будет находиться в точке с координатами (3·a - L, a). Аналогичным образом разбираются остальные 3 случая.

404C - Восстановите граф

Заметим, прежде всего, что в массиве d должен быть один и только один 0. При этом d[start] = 0 обозначает, что start именно та вершина, от которой Валера считал расстояние до всех остальных. Заметим, что любая вершина u, для которой d[u] = i должна быть соединена ребрами только с вершинами v, у которых d[v] ≥ i - 1. При этом хотя бы для одной вершины v₀ из соседей u должно выполняться d[v₀] = i - 1. Будем строить искомый граф добавляя по одной вершине в порядке увеличения их расстояния до start. Изначально в нашем графе будет одна вершина с номером start. При добавлении вершины u с d[u] = i рассмотрим все вершины v, у которых d[v] = i - 1. Выберем среди таких вершин вершину минимальной степени. Если эта степень равна k, то ответа не существует. Иначе добавим в граф вершину u и ребро (u, v). Если вершин с расстоянием до start равным i - 1 нет, то ответ также  - 1. В противном случае после добавления всех вершин, мы получим граф, удовлетворяющий условиям задачи, который при этом будет деревом, а значит количество ребер в нем n - 1 ≤ 10⁶.

404D - Сапер 1D

Задача решается методом динамического программирования. Будем считать d[i][type] — количество корректных способов заполнить префикс полоски длиной i так, что последняя заполненная клетка имеет один из пяти типов. Типы последних клеток будут следующие:

1. в клетке записано "0"

2. в клетке записано "1" и слева от нее стоит бомба

3. в клетке записано "1" и слева от нее нет бомбы

4. в клетке записано "2"

5. в клетке находится бомба

Когда мы хотим заполнить очередную клетку, мы перебираем, что туда запишем, и проверяем два условия. Во-первых в заданной строке значение заполняемой клетки должно либо совпадать с тем, что мы хотим записать, либо быть равно "?". Во-вторых новый префикс должен оставаться корректно заполненным. Это значит, например, что если мы находимся в состоянии (i, 1) (то есть в последней заполненной клетке записан "0"), то в следующую клетку мы можем либо записать "0" и перейти в состояние (i + 1, 1), либо записать "1" и перейти в состояние (i + 1, 3). Записать "2" мы не можем, так как у клетки с "2" оба соседа должны быть заполнены бомбами. Поставить бомбу после "0" мы не можем по очевидным причинам. Обратите внимание, что записав "1" после "0" мы переходим именно в состояние (i + 1, 3), а в состояние (i + 1, 2) мы можем перейти лишь записав "1" после бомбы. Аналогичным образом разбираются остальные переходы динамики.

404E - Лабиринт 1D

Рассмотрим случай, когда последовательность ходов робота заканчивается буквой "R". Если она заканчивается на "L", то можно заменить в исходной строке все "L" на "R" и все "R" на "L" и ответ от этого не изменится. Покажем, что количество препятствий, которое потребуется Валере, не превосходит 1. Предположим Валера поставил препятствия в какие-то клетки. Будем говорить, что номер препятствия — это номер клетки в которой оно стоит. Рассмотрим среди всех препятствий с отрицательными номерами самое правое (обозначим его obs1), а среди препятствий с положительными — самое левое (обозначим его obs2). Очевидно, что робот не сможет оказаться левее препятствия obs1 и правее obs2. Поэтому требуемое количество препятствий не превосходит двух. Покажем, что Валере не нужно ставить препятствия в клетки с номерами больше нуля. Предположим он поставит препятствие в клетку с номером a > 0. Если робот ни разу не попытается сходить в эту клетку, то, очевидно, препятствие лишнее. Если в какой-то момент робот пытается пойти в клетку a, то в последующем он посетит финишную клетку более одного раза. Это так, потому что на последнем ходу роботу нужно пойти направо, но из клетки a - 1 направо пойти нельзя, а все клетки, которые левее уже были посещены. Таким образом мы получаем, что Валере потребуется не более одного препятствия, которое должно иметь номер меньше нуля.

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

Заметим, во-первых, что по тому, где Валера поставил препятствие, однозначно восстанавливается финишная клетка. Это значит, что количество способов выбрать препятствия и финишную клетку, равно количеству клеток, в которые нужно поставить одно препятствие. Предположим Валера поставил препятствие в клетку с номером b < 0 и робот успешно закончил инструкцию. Заметим, что в этом случае робот пропустит какие-то ходы типа "L", выполнит все ходы типа "R" и последним своим ходом пойдет направо в какую-то не посещенную клетку. Если теперь мы подвинем наше препятствие на одну клетку вправо, то от этого робот может лишь пропустить больше ходов типа "L". Это значит, что финишная клетка может лишь подвинуться вправо. Но так как в прошлый раз мы ее посетили последней, то и новую финишную клетку мы посетим последней. Это в свою очередь значит, что существует какая-то клетка p < 0 такая, что если мы поместим препятствие во все клетки c ≥ p, то робот сможет успешно выполнить инструкцию, а если поместим препятствие в клетку d < p, то не сможет. Эту клетку p можно найти при помощи бинарного поиска и простого моделирования за O(n) на каждой его итерации. Таким образом получаем решение за O(n log n).

Всем привет!)

Завтра 19 марта в 19:30 MSK состоится очередной раунд Codeforces #237 для участников из 2 дивизиона. Традиционно, участники 1 дивизиона могут написать соревнование вне конкурса.

Подготовкой задач занимались Игорь Кудряшов (Igor_Kudryashov) и Геральд Агапов (Gerald). Кроме того, выражаем благодарность Михаилу Мирзаянову (MikeMirzayanov) за прекрасный ресурс Codeforces и Марии Беловой (Delinur) за перевод условий задач на английский язык.

Желаем всем участникам удачи, высокого рейтинга и удовольствия от решения задач)

UPD: Распределение баллов будет стандартное 500 — 1000 — 1500 — 2000 — 2500.

UPD2: Соревнование завершено, благодарим всех за участие.

Поздравляем победителей:

1. Pkqs09
2. juggler
3. zstu_bobo
4. kevinswat
5. Salvare004

UPD3: Разбор задач можно найти здесь

353A - Домино

Обозначим сумму чисел на верхних половинках костей за s₁, а сумму на нижних — s₂. Если изначально s₁ и s₂ четные, то ответ, очевидно, 0. Заметим, что если числа на обеих половинках кости одинаковой четности, то при повороте этой кости четность s₁ и s₂ не меняется. Если же четность чисел на половинках разная, то при повороте кости меняется четность как у s₁ так и у s₂. Из этого следует, что если s₁ и s₂ имеют разную четность, то ответ  - 1. Если же s₁ и s₂ нечетные, то нужно проверить, имеется ли в наборе кость с числами разной четности на половинках. Если имеется, то ответ 1, иначе ответ  - 1.

353B - Две кучки

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

Заметим, что ответ на задачу, это произведение количеств различных чисел в каждой из кучек. Предположим, что все заданные числа различны. В этом случае ответ равен n². Предположим теперь, что есть два одинаковых числа, а все остальные различны. Тогда, если мы их положим в разные кучки, то ответ будет равен n², а если в одну, то n·(n - 1). Очевидно, первый вариант даст большее произведение.

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

353C - Найдите максимум

Рассмотрим старший бит числа m. Если он равен нулю, то во всех в n - 1-ой позиции будет стоять 0, а значит a_n - 1 никак не повлияет на ответ и мы можем выбросить его из набора и считать ответ для массива из n - 1 элемента.

Если же старший бит числа m равен 1, то a_n - 1 для некоторых x будет входить в f(x), а для некоторых — нет. Рассмотрим все x, при которых a_n - 1 не будет входить в f(x). Это, очевидно, . Среди таких x максимальное f(x), очевидно, будет достигаться при x = 2^n - 1 - 1. Попробуем улучшить ответ этим значением.

Теперь нам осталось рассмотреть , среди них найти максимальное f(x) и попробовать улучшить ответ этим значением. Заметим, что во всех таких x на (n - 1)-ой позиции находится 1, поэтому мы можем найти максимальное значение f(y) среди всех и прибавить к нему a_n - 1.

353D - Очередь

Заметим, что если несколько девочек стоит в самом начале очереди, то они никогда не будут двигаться, поэтому удалим их, и будем считать, что очередь начинается с мальчика. Также заметим, что относительный порядок девочек при движении не меняется. Посчитаем для каждой девочки момент времени t_i, начиная с которого она перестанет двигаться в очереди навсегда. Заметим, что для i-ой по порядку девочки t_i ≥ t_i - 1. Будем считать t_i в порядке слева направо. Посмотрим на какой позиции y_i в очереди будет находиться девочка, когда она закончит свое движение, и на какой позиции x_i она находится сейчас. Тогда этой девочке потребуется не менее x_i - y_i времени, чтобы добраться до своего места. Тогда если x_i - y_i > t_i - 1, то t_i = x_i - y_i. Рассмотрим, что произойдет при x_i - y_i ≤ t_i. В момент времени t_i - 1 (i - 1)-ая девочка будет находиться на позиции y_i, поэтому t_i ≥ t_i - 1 + 1. С другой стороны, рассмотрим последний момент времени p, когда i-ая девочка стоит непосредственно за (i - 1), но еще не на позиции y_i. После этого, в момент времени p + 1 (i - 1)-ая девочка меняется местами со стоящим перед ней мальчиком, а i-ая девочка остается на своей позиции. Затем с момента времени p + 2 до t_i - 1 обе девочки меняются местами с впереди стоящими мальчиками. А в момент времени t_i - 1 + 1 i-ая девочка наконец встает на свое конечное место. Отсюда следует, что в этом случае t_i = t_i - 1 + 1.

353E - Антицепь

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

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

Выпишем все вершины в цепочку и пронумеруем слева направо числами от 1 до k. После этого будем считать величину d_i — размер максимальной антицепи, среди вершин с номерами j ≥ i. Тогда, если i > k, то d_i = 0. Иначе мы можем пропустить i-ую вершину и улучшить величину d_i значением d_i + 1. Также мы можем попробовать взять i-ую вершину в ответ. В этом случае нужно пропустить все вершины, которые либо достижимы из i-ой, либо из которых достижима i-ая, взять ответ от следующей, прибавить к нему единицу и попробовать улучшить ответ.

Всем привет!)

Сегодня состоится очередной раунд Codeforces #205 для участников из 2 дивизиона. Традиционно, участники 1 дивизиона могут написать соревнование вне конкурса.

Подготовкой задач занимались Игорь Кудряшов (Igor_Kudryashov) и Геральд Агапов (Gerald). Кроме того, выражаем благодарность Михаилу Мирзаянову (MikeMirzayanov) за прекрасный ресурс Codeforces и Марии Беловой (Delinur) за перевод условий задач на английский язык.

Желаем всем участникам удачи, высокого рейтинга и удовольствия от решения задач)

UPD: В раунде будет использована динамическая система оценки задач.

UPD 2: Соревнование завершено, благодарим всех за участие.

Поздравляем победителей:

1. hos_epic
2. gzh1996n
3. I_LOVE_ELE

UPD 3: Разбор задач можно найти здесь

231A - Команда

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

231B - Магия, волшебство и чудеса

Для того чтобы быстро и элегантно решить эту задачу, можно рассмотреть, каким будет последнее число массива после i итераций. После первой итерации оно будет равно a_n - 1–a_n (при этом количество элементов уменьшится на единицу). После второй –-- a_n - 2–a_n - 1 + a_n. Очевидно, что после n - 1 итерации останется a₁–a₂ + a₃–a₄ + ... + ( - 1)^n + 1·a_n. Таким образом, наша задача состоит в том, чтобы расставить в массиве числа от 1 до l так, чтобы сумма чисел стоящих на нечетных позициях минус сумма чисел на четных позициях была равна заданному d. Тогда мы должны на нечетных позициях набрать число, равное . При этом минимальное число, которое мы сможем набрать , а максимальное –-- .

Поэтому нужно подобрать a_2·k так, чтобы s укладывалось в эти границы. Ограничения позволяли сделать это следующим образом. Расставим сначала на четных позициях единицы. Теперь если s > maxv, то ответ  - 1. Иначе будем увеличивать каждое a_2·k на единицу до тех пор, пока s < minv. Если, даже расставив на всех четных позициях l, окажется, что s < minv, то ответ также  - 1. После того, как мы расставили значения на четных позициях, ставим 1 на всех нечетных местах, и пока сумма этих элементов меньше s увеличиваем каждое из них на допустимую величину.

231C - Прибавляй не прибавляй

Для решения этой задачи нужно было заметить, что второе число ответа всегда совпадает с каким-то из чисел исходного массива. Это можно объяснить следующим образом. Предположим, второе число ответа равно a_j + d для какого-то j и при этом a_j + d ≠ a_i ни для какого i. Это значит, что мы увеличили некоторые числа, меньшие a_j, до значения a_j, а затем эти числа, вместе с некоторыми числами, равными a_j, увеличили до значения a_j + d. Но если бы мы не увеличивали все эти числа до a_j + d, а оставили равными a_j, то потратили бы меньше операций увеличения и при этом улучшили бы ответ.

Используя этот факт можно решать задачу следующим образом. Отсортируем исходный массив по неубыванию. Переберем второе число ответа –-- a_i и посчитаем, какое мы можем получить максимальное первое число ответа. Для того чтобы максимизировать первое число ответа, нам надо увеличить некоторые меньшие числа до значения a_i, при этом используя максимум k операций. Очевидно, что в первую очередь нужно увеличивать те a_j, для которых a_i–a_j минимально. То есть если бы можно было решать задачу за O(n²), то мы бы шли по j от i налево и увеличивали a_j до значения a_i, пока хватает операций. Однако нужно более быстрое решение. Поэтому нам поможет бинарный поиск по ответу. Мы будем бинарным поиском перебирать количество чисел, которые нужно сделать равными a_i. Предположим мы зафиксировали cnt эту величину. Теперь нам нужно за O(1) проверить, можно ли за не более чем k операций сделать cnt чисел равными a_i. Для этого подсчитаем следующую величину . Если эта величина не превосходит k, то мы можем это сделать. Для того чтобы быстро вычислять сумму, нужно подсчитать s_i частичные суммы на префиксе и тогда s_{i - cnt + 1, i} = s_i–s_i–cnt. Итого мы получаем решение за O(n·logn).

231D - Волшебный ящик

В данной задаче, по сути, нужно было проверить, что из точки p = (x, y, z) виден центр грани параллелепипеда. Рассмотрим случай, когда грань находится в плоскости z = z₁. Для того чтобы можно было все вычисления производить в целых числах, умножим все координаты x, y, z, x₁, y₁, z₁ на 2. Возьмем точку и вектор нормали к плоскости, содержащей эту грань, который направлен в сторону от внутренности параллелепипеда, то есть . Рассмотрим также вектор . Если неориентированный угол между этими векторами меньше 90 градусов, то из точки p будет видно точку a. Чтобы просто проверить это условие, нужно вычислить скалярное произведение между векторами и , и если оно строго больше нуля, то угол будет подходящим.

231E - Кактус

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

Теперь, чтобы найти количество путей между вершинами a и b в исходном графе, проделаем следующее. Обозначим за c вершину, которая соответствует вершине a в полученном дереве (это может быть либо отдельная вершина, либо вершина, соответствующая сжатому циклу, в котором лежит a), за d --– вершину, соответствующую b. Подсчитаем величину deg --– количество 1-вершин на пути из c в d в дереве. Тогда несложно понять, что ответ на запрос равен , так как каждый цикл (1-вершина) увеличивает количество возможных путей вдвое (потому что в цикле из одной вершины в другую можно пройти двумя способами).

Таким образом, для ответа на запрос, нам надо быстро считать количество 1-вершин на пути из одной вершины в другую в дереве. Это можно делать следующим образом. Подвесим полученное дерево за какую-нибудь вершину, которую назовем корнем. Подсчитаем для каждой вершины cnt_v — количество 1-вершин на пути до корня (включая корень и саму вершину). Допустим, мы хотим найти количество 1-вершин на пути из a в b. Обозначим за c наименьший общий предок вершин a и b. Тогда количество 1-вершин на пути из a в b, равно cnt_a + cnt_b–2·cnt_c, если c является 0-вершиной и cnt_a + cnt_b–2·cnt_c + 1, если c — 1-вершина. Наименьший общий предок можно искать стандартным приемом –-- методом двоичного подъема. Итого мы имеем решение за O(m + k·logn).

Всем привет!)

Сегодня состоится очередной раунд Codeforces #143 для участников второго дивизиона. Наверное, нет смысла напоминать, что ребята с рейтингом больше 1699 могут поучаствовать в нем вне конкурса.

Авторами задач для данного мероприятия являются Холкин Павел (HolkinPV) и Кузнецов Николай (NALP). В подготовке контеста также участвовали Кудряшов Игорь (Igor_Kudryashov) и Агапов Геральд (Gerald). Отдельную благодарность выражаем создателю прекрасного ресурса Codeforces Михаилу Мирзаянову (MikeMirzayanov) и нашей переводчице Марии Беловой (Delinur).

Распределение баллов по задачам будет определено через некоторое время, следите за изменениями).

Желаем всем получить удовольствие от соревнования и почерпнуть для себя что-то новое и полезное.

UPD: Распределение баллов по задачам будет стандартное 500-1000-1500-2000-2500.

UPD2: Раунд окончен. Благодарим всех за участие. Шесть человек, занявшие первые места решили все 5 задач, поздравляем их с отличным выступлением.

1) teoy

2) gomineral02

3) mrNobody

4) Ryannnnnnn

5) marschenly

6) KuchumovIlya

Разбор задач будет опубликован через некоторое время.

UPD3: Разбор опубликован, его можно найти здесь

200A — Кино

В этой задаче было дано поле размером n × m и k запросов. Каждый запрос –-- это клетка поля. Нужно было для каждого запроса находить ближайшую к заданной не занятую клетку (при этом ближайшая клетка находится по манхэттенской метрике). После этого найденная клетка помечалась как занятая. В задаче предполагалось решение за время . Сначала поясним идею решения, затем покажем, как достигается такая временная оценка. Идея решения состоит в следующем. Прежде всего, если n > m, то повернем матрицу на 90 градусов (далее будет пояснено зачем). Будем хранить две матрицы n × m, в которых для каждой клетки будем хранить ближайшую свободную клетку слева и справа. Пусть теперь приходит запрос клетка (x, y). Будем перебирать величину d на сколько строчек мы отступим вниз и вверх. Когда мы зафиксировали d, то рассмотрим строку, например, x–d (аналогичные действия нужно будет проделать для строки x + d). В данной строке найдем при помощи наших матриц ближайшие свободные клетки слева и справа от клетки (x–d, y) и попробуем улучшить ответ. В тот момент, когда величина d станет больше, чем текущая найденная величина ответа, остановимся, т.к. в этом случае ответ уже не улучшится. После того, как мы найдем ответ на запрос – ближайшую клетку, нужно пересчитать значения в массивах. Это можно делать, используя, например, для каждой строки структуру DSU.

Покажем теперь, почему данное решение работает за время . Предположим, у нас все запросы одинаковы, т.е. одна и та же точка (x, y). Тогда если поле достаточно большое, то все точки будут располагаться в виде квадрата, повернутого на 45 градусов, с центром в точке (x, y). При этом сторона квадрата будет иметь величину порядка . Тогда и диагональ, которую мы рассмотрим в результате решения, описанного выше, имеет величину порядка . Т.е. в каждом запросе мы рассматриваем строчек и в каждой строке мы совершаем O(1) действий. Если поле такое, что квадрат не помещается в него, т.е. слишком узкое либо по вертикали, либо по горизонтали, то получится нечто, похожее на прямоугольник, у которого одна из сторон будет меньше . Тогда повернем поле таким образом, чтобы меньшая сторона этого прямоугольника соответствовала строкам. В результате мы будем проходить при каждом запросе также не более строк и в каждой строке совершать не более O(1) действий. Данная задача предполагалась как самая сложная задача контеста.

200B — Напитки

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

200C — Чемпионат по футболу

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

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

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

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

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

200E — Тракторный институт

В данной задаче по сути было дано четыре числа c₃, c₄, c₅, s. Нужно было найти такие числа 0 ≤ k₃ ≤ k₄ ≤ k₅, что c₃·k₃ + c₄·k₄ + c₅·k₅ = s и при этом |c₃·k₃–c₄·k₄| + |c₄·k₄–c₅·k₅| минимально.

Для начала переберем k₄ так, чтобы s–c₄·k₄ ≥ 0. Затем рассмотрим 4 случая, в зависимости от того, каковы по знаку значения под модулями.

Рассмотрим случай c₃·k₃–c₄·k₄ ≥ 0 и c₄·k₄–c₅·k₅ ≥ 0. Тогда нужно минимизировать c₃·k₃–c₅·k₅. При этом 0 ≤ k₃ ≤ k₄ ≤ k₅ и c₃·k₃ + c₅·k₅ = s–c₄·k₄. Рассмотрим диофантово уравнение c₃·k₃ + c₅·k₅ = s–c₄·k₄. При этом оно может не иметь решений. Рассмотрим случай, когда решения есть. Поскольку c₃, c₅ ≥ 0, то для минимизации c₃·k₃–c₅·k₅ нужно минимизировать k₃ и максимизировать k₅. Все решения диофантового уравнения c₃·k₃ + c₅·k₅ = s–c₄·k₄ можно выразить через один параметр k. Тогда необходимо найти отрезок значений k, при которых k₃ будет подходящим, отрезок, при котором k₅ будет подходящим, пересечь данные отрезки и, если пересечение не пусто, выбрать то значение k, при котором k₅ максимально.

Аналогично рассуждая, нужно разобрать остальные 3 случая и выбрать оптимальные значения k₃ и k₅ для фиксированного k₄. Можно было также заметить, что в каждом из случаев искомая функция линейно зависит от аргумента, а, значит, она принимает минимальное значение на отрезке в одном из его концов. Поэтому можно не рассматривать случаи, а находить отрезки k, при которых k₃, k₅ принимают допустимые значения, и считать целевую функцию в концах этих отрезков. Если при этом для всех фиксированных k₄ не существует решений диофантовых уравнений, или пересечения выше указанных отрезков пустые, то ответ IMPOSSIBLE, иначе нужно выбрать лучшее. Таким образом решение получается за O(s·log(s)) --– перебор k₄, и решение диофантова уравнения при каждом k₄.

Добрый день, друзья)

Предлагаем вашему вниманию уникальный Codeforces Round #126 (Div. 2). Обратите внимание, что Codeforces Round #126 (Div. 2) проводится только сегодня, и только сегодня у вас будет единственная возможность поднять рейтинг в этом соревновании (конечно, порешать задачи с этого раунда вы сможете после его окончания как виртуальный участник, но это не повлияет на рейтинг). Также для участников из первого дивизиона данный раунд будет нерейтинговым.

В подготовке раунда принимали участие студенты Саратовского Государственного университета Николай Кузнецов (NALP), Павел Холкин (HolkinPV), Игорь Кудряшов (Igor_Kudryashov) и Геральд Агапов (Gerald). Выражаем также благодарность создателю Codeforces Михаилу Мирзаянову (MikeMirzayanov) за прекрасную систему, сотруднику штаба Codeforces Марии Беловой (Delinur) за отличный перевод условий, а также Александру Куприну (Alex_KPR) за помощь при организации данного раунда.

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

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

Желаем всем побольше правильных идей и изящных решений.

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

1. Andreos

2. jma127

3. iensen

4. Spider-man

5. MrPapaya

Разбор задачи "E. Помощник"

Для решения задачи, во-первых, необходимо было аккуратно считать входные данные и для удобства перевести все времена, заданные в формате day, hour, minute в минуты. Это можно было сделать, используя формулу newTime = (day - 1) * 24 * 60 + hour * 60 + minute. 

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

Далее для каждого студента следует посчитать величину deadline_i --- такую наибольшую свободную минуту с начала сессии, что если Валера закончит выполнять задание в эту минуту, то он получит вознаграждение от соответствующего студента. Очевидно, что если во время сдачи экзамена i-ым студентом, Валера не будет спать или кушать, то deadline_i будет равно минуте, предшествующей началу экзамена, иначе deadline_i будет соответствовать последней свободной минуте, предшествующей сну или трапезе. Кроме того, если свободной минуты с начала сессии не найдется или Валера не сможет помочь i-ому студенту, то определим в этом случае deadline_i = -1.

Теперь отсортируем всех студентов по неубыванию величины deadline и воспользуемся методом динамического программирования. Состояниями "динамики" будут два параметра i --- количество обработанных студентов (т.е. тех, для которых задачи уже решены) и j --- номер свободной минуты, начиная с которой Валера может начать выполнять задания для очередного студента. Значением "динамики" будет максимальная прибыль, которую Валера сможет получить, достигнув соответствующего состояния.

Очевидно, возможны два перехода из состояния i, j:

1. в состояние i + 1, j --- в этом случае Валера не будет решать задачи для i-го студента
2. в состояние i + 1, j + time[i] (где time[i] --- время, необходимое для решения задач i-го студента) --- в этом случае Валера будет решать задачи для i-го студента, и к его прибыли прибавится вознаграждение, которое этот студент готов заплатить. Однако такой переход возможен лишь в том случае, когда t(j + time[i]) не превосходит deadline_i. 

После того, как будут посчитаны значения для всех возможных i, j, ответом на задачу будет максимум в n-ой строке соответствующего массива (где n --- суммарное число студентов).

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

Разбор задачи "A. Что у нас на ужин?"

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

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

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