codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

174.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 **Конец.**