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

Revision ru3, by Edvard, 2016-08-25 01:37:55

710A - King Moves

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

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

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

710B - Optimal Point on a Line

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

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

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

710C - Magic Odd Square

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

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

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

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

710D - Two Arithmetic Progressions

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

Запишем уравнение, которое описывает все решения задачи: 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 - Generate a String

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

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

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

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

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 Первая редакция (опубликовано)