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

Revision ru4, by Edvard, 2016-08-25 01:51:17

710A - Ходы короля

Легко видеть, что в задаче возможно всего три случая. Если король находится углу доски, то у него 3 возможных хода. Если он стоит на краю доски, то у него 5 возможных хода (если конечно он не в углу). Наконец, если король не стоит на краю доски, то у него всего 8 возожных хода.

Решение на С++

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

710B - Оптимальная точка на прямой

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

Решение на C++

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

710C - Магический нечётный квадрат

Задачу предложил Resul Hangeldiyev Resul.

Решение задачи легко получить из второго примера. Легко видеть, что если расставить все нечётные числа в виде ромба посередине квадрата, то мы получим магический квадрат.

Решение на C++

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

710D - Две арифметические прогрессии

Эту задачу я уже давно хотел дать на раунд, она мне казалась очень стандартной, но я недооценил её сложность.

Запишем уравнение, которое описывает все решения задачи: a1k + b1 = a2l + b2 → a1k - a2l = b2 - b1. Имеем линейное диофантово уравнение с двумя неизвестными: Ax + By = C, A = a1, B =  - a2, C = b2 - b1. Его решение имеет вид: , где последнее уравнение решается с помощью расширенного алгоритма Евклида, а p произвольное целое число. Далее нам нужно удовлетворить двум условиям: и . Поскольку мы знаем знаки чисел A и B, последние уравнения задают отрезок возможных значений для переменной p, длина этого отрезка и является ответом на задачу.

Решение на C++

Сложность: O(log(max(a1, a2))).

710E - Генерация строки

Задачу предложил Zi Song Yeoh zscoder.

У этой задачи есть простое решение, которое участники описали в комментариях. Моё решение несколько сложнее. Будем решать задачу с помощью динамического программирования. zn — наименьшее время, необходимое для получения n букв 'a'. Теперь рассмотрим переходы: переходы на дописывание одной буквы 'a' будем обрабатывать как обычно. Переходы на умножения на два и вычитание единицы будем обрабатыват одновременно: будем считать, что сразу после умножения числа i на двойку мы сразу сделаем i вычитаний и далее будем проталкивать от нашего числа вперёд такие обновления. Легко видеть, что такие обновления никогда не никогда не вкладываются, поэтому их можно хранить в очереди, дописывая очередное обновление в конец очереди, и, забирая лучшее обновление с начала очереди. Решение достаточно сложное на объяснение, но очень короткое, поэтому лучше посмотреть код :-)

Решение на C++

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

710F - Операции над множеством строк

Задачу предложил Александр Кульков adamant.

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

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

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

Легко видеть, что каждая строка перебросится не более logm раз и на каждый запрос мы умеем отвечать за O(logm).

Решение на C++

Сложность: O((slen + m)logm), где slen — суммарная длина всех строк во входном файле.

Tags educational round 16, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Edvard 2016-08-30 01:56:47 4835
en5 English Edvard 2016-08-30 01:11:02 1545
en4 English Edvard 2016-08-30 00:41:38 1965
en3 English Edvard 2016-08-30 00:04:38 2 Tiny change: 'ncorner than the answ' -> 'ncorner then the answ'
en2 English Edvard 2016-08-30 00:03:23 945
en1 English Edvard 2016-08-29 23:57:58 1839 Initial revision for English translation
ru4 Russian Edvard 2016-08-25 01:51:17 4900 Мелкая правка: 'ность: $O(slen\cdot logm)$, гд' -
ru3 Russian Edvard 2016-08-25 01:37:55 1633
ru2 Russian Edvard 2016-08-25 01:24:39 1967 Мелкая правка: 'уравнение получается решается ' -> 'уравнение решается '
ru1 Russian Edvard 2016-08-25 01:08:13 2829 Первая редакция (опубликовано)