Разбор Codeforces Round #325

Правка ru5, от Edvard, 2015-10-12 14:46:40

Div2 problem A 586A - Alena's Schedule

Задачу подготовил adedalic.

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

Div2 problem B 586B - Laurenty and Shop

Задачу подготовил Oleg_Smirnov.

Назовем путь i-м (0 ≤ i ≤ n - 1), если мы, выходя из дома, сначала i раз идем налево, потом переходим проспект и снова n - 1 - i раз идем налево. Введем обозначение di — время, которое нам придется ждать на светофорах на i-м пути. Если рассмотреть путь из магазина домой с конца, то получится пути из дома в магазиг, поэтому искомый путь есть два разных пути из дома в магазин. Значит ответом на задачу является сумма наименьшего и второго по величине значения di. Значение di легко пересчитывается из значения di - 1, таким образом все di можно посчитать за один проход.

Асимптотическая сложность решения: O(n).

Div2 problem C / Div1 problem A 585A - Gennady the Dentist

Задачу подготовил Neon.

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

Асимптотическая сложность решения: O(n2).

Div2 problem D / Div1 problem B 585B - Phillip and Trains

Задачу подготовил IlyaLos.

В задаче требовалось просто промоделировать игру. Это можно сделать с помощью обхода в глубину, ширину или динамического программирования. Состоянием является пара чисел x, y — позиция Филиппа в туннеле, а значением \texttt{true} или \texttt{false} в зависимости от того, можем ли мы попасть из стартовой позиции в x, y. Положения поездов в каждый момент времени определяются однозначно.

Асимптотическая сложность решения: O(n).

Div2 problem E / Div1 problem C 585C - Alice, Bob, Oranges and Apples

Задачу подготовил Edvard.

Поймем для начала, что означает процесс описанный в условии. Если нарисовать дерево переходов по буквам \texttt{A} и \texttt{B}, то получится дерево Штерна-Броко (https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A8%D1%82%D0%B5%D1%80%D0%BD%D0%B0_%E2%80%94_%D0%91%D1%80%D0%BE%D0%BA%D0%BE). Пусть апельсины это значения знаменателя дроби, а яблоки — числителя. На каждом шагу у нас есть две дроби (изначально ) и мы заменяем либо первую дробь на их медианту, либо вторую. Таким образом, первая дробь есть первый предок влево от медианты, а вторая — первый предок вправо. Таким образом, искомый процесс это просто процесс поиска дроби в дереве Штерна-Броко, который завершается тем, что текущая медианта совпадает с дробью, которую мы ищем (момент окончания игры, описанный в условии). Значит, числа x, y заданные в условии это просто дробь, которую мы ищем. Отсюда следует, что ответа не существует, если x не взаимнопросто с y (поскольку таким дробей нет в дереве Штерна-Броко). Пусть теперь мы хотим найти дробь в дереве. Понятно, что если x > y, то мы сначала перейдем в правую ветку. Более того мы можем считать, что теперь ищем дробь и никуда не спускались. Если же x < y, то нам нужно спуситься в левую ветку и можно считать, что мы ищем дробь и пока никуда не спускались. Эти рассуждения легко формализовать, чтобы получить строгое доказательство. Таким образом, решение задачи сводится к выполнению алгоритма Евклида для пары чисел x, y. Как известно время работы алгоритма Евклида O(logn) (дольше всего алгоритм Евклида работает на двух последовательных числах Фибоначчи), значит длина ответа тоже растет как логарифм.

Асимптотическая сложность решения: O(logn).

Div2 problem F / Div1 problem D 585D - Lizard Era: Beginning

Задачу подготовил danilka.pro.

Для решения этой задачи воспользуемся приемом \texttt{meet-in-the-middle}. А именно переберем для первых (первая половина) заданий с какими спутницами главный герой будет путешествовать. Пусть при этом симпатия первой спутницы оказалась равна a, второй — b, а третьей c. Пусть существует способ выбрать спутниц для последующих (вторая половина) заданий так и пусть симпатии при этом будут равны a', b', c'. Тогда, чтобы по всем заданиям суммы симпатий были одинаковы необходимо и достаточно, чтобы a - b = b' - a и b - c = c' - b'. Теперь для решения задачи достаточно перебрать первую половину и сохранить в некоторой структуре данных тройки чисел a - b, b - c, a (третье число нужно для максимизации ответа в случае равенства). Далее нужно перебрать вторую половину и найти в структуре данных значения b' - a', c' - b', m, где m — максимальное третье значение которое есть в структуре данных. В качестве структуры данных можно использовать map < pair < int, int > , int >  в языке C++, первые два числа это значение a - b, b - c, а третье — максимальное a соответствующее первым двум. Также можно все тройки сложить в один большой массив, отсортировать его и бинарным поиском находить необходимые значения.

Асимптотическая сложность решения: , где logC — константа, появляющаяся вместе со структурой данных.

Div2 problem G / Div1 problem E 585E - Present for Vitalik the Philatelist

Задачу подготовил gridnevvvit.

Пусть мы хотим посчитать количество подмножеств с НОД равным 1 — число A. Посчитаем это количество с помощью формулы включений-исключений: сначала скажем, что все подмножества нам подходят. Таких подмножеств 2n. Теперь вычтем подмножества с НОД кратным 2. Количество таких множеств 2cnt2 - 1, где cnti — количество чисел, делящихся на i. Далее вычитаем 2cnt3 - 1. Подмножества с НОД кратным 4 мы учли вместе с двойкой. Далее вычитаем 2cnt5 - 1. Теперь заметим, что подмножества с НОД кратным 6 мы вычли уже дважды: сначала с двойкой, затем с тройкой, поэтому давайте прибавим количество таких подмножеств 2cnt6 - 1. Продолжая этот процесс получаем, что для числа d, к ответу нужно прибавить величину μ(d)(2cntd - 1), где μ(d) равно 0, если d делится на полный квадрат, 1, если количество простых в факторизации d четно и  - 1 в противном случае. Значит числа, делящиеся на полный квадрат мы можем не суммировать, поскольку они входят с коэффициентом 0. Для подсчета значений cnti достаточно факторизовать все числа и для каждого за 2k перебрать делитель, со значением μ(d) ≠ 0. Теперь легко понять, что количество подмножеств с НОД большим 1 равно B = 2n - A. Теперь для решения задачи давайте переберем марку, которую купит Виталик ai. Пересчитаем число B так, как если бы числа ai не было в множестве. Для этого нужно просто вычесть те слагаемые на которые повлияло число ai. Это можно сделать за 2k, где k — количество простых в факторизации числа ai (снова нужно перебрать делители ai со значением μ(d) ≠ 0). Теперь поймем какие подмножества дадут НОД равный 1 вместе с выбранной маркой. Понятно это те подмножества НОД которых больше 1, но при этом не делится ни на один делитель ai. Для этого снова воспользуемся формулой включений-исключений. Для каждого делителя d числа ai вычтем из B значение 2cntd - 1. Таким образом, мы получим количество способов Bi выбрать подмножество c НОД большим 1, но при это взаимнопростым с ai. Ответом на задачу является сумма всех di. Наибольшее количество простых в факторизации числа не превосходящего 107 равно 8. Факторизацию чисел можно выполнить с помощью линейного алгоритма поиска минимального делителя чисел от 1 до n, либо с помощью решета Эратосфена за время O(nloglogn). Асимптотическая сложность решения: O(C + n2K), где , а K — наибольшее количество простых в факторизации чисел ai.

Div2 problem H / Div1 problem F 585F - Digits of Number Pi

Расмотрим все подстроки строки s длины . Сложим все эти строки в бор, посчитаем суффиксные ссылки и построим автомат по цифрам. Это можно сделать за линейное время с помощью алгоритма Ахо-Корасик. Теперь для решения задачи посчитаем динамику zivb1b2b в котором состояние описывается пятеркой чисел: i — количество цифр которые мы уже поставили в искомом числе, которое встречается \texttt{наполовину}, v — в какой вершине бора мы находимся, b1 — равен ли префикс числа, которое мы набираем префиксу числа x, b2 — равен ли префикс числа, которое мы набираем префиксу числа y, b — находится ли некоторая подстрока длина на уже набранном префиксе в боре (значения b1, b2, b — равны либо 0, либо 1). Значением динамики является количество способов набрать префикс с заданным набором свойств. Для того, чтобы сделать переход нужно перебрать цифру, проверить что мы не вышли за границы отрезка [x, y], перейти от вершины v к следующей вершине по автомату и заданной цифре. Ответом является сумма по всем v, b1, b2 zbvv1v21.

Асимптотическая сложность решения: O(nd2).

Задачу подготовил Edvard.

Теги cf-325, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en12 Английский Edvard 2015-10-15 19:26:24 6 Tiny change: 'he value $2^{cnt_d}-1$ from $B$' -> 'he value $\mu (2^{cnt_d}-1)$ from $B$'
en11 Английский Edvard 2015-10-14 00:31:12 105
ru17 Русский Edvard 2015-10-14 00:27:58 285
ru16 Русский Edvard 2015-10-13 18:44:39 1 Мелкая правка: 'b = b' - a$ и $b - c' -> 'b = b' - a'$ и $b - c'
en10 Английский Edvard 2015-10-13 18:44:22 1 Tiny change: 'b = b' - a$ и $b - c' -> 'b = b' - a'$ и $b - c'
en9 Английский Edvard 2015-10-12 23:51:36 10516 Tiny change: 'n2 \rceil}$} \log ({3' - (published)
en8 Английский Edvard 2015-10-12 23:16:47 6
en7 Английский Edvard 2015-10-12 23:06:27 4 Tiny change: 'answer is sum by al' -> 'answer is the sum by al'
en6 Английский Edvard 2015-10-12 22:56:38 12 (saved to drafts)
ru15 Русский Edvard 2015-10-12 22:54:57 10 (опубликовано)
en5 Английский Edvard 2015-10-12 22:52:14 258
en4 Английский Edvard 2015-10-12 22:48:02 1 Tiny change: 'able by $2). Next we' -> 'able by $2$). Next we'
en3 Английский Edvard 2015-10-12 22:34:17 125
en2 Английский Edvard 2015-10-12 22:29:23 3616 (saved to drafts)
ru14 Русский Edvard 2015-10-12 22:26:03 2 Мелкая правка: 'мма всех $d_i$. Наибо' -> 'мма всех $B_i$. Наибо'
ru13 Русский Edvard 2015-10-12 22:16:59 9 Мелкая правка: 'значение $2^cnt_d-1$. Таким о' -> 'значение $\mu(d) (2^cnt_d-1)$. Таким о'
ru12 Русский Edvard 2015-10-12 21:45:28 18 Мелкая правка: 'намику $z_i_v_{b_1}_{b_2}_b$ в которо' -> 'намику $z_{i, v, b_1, b_2, b}$ в которо' (опубликовано)
en1 Английский Edvard 2015-10-12 21:44:30 9316 Initial revision for English translation (saved to drafts)
ru11 Русский Edvard 2015-10-12 18:38:48 18 Мелкая правка: ', b_2$ $z_b_v_{v_1}_{v_2}_1$.\n\nАсим' -> ', b_2$ $z_{b, v, v_1, v_2, 1}$.\n\nАсим'
ru10 Русский Edvard 2015-10-12 15:33:23 6
ru9 Русский Edvard 2015-10-12 15:32:40 12
ru8 Русский Edvard 2015-10-12 14:49:09 0 (опубликовано)
ru7 Русский Edvard 2015-10-12 14:48:56 2 Мелкая правка: 'n2 \rceil}) logC$, где $lo' -> 'n2 \rceil} logC)$, где $lo'
ru6 Русский Edvard 2015-10-12 14:48:28 326
ru5 Русский Edvard 2015-10-12 14:46:40 716
ru4 Русский Edvard 2015-10-12 14:45:00 130
ru3 Русский Edvard 2015-10-12 14:24:26 104
ru2 Русский Edvard 2015-10-12 14:17:30 9857
ru1 Русский Edvard 2015-10-12 12:03:52 414 Первая редакция (сохранено в черновиках)