164.md (14867B)
1 Source: https://codeforces.com/blog/entry/4303 2 3 [164A - Переменная, или Туда и обратно](/contest/164/problem/A "VK Cup 2012 Раунд 3") 4 5 **Кратко о решении — dfs, O(E).** 6 7 Пустим поиск в глубину из всех вершин, где переменная присваивается. Пометим все посещенные. 8 9 Пустим поиск в глубину по обратным ребрам из всех вершин, где переменная используется. Запретим ему проходить по вершинам, где переменная присваивается. Пометим все посещенные. 10 11 Вершины помеченные оба раза — это и есть те вершины, где состояние Васи кого-то волнует 12 13 [164B - Древние берляндские иероглифы](/contest/164/problem/B "VK Cup 2012 Раунд 3") 14 15 **Кратко о решении — метод двух указателей, O(N).** 16 17 Давайте для удобства предположим, что каждый символ в каждой строке встречается ровно один раз. 18 19 Тогда у нас есть перестановка *p**i* (позиция во второй строке *i*-го символа первой строки) 20 21 Решение за квадрат теперь такое: фиксируем начало подстроки и идем по ней вперед, при этом параллельно идем по подпоследовательности и следим, что и там, и там мы не прошли больше круга. 22 23 Решение за линию. 24 25 Будем теперь идти двумя указателями "начало подстроки" и "конец подстроки". Параллельно будем хранить очередь — текущая парная подпоследовательность. В очереди все *p**i* обязательно возрастают (этого не сложно достичь, т.к. можно прибавлять к *p**i* число *n* столько раз, сколько нужно. То что подпоследовательность не зациклилась проверяется так *queue*.*first* - *queue*.*last* < *n*. Значит, мы можем двигать конец подстроки вперед, пока это неравенство выполнено. Как только конец подстроки нельзя увеличить, увеличиваем начало. Заметим, что начало и конец подстроки также двигаются по кругу. 26 27 Альтернативное решение: 28 29 После того, как мы увидели перестановку *p*, можно воспользоваться методом двоичных подъемов и получить решение за O(NlogN), которое тоже получало Accepted. 30 31 [164C - Автоматное программирование](/contest/164/problem/C "VK Cup 2012 Раунд 3") 32 33 **Кратко о решении — MinCost flow, O(*N*2 K) или O(NlogN K).** 34 35 Самое главное было — увидеть граф, где вершины = задания, множества заданий, выполняемые автоматами = вершиннонепересекающиеся пути, а ребра можно было строить двумя способами (см. ниже). 36 37 Как сделать пути вершиннонепересекающимися? Раздвоить вершины. 38 39 Как добавить стоимость? Между двумя половинками вершины должна быть стоимость - *c**i*. 40 41 Первый способ, граф *G*1 : вершины A, B соединены ребром, если после задания A можно успеть выполнить задание B тем же автоматом. Тогда ребер *O*(*N*2). 42 43 Второй способ, граф *G*2 : все вершины упорядочены по *s**i* из вершины i ведут два ребра — в *i* + 1 (не берем *i* задание, пробуем взять следующее) и в вершину с минимальным *j* : *s**j* ≥ *s**i* + *t**i* (берем задание, переходим к минимальному из возможных следующих). Тогда ребер *O*(*N*). 44 45 Если вы пользовались первым способом и для поиска пути реализовали одну из вариаций алгоритма Форда-Беллмана, то вы могли получить TL. Собственно пока из-за того, что на java все медленно, TL не подняли, все Форд-Беллманы кроме одного особенного получали заслуженный TL. 46 47 Чтобы в *G*1 использовать Дейкстру с потенциалами, удобнее всего было заметить, что граф ацикличен и первый раз расстояния посчитать за O(E). 48 49 [164D - Минимальный диаметр](/contest/164/problem/D "VK Cup 2012 Раунд 3") 50 51 **Кратко о решении — бинпоиск по ответу, а внутри перебор за O(Fib(K)).** 52 53 Правильное решение состояло из четырех несложных идей: 54 55 1) Нужно из *N*2 ребер покрыть удаленными вершинами сколько то максимальных. Когда мы покрываем еще не покрытое ребро, у нас 2 варианта это сделать — выбрать 1 конец, выбрать второй конец. Эта идея сама по себе давала асимптотику *O*(2*K* * *N*). 56 57 2) Если сделать бинпоиск по ответу, то мы решаем более простую задачу: можно ли покрыть первые X ребер K вершинами? Т.е. правда ли, что размер контролирующего множества в таком графе не более K. 58 59 3) Если мы теперь внутри бинпоиска не берем какую-то вершину, то мы должны брать всех ее соседей в уменьшенном графе. Из этого можно сделать 2 вывода: во-первых, если есть вершина степени больше чем K, ее брать обязательно, во-вторых, не выгодно брать вершину степени 1. 60 61 4) Теперь решение работает за log * Fib(K) * K, где log — константа от бинпоиска, Fib(K) — K-е число Фибоначчи, K --- максимальная степень вершины в уменьшенном графе. 62 63 Почему Fib(K)? Теперь, когда мы делаем выбор, в одной ветке рекурсии K уменьшается на 1, а в другой хотя бы на 2... На лицо числа Фибоначчи. 64 65 P.S. Из похожих задач я знаю вот эту: [задача 2 с РОИ 2009-2010](http://neerc.ifmo.ru/school/archive/2009-2010/ru-olymp-roi-2010-statements.rar) 66 67 [164E - Поликарп и работы](/contest/164/problem/E "VK Cup 2012 Раунд 3") 68 69 **Кратко о решении — жадность + куча запросов на отрезке, асимптотика = O(NlogN).** 70 71 В этой задаче так и не получилось написать очевидное условие... 72 73 Расскажу некоторую легенду, чтобы дать понять, что задачка не искусственна, взята из "реальной жизни". 74 75 Все вы читали задачу C. Давайте чуть поменяем ее, скажем, что автомат у нас один, а работа должна начаться не раньше *l**i*, закончиться на позже *r**i*, а времени на нее уйдет *t**i*. Рассмотрим случай, когда *l**i* и *r**i* возрастают. 76 77 Попробуем придумать жадное решение: отсортируем все работы по *l**i* и будем пытаться "брать". Если можно взять, то выполнять работу будем в минимально возможный момент времени. 78 79 Это жадное решение не сложно завалить тестом (L=1, R=10, T=10), (L=2,R=11,T=5), (L=3,R=12,T=5). 80 81 Поэтому давайте жадность улучшим, попробуем, если добавить в конец не получается менять на кого-нибудь так, чтобы правый конец (последний использованный момент времени) максимально уменьшился. 82 83 Собственно задача E состояла в моделировании процесса. В том, чтобы запрограммировать эту жадность. 84 85 **Итак, решение:** 86 87 Для каждого отрезка определим величину *shift**i* = *s**i* — *l**i* (насколько можно отрезок подвинуть влево). 88 89 У нас уже есть *k* отрезков. Добавляем *k* + 1-й, не получается. Пробуем сделать замену. Перебираем все отрезки в порядке уменьшения индекса, смотрим, насколько уменьшится правый конец. 90 91 Это min(*t**i*, min по j=i+1..k (*shift**j*)). 92 93 Т.е. ни один из отрезков из 1..i уже не даст ответ лучше, чем min(max по j=i+1..k (*t**j*), min по j=i+1..k (*shift**j*)). 94 95 Зачем я выдумал этот максимум? Дело в том, что под минимумом теперь две функции, убывающая и возрастающая. Значит, максимум можно искать бинарным или троичным поиском. 96 97 Следующая идея заключается в том, что когда мы нашли оптимальную замену *besti*, то чтобы пересчитать все *shift**j*, достаточно сделать вычитание на отрезке besti+1..k 98 99 Полученное решение имеет асимптотику *O*(*Nlog*2*N*). Его можно улучшить до *O*(*NlogN*), заменив бинпоиск, а внутри него обращение к дереву поиска или дереву отрезков на один спуск по дереву. 100 101 **UPD:** 102 103 **По просьбам участников выкладываю "разбор" задач A,B,C второго дивизиона.** 104 105 Задачи второго дивизиона я не готовил, не читал, не решал. Но вроде бы, если почитать, они решаются так, как описано ниже. Так что разбор второго дивизиона не стоит воспринимать как авторский, это просто рассказ "как бы я решал эти задачки". Надеюсь, нигде не наврал. 106 107 [Задача A](https://codeforces.com/contest/174/problem/A) 108 109 X = (*a*1 + *a*2 + ... + *a**n* + b) / n. 110 111 Если *X* **меньше** максимального *a**i*, то нельзя сделать так, как просят. Иначе нужно вывести числа X — *a**i*. 112 113 [Задача B](https://codeforces.com/contest/174/problem/B) 114 115 **Решение #1, жадное:** 116 117 Если между двумя точками больше 11 или меньше 2 символов, то нельзя так разрезать. 118 119 Если перед первой точкой больше 8 символов, то нельзя так разрезать. 120 121 Если между после последней точки больше 3 символов, то нельзя так разрезать. 122 123 А иначе режем жадно :-) Если количество символов между двумя точками равно X, то разрез проводится в позиции min(8,X-1). 124 125 **Решение #2, DP:** 126 127 is[i] — можем ли мы разрезать префикс длины *i*. 128 129 Изначально is[0] = 1, остальные нули. 130 131 Теперь перебираем *i* в порядке возрастания и если is[i] = 1, пытаемся сделать переход в *i* + 1..*i* + 12. 132 133 [Задача C](https://codeforces.com/contest/174/problem/C) 134 135 Основная идея — жадность. 136 137 Если минимум на всем массиве равен нулю, то задача естественным образом распадается на подзадачи, а иначе нужно уменьшить весь отрезок на 1. 138 139 **Решение #1, ищем минимум** 140 141 Ищем минимум в массиве, вычитаем 1 из всего массива *min* раз, задача распадается на несколько (т.е. в каждый момент времени, задача = отрезок исходного массива). Минимум на отрезке нужно искать быстро, за O(logN), например. 142 143 **Решение #2, простое** 144 145 Будем идти слева направо и хранить, сколько у нас отрезков уже начато торчит налево, пусть это X. Если *X* < *a**i*, то нужно начать несколько новых отрезков, если же *X* > *a**i*, то несколько уже начатых нужно закончить в позиции *i* - 1. Начатые отрезки можно хранить в стэке. Хранить, конечно, нужно только позицию начала. Новый *X* будет равен *a**i*. 146 147 **Конец.**