Разбор задач Codeforces Round #306 (Div. 2)

Revision ru5, by ADJA, 2020-04-06 17:38:41

550A - Two Substrings

Задачу можно решать разными способами. Авторское решение такое: проверим две возможности — когда подстрока "AB" идет первее "BA" и наоборот. Проверять можно следующим образом: найти самое первое вхождение "AB" в исходной строке и рассмотреть подстроки длины 2 правее. Если среди них встретилась подстрока "BA" — ответ "YES". Аналогично проверяется второй случай. Если оба варианта не выполнены, ответ "NO". Сложность решения — O(n), где n — длина исходной строки.

550B - Preparing Olympiad

Задачу можно решить полным перебором всех подмножеств задач (всего 2n подмножеств). Для каждого из подмножеств проверим, удовлетворяет ли оно условиям задачи. Найдем сумму сложностей всех задач, входящих в подмножество, и убедимся, что она лежит в отрезке [l, r]. Найдем также разность между сложностями максимально сложной задачи и минимально сложной задача подмножества и убедимся, что она не менее x. Если подмножество задач удовлетворяет условиям — увеличиваем общий ответ на 1. Сложность решения задачи — O(2n·n).

550C - Divisibility by Eight

Задачу можно решить как минимум двумя способами.

Первый — через "школьный" признак делимости на 8 (число делится на 8 тогда и только тогда, когда число, образованное его последними тремя цифрами, делится на 8). Таким образом, достаточно проверять на делимость на 8 все однозначные, двухзначные и трехзначные числа, образуемые из исходного вычеркиванием цифр. Это можно сделать за O(n3) вложенными циклами по цифрам числа, где n — количество цифр числа.

Второй способ использует динамическое программирование. Будем считать величину dp[i][j], 1 ≤ i ≤ n, 0 ≤ j < 8 — величину, равную 1, если из префикса числа длиной i цифр можно вычеркнуть несколько цифр так, что остаток от деления полученного числа на 8 равен j, и 0 в противном случае. Формулы для пересчета: пусть i-я цифра числа есть ai, тогда dp[i][aimod8] = 1 (по смыслу — однозначные числа), dp[i][(j * 10 + ai)mod8] = max(dp[i][(j * 10 + ai)mod8], dp[i - 1][j]) (по смыслу — дописывание текущей цифры), dp[i][j] = max(dp[i][j], dp[i - 1][j]) (по смыслу — вычеркивание текущей цифры), где 0 ≤ j < 8. Ответ "YES" будет в том случае, когда для некоторого i выполнено dp[i][0] = 1. Для восстановления ответа также нужно завести дополнительный массив prev[i][j], который будет хранить индекс k такой, что при подсчете dp[i][j] пересчет был сделан из dp[i - 1][k]. Сложность такого решения — O(8·n).

Решение с динамическим программированием: 75664736

550D - Regular Bridge

Докажем, что если k — четное, то решения не существует. Пусть наш граф содержит мост(ы), k = 2s — четное число, степени всех вершин графа равны k. Дерево двусвязных (реберно двусвязных, далее слово "реберных" будет опущено для краткости) компонент исходного графа содержало компоненту, связанную с остальной частью графа только одним мостом (не несколькими мостами!) (на самом деле таких компонент как минимум две, но нам достаточно одной).

Рассмотрим эту компоненту. Удалим мост, связывающий ее с остальной частью графа. Тогда в ней будет всего одна вершина степени k - 1 = 2s - 1 и какое-то количество вершин степени k = 2s. Но тогда она будет содержать только одну вершину нечетной степени, что невозможно.

Построим такой граф для нечетных k. Пусть k = 2s - 1 — нечетное число. Рассмотрим отдельно случай k = 1, тогда, очевидно, подойдет дерево из двух вершин.

Для k ≥ 3 сперва найдем минимальное количество вершин искомого графа. Граф будет содержать как минимум один мост и как минимум две двусвязные компоненты, связанные с остальной частью графа одним мостом. Каждая из этих компонент содержит не менее k + 2 вершин (так как одна вершина связана k - 1 ребрами с другими, остальные имеют степень k = 2s - 1 — нечетное число, т.. количество этих вершин должно быть четным, в то же время оно не может быть меньше k = 2s - 1, то есть оно будет не меньше k + 1, что в сумме с одной вершиной степени k - 1 даст k + 2).

Следовательно, во всем графе будет не менее 2k + 4 вершин. Построим граф с таким количеством вершин.

Занумеруем вершины первой компоненты с 1 до k + 2, вторую компоненту построим аналогично первой. Пусть вершина 1 связана мостом с второй компонентой. Соединим ее k - 1 ребрами с вершинами 2, 3, ..., k. Вершины с номерами 2, 3, ..., k соединим между собой попарно и потом между каждой соседней парой, например 2 - 3, 4 - 5, ... (k - 1) - k, выкинем ребро. После соединим вершины 2, 3, ..., k с вершинами k + 1 и k + 2. Также соединим вершины k + 1 и k + 2 между собой. Тогда все вершины компоненты, кроме первой, будут иметь степень k. Точно так же создаем вторую компоненту и соединяем мостом с первой. Искомый граф построен и содержит O(k) вершин и O(k2) ребер.

Асимптотика решения — O(k2).

550E - Brackets in Implications

Пусть дано выражение , ai0 или 1 для всех i.

Покажем, что решения нет только в двух случаях.

1) an = 1.

Это следует из того, что , т. е. никакая расстановка скобок не сможет заменить самую правую 1 выражения на 0.

2) Выражение имеет вид или является его суффиксом, содержащим не менее 2 аргументов.

Это несложно доказать индукцией. Для суффикса невозможность расстановки скобок очевидна, для более длинных суффиксов любая свертка импликаций либо приведет к тому, что справа появится 1, либо уменьшит число единиц в выражении на 1.

Покажем, что в остальных случаях решение есть.

1) Для выражения 0 ничего делать не надо — ответ 0.

2) Выражение вида . Можно не расставлять никаких скобок, так как значение такого выражения без скобок равно 0.

3) Выражение вида , где вторая опущенная часть состоит только из единиц. Тогда .

Асимптотика: O(n).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru6 Russian ADJA 2020-04-07 23:35:53 1421
en7 English ADJA 2020-04-07 23:35:03 1421
ru5 Russian ADJA 2020-04-06 17:38:41 67
ru4 Russian ADJA 2020-04-06 17:36:31 26 Мелкая правка: '(dp\[i\]\[(j * 10) mod 8\], dp\[i-' -> '(dp\[i\]\[j\], dp\[i-'
en6 English ADJA 2020-04-06 17:35:23 197 Tiny change: '\]\[a_{i} mod 8] = ' -> '\]\[a_{i} \n mod 8] = '
en5 English ADJA 2020-04-06 16:30:08 2 Tiny change: 'ut some ditits from t' -> 'ut some digits from t'
ru3 Russian ADJA 2015-06-04 22:14:01 85
en4 English ADJA 2015-06-04 22:12:31 60
en3 English ADJA 2015-06-04 22:11:32 15 Tiny change: 'i\]\[a_{i}~mod,2015-06-04~8] = 1$ (j' -
en2 English ADJA 2015-06-04 22:10:45 11 Tiny change: 'Answer is ``\t{YES}'' if $dp\[i' -
ru2 Russian ADJA 2015-06-04 22:02:00 0 (опубликовано)
ru1 Russian ADJA 2015-06-04 22:01:24 6838 Первая редакция перевода на Русский
en1 English ADJA 2015-06-04 21:58:02 6093 Initial revision (saved to drafts)