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

Revision ru5, by Edvard, 2016-02-19 22:49:52

628A - Tennis Tournament

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

В этой задаче можно было просто промоделировать процесс. А можно было заметить, что после каждого матча один игрок выбывает. Всего выбывших n - 1. Таким образом, всего нам нужно (n - 1) * (2b + 1) бутылок воды. Полотенец, конечно, нам нужно np штук.

С++ solution 1

С++ solution 2

Сложность: O(log2n), O(logn) или O(1) в зависимости от реализации.

628B - New Skateboard

Эта одна из задач предложенных пользователями Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

Ключевым для решения задачи является наблюдение, что число делится на 4 тогда и только тогда, когда его последние две цифры делятся на 4. Таким образом, для подсчёта ответа достаточно сначала посчитать количество подстрок длины один. Далее нужно рассмотреть пары соседних цифр таких, что они образуют двузначное число кратное 4-м и прибавить к ответу индекс правого из них.

C++ solution

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

628C - Bear and String Distance

Задачи предложена и подготовлена Камилем Дебовски Errichto.

В этой задаче можно действовать жадно. Будем идти по строке слева направо. Рассмотрим наибольшее расстояние d, которое мы можем получить на этой позиции (это либо расстояние вниз до буквы 'a', либо вверх до буквы 'z'). Пусть v = min(d, k). Поставим на текущей позиции букву на расстоянии v (вниз или вверх), а значение k уменьшим на v. Если после обработки всей строки, k оказалось больше нуля, то ответа не существует. В противном случае мы нашли ответ.

C++ solution 1

C++ solution 2

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

628D - Magic Numbers

Более простую версию задачи предложил Kareem Mohamed Kareem_Mohamed.

Обозначим ответ на задачу как f(a, b). Заметим, что f(a, b) = f(0, b) - f(0, a - 1) или что то же самое f(a, b) = f(0, b) - f(0, a) + g(a), где g(a) равно единице если a является волшебным число, иначе g(a) равно нулю. Далее будем решать задачу для отрезка [0, n].

Далее приводится стандартная техника, которую иногда называют 'динамикой по цифрам'. Её можно реализовать двумя способами, в первом перебирается длина префикса числа, который совпадёт с префиксом числа n. Следующий символ может быть произвольным меньшим соответствующей цифры в n, а далее любые цифры. Но я расскажу о втором подходе.

Пусть zijk равно количеству волшебных префиксов длины i, дающих остаток j при делении на m. При этом если k = 0, то префикс должен быть строго меньше префикса числа n, а если k = 1, то префикс должен быть равен префиксу числа n (больше он быть не может). Будем делать динамику вперёд. Переберём цифру , которую мы поставим на позиции i. При этом нам нужно проверить, что если позиция чётна то эта цифра должна быть равна d, а в противном случае она не может быть равна d. Также нужно проверить, что если k = 1, то эта цифра не может быть больше соответствующей цифры в числе n. Теперь поймём в какое состояние мы попадём после такого перехода. Конечно, i' = i + 1. Согласно схеме Горнера j' = (10j + p) mod m. Легко видеть, что . Для перехода нужно сделать zi'j'k' +  = zijk. Конечно, нужно не забыть делать все операции по модулю 109 + 7.

C++ solution

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

628E - Zbazi in Zeydabad

Задача предложена Ali Ahmadi Kuzey.

Давайте сначала сделаем предподсчёт zlij, zrij, zldij — наибольшее количество букв 'z' влево, вправо и влево-вниз от позиции (i, j). Это легко сделать за O(nm). Пусть мы зафиксировали некоторую клетку (i, j). Рассмотрим величину c = min(zlij, zldij). Это наибольший допустимый размер квадрата с верхним правым углом в (i, j). Теперь поймём сколько таких квадратов. Рассмотрим произвольную клетку (x, y) по диагонали вниз-влево на расстоянии не более c. Пара клеток (i, j) и (x, y) образует z-паттерн, если y + zrxy > j.

Отлично, теперь для решения задачи заведём структуру данных для каждой диагонали (она определяется формулой x + y), которая умеет прибавлять в точке и брать сумму на отрезке (лучше всего для этого подходит дерево Фенвика). Будем перебирать столбец j справа налево и обрабатывать события: некоторая клетка (x, y) такова, что y + zrxy - 1 = j. В этом случае нам нужно в дереве номер x + y сделать прибавление в точке y на единицу. Теперь будем перебирать клетку в текущем столбце (i, j). Тогда к ответу нужно прибавить величину суммы в дереве номер i + j на отрезке от j - c + 1 до j.

С++ solution

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

628F - Bear and Fair Set

Задача предложена и подготовлена Камилем Дебовски Errichto.

С++ solution

Сложность: O(2Cn), где в нашей задаче C = 5.

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru6 Russian Edvard 2016-02-19 23:07:43 1319
ru5 Russian Edvard 2016-02-19 22:49:52 37
en10 English Edvard 2016-02-19 20:29:32 29 Tiny change: '16-02-19].\n\nAt th' -> '16-02-19]. He also wrote the editorial.\n\nAt th'
en9 English Edvard 2016-02-19 20:28:14 1288
en8 English Edvard 2016-02-19 20:01:07 0 (published)
en7 English Edvard 2016-02-19 19:53:34 72
en6 English Edvard 2016-02-19 19:51:34 1255
en5 English Edvard 2016-02-19 18:39:13 1526
ru4 Russian Edvard 2016-02-19 18:31:29 11 Мелкая правка: ' точке $y$. Теперь б' -> ' точке $y$ на единицу. Теперь б'
en4 English Edvard 2016-02-19 18:12:12 9
en3 English Edvard 2016-02-19 17:55:04 1837
en2 English Edvard 2016-02-19 16:18:14 661
en1 English Edvard 2016-02-19 16:11:13 514 Initial revision for English translation
ru3 Russian Edvard 2016-02-19 16:03:48 160 Мелкая правка: 'сть: $O(2^C n)$, где' -
ru2 Russian Edvard 2016-02-19 15:36:22 1314 Мелкая правка: 'tebin.com/w1p4uf1X)\n\nСложн' -> 'tebin.com/uxu6s5WD)\n\nСложн'
ru1 Russian Edvard 2016-02-19 14:20:15 3638 Первая редакция (сохранено в черновиках)