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

Revision ru9, by Edvard, 2016-06-16 00:45:21

678A - Вася любит числа

Задачу предложил Әбдірахман Исмаил bash.

Нам нужно найти минимальное x, что x * k > n. Легко видеть, что . Для подробного знакомства с математическими функциями пола и потолка я рекомендую книгу авторов Грэхем, Кнут, Паташник "Конкретная математика". В этой книге есть отдельная глава, посвящённая этим функциям и их свойствам.

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

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

678B - Такой же календарь

Задачу предложил Артур Яворски KingArthur.

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

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

Сложность: O(1) — легко видеть, что количество итерация не превосходит небольшой константы.

678C - Мила и шоколад

Задачу предложил Sheikh Monir skmonir.

Легко видеть, что в оба цвета мы можем покрасить доски с номерами кратными lcm(a, b) — НОК чисел a и b. Очевидно, что эти доски выгоднее красить в более дорогой цвет. Таким образом, ответ равен: .

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

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

678D - Итерированная линейная функция

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

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

Я опишу более сложное, но более общее решение. Если у нас есть некоторый набор переменных, который пошагово пересчитывается друг через друга с помощью линейной функции, то можно применить бинарное возведение в степень матрицы. Итак, в нашей задаче переменная была одна x. Новая переменная x' получалась по формуле A·x + B. Рассмотрим матрицу z = [[A, B], [0, 1]] и вектор v = [x, 1]. Умножим z на v слева. Легко видеть, что получится вектор v' = [x', 1]. Таким образом, чтобы сделать n итераций, мы просто должны n раз умножить слева матрицу z на вектор v. В силу свойства ассоциативности операции умножения матриц перемножение мы можем сделать бинарно.

В качестве упражнения можете попробовать выписать самостоятельно матрицу для чисел Фиббоначи и научиться их быстро считать. Под спойлером матрица и вектор.

Матрица и вектор для чисел Фиббоначи
Решение на C++

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

678E - Очередной турнир ситхов

Задачу предложил и подготовил Алексей Дергунов dalex.

Давайте решать задачу динамикой. zmask, i — наибольшая вероятность выиграть Ивану, если джедаи из маски mask уже хоть раз сражались, а в живых остался только i-й джедай. Для подсчёта динамики переберём следующего джедая (ему придётся сражаться против i-го джедая): .

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

Сложность по времени: O(2nn2).

Сложность по памяти: O(2nn).

678F - Лена и запросы

Задачу предложил AmirMohammad Dehghan PrinceOfPersia.

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

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

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

Сложность: .

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Edvard 2016-06-17 00:08:58 71
en6 English Edvard 2016-06-17 00:06:45 2252
en5 English Edvard 2016-06-16 01:55:47 3667
en4 English Edvard 2016-06-16 01:45:55 1547
en3 English Edvard 2016-06-16 01:38:08 841
en2 English Edvard 2016-06-16 01:35:20 941
en1 English Edvard 2016-06-16 01:19:27 632 Initial revision for English translation
ru9 Russian Edvard 2016-06-16 00:45:21 76 Мелкая правка: ' summary="C++ solution">\n~~~~~\' -> ' summary="Решение на C++">\n~~~~~\'
ru8 Russian Edvard 2016-06-16 00:40:51 307
ru7 Russian Edvard 2016-06-15 00:49:41 3519 Мелкая правка: 'тьего типа отсортиру' -> 'тьего типа, отсортиру'
ru6 Russian Edvard 2016-06-14 23:38:12 51 Мелкая правка: 'ть: $O(log max(a, b))$.\n\n##' -> 'ть: $O(log(max(a, b)))$.\n\n##'
ru5 Russian Edvard 2016-06-14 23:37:44 62 Мелкая правка: 'ность: $O(1)$.\n\n###' -> 'ность: $O(log max(a, b))$.\n\n###'
ru4 Russian Edvard 2016-06-14 23:36:58 1541
ru3 Russian Edvard 2016-06-14 23:20:12 2276 Мелкая правка: '[1, 1]]$, v=[0, 1]$.' -
ru2 Russian Edvard 2016-06-14 01:38:58 832 Мелкая правка: 'т равен: $\lfloor p\frac na \' -> 'т равен: $p\lfloor \frac na \'
ru1 Russian Edvard 2016-06-14 01:21:42 1580 Первая редакция (опубликовано)