Разбор задач Educational Codeforces Round 9

Revision ru10, by Edvard, 2016-03-02 17:05:02

632A - Бабушка Лаура и яблоки

Задача предложена пользователем unprost.

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

С++ solution by me.

С++ solution by unprost.

Сложность: O(p).

632B - Алиса, Боб, две команды

Задача предложена пользователем Lewin Gan Lewin.

Посчитаем частичные суммы на префиксах отдельно для всех чисел (в массиве s1) и отдельно для чисел напротив, которых стоит буква B (в массиве s2). Теперь мы можем за O(1) вычислять сумму на любом подотрезке, а также сумму на любом отрезке по числам напротив буквы B.

Переберем теперь префикс или суффикс и посчитаем сумму в случае его изменения по формуле: sum(s1, 0, n - 1) + sum(s2, 0, i) - 2·sum(s1, 0, i) для префикса и sum(s1, 0, n - 1) + sum(s2, i, n - 1) - 2·sum(s1, i, n - 1) для суффикса.

C++ solution by me.

Python solution by Lewin.

Сложность: O(n).

632C - Наименьшая конкатенация строк

Задача предложена пользователем Lewin Gan Lewin. Доказательство транзитивности также принадлежит ему.

Отсортируем все строки по компаратору a + b < b + a и сконкатенируем их в получившемся порядке. Докажем, что ответ оптимальный. Пусть эта операция транзитивна (то есть из ). Рассмотрим оптимальный ответ в котором есть пара строк, находящихся по этому отношению в обратном порядке. Поскольку это отношение транзитивно, то без потери общности можно считать, что это пара соседних строк. Но тогда мы их можем просто поменять местами и улучшить ответ.

Докажем транзитивность отношения. Будем смотреть на эти строки как на числа в 26-ной системе счисления. Тогда отношения a + b < b + a эквивалентно . Последнее есть просто отношение для действительных чисел. Таким образом, мы доказали транзитивность отношения a + b < b + a.

C++ solution by me.

Python solution by Lewin.

Сложность: O(nLlogn), где L — наибольшая длина строки.

632D - Самая длинная подпоследовательность

Задачу предложил Денис Безруков pitfall.

Пусть cntx количество повторений числа x в заданном массиве (понятно, что числа большие m можно не рассматривать). Переберём и 1 ≤ k, x·k ≤ m и увеличим значение в позиции k·x в некотором массиве z на величину cntx. Таким образом, значение zl равно количеству чисел в исходном массиве делящих l. Найдём минимальное l с максимальным значением zl (1 ≤ l ≤ m). Легко видеть, что ответом на задачу будут числа делящие l.

Оценим время работы решения. Количество пар (k, x) можно сверху оценить как .

C++ solution by me.

Java solution by pitfall.

Сложность: O(n + mlogm).

632E - Вор в магазине

Задачу предложил Алексей Чесноков CleRIC.

Пусть k = 2, тогда это стандартная задача которая может быть решена с помощью БПФ (быстрого преобразования Фурье). А решается она следующим образом: рассмотрим многочлен в которого коэффициент при i-й степени равен единице если и только если в заданном массиве есть число i. Возведём этот многочлен в квадрат, тогда те i коэффициент при которых в квадрате не равен 0 будут находиться в ответе. Легко обобщить это решение на случай произвольного k. Нужно просто исходный многочлен возвести в k-ю степень. Это, конечно, нужно сделать с помощью бинарного возведения в степень. Сложность получается O(WlogWlogk), где W — максимальная сумма.

Заметим, что это решение можно улучшить. Зачем возводить в степень многочлен, когда можно возводить в степень его образ (то есть его ДПФ)? Единственное, что нас может остановить это то, что в случае комплексного БПФ будут получаться очень большие числа (порядка 1000-х степеней) и соответственно никакие вещественные типа нас не спасут). Но это можно сделать в целых числах используя теоретикочисловое преобразование Фурье (ТПФ). У этого решения есть проблема, что при преобразовании (прямом или обратном) какие-то коэффициенты могут случайно обнулиться по модулю простого из ТПФ, но на самом деле коэффициент не ноль. Это можно обойти случайным выбором простого (а лучше двух или трёх), чтобы никто не мог взломать решение. Таким образом, получаем сложность O(W(logW + logk)).

Основное авторское решение было со сложностью O(WlogWlogk) с комплексным Фурье, второе с той же сложностью но по модулю, третье было с улучшенной асимптотикой (некоторые участники тоже это сдали можете попробовать взломать их, они вроде не выбирали модуль случайным образом).

С++ solution, complex FFT by me.

С++ solution, NTT by me.

С++ solution, improved NTT by me.

С++ solution by CleRIC.

P.S.: Чтобы решение было быстрым нужно каждый раз умножать многочлены нужной степени, а не степени 220.

Сложность: O(WlogWlogk) или O(W(logW + logk)), в зависимости от смелости кодера :-)

632F - Волшебная матрица

Задача предложена пользователем Lewin Gan Lewin. Решение и доказательство также принадлежат ему.

Рассмотрим полный граф с весами рёбер aij. Обозначим Bij — минимальное значение максимального ребра на пути из вершины i в вершину j. Очевидно aij ≥ Bij по определение Bij.

Если матрица волшебная мы можем выбрать произвольную последовательность k1, k2, ..., km и получить aij ≤ max{ai, k1, ak1, k2, ..., akm, j} (для этого нужно последовательно применить третье неравенство для волшебной матрицы). Также легко показать, что если это условие выполнено, то матрицы волшебная (нужно просто взять m = 1 и выбрать произвольное k1).

Таким образом, мы получили, что матрица волшебная тогда и только тогда, когда aij ≤ Bij. Пользуясь неравенством aij ≥ Bij окончательно получаем ai, j = Bi, j.

Теперь нам нужно быстрый способ подсчёта значений Bij для всех пар (i, j). Это можно сделать вычислым MST (минимальное покрывающее дерево графа), поскольку MST минимизирует максимальное ребро на путях между всеми парами вершин. Таким образом, решение выглядит следующим образом: сначала нужно найти MST (например, алгоритмом Прима за O(n2)), а затем нужно найти наибольшее ребро на пути из i в j и проверить, что оно равно aij (я это делал с помощью бинарного подъёма по дереву, но это можно делать во время построения MST). И, конечно, нужно не забыть предварительно проверить матрицу на симметричность и нули на диагонали.

P.S.: К сожалению в этой задаче мы не могли увеличить n, поскольку тесты здесь очень специфические (и уже имели размер порядка 67MB) и генератором их задавать было нельзя. Большинство решений, которые сдали участники на контесте использует bitset-ы и работает за , где b = 32 или b = 64.

C++ solution, binary lifts by me.

Java solution by Lewin.

Сложность: O(n2logn) или O(n2).

Tags учебный раунд 9, разбор задач

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Edvard 2016-03-03 02:14:37 138
ru12 Russian Edvard 2016-03-03 02:04:28 140
ru11 Russian Edvard 2016-03-02 17:52:11 122
en6 English Edvard 2016-03-02 17:51:16 2062
en5 English Edvard 2016-03-02 17:29:46 963
en4 English Edvard 2016-03-02 17:17:52 1105
ru10 Russian Edvard 2016-03-02 17:05:02 180
en3 English Edvard 2016-03-02 17:03:47 748
en2 English Edvard 2016-03-02 16:58:00 686
ru9 Russian Edvard 2016-03-02 03:33:59 39
en1 English Edvard 2016-03-02 03:33:00 1838 Initial revision for English translation
ru8 Russian Edvard 2016-03-02 03:24:21 2035 Мелкая правка: '_2},\ldots\n,a_{k_m,j}' -
ru7 Russian Edvard 2016-03-02 02:55:42 4
ru6 Russian Edvard 2016-03-02 02:46:07 2299
ru5 Russian Edvard 2016-03-02 02:11:36 2
ru4 Russian Edvard 2016-03-02 02:08:48 870 Мелкая правка: 'руков [used:pitfall].' -
ru3 Russian Edvard 2016-03-02 01:36:50 1379 Мелкая правка: 'ость: $O(n logn l)$, где $l$ --- наиб' -
ru2 Russian Edvard 2016-03-02 01:14:49 776
ru1 Russian Edvard 2016-03-02 01:03:34 748 Первая редакция (опубликовано)