codeforces-scrape

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

467.md (9453B)


      1 Source: https://codeforces.com/blog/entry/13870
      2 
      3 [467A - George and Accommodation](/contest/467/problem/A "Codeforces Round 267 (Div. 2)")
      4 
      5 В этой задаче нужно было просто посчитать количество пар, у которых *q**i* - *p**i* ≤ 2
      6 
      7 Асимптотика: *O*(*N*)
      8 
      9 [467B - Fedor and New Game](/contest/467/problem/B "Codeforces Round 267 (Div. 2)")
     10 
     11 В этой задаче нужно было уметь считать количество различных битов в двух числах. Как вариант, можно просто побежать по битам и посчитать количество различных. Ещё, как вариант, если исходные два числа *X* и *Y*, то количество различных битов равнялось бы количеству единиц в числе *X* *xor* *Y*, где *xor* — операция исключающего или.
     12 
     13 Асимптотика *O*(*M*·*N*)
     14 
     15 [467C - George and Job](/contest/467/problem/C "Codeforces Round 267 (Div. 2)")
     16 
     17 Решение этой задачи — динамическое программирование. Изначально нужно посчитать *psum**R*, где *psum**R* — сумма на префиксе массива *p* длиной *R*.
     18 
     19 Обозначим *dp**i*, *j* — максимальная прибыль которую может получить Юра, если мы уже выбрали *i* последовательностей и последний элемент в *i*-ой последовательности имеет индекс *j*.
     20 
     21 Очевидно, что если *i*·*m* > *j*, то *dp**i*, *j* = 0. Иначе *dp**i*, *j* = *max*(*dp**i*, *j* - 1, *dp**i* - 1, *j* - *m* + *psum**j* - *psum**j* - *m*) Ответом будет *dp**k*, *n*.
     22 
     23 Ещё нужно было не забыть использовать **long long** при вычислениях.
     24 
     25 Асимптотика: *O*(*N*·*K*)
     26 
     27 [467D - Fedor and Essay](/contest/467/problem/D "Codeforces Round 267 (Div. 2)")
     28 
     29 Первое, что нужно сделать, чтобы облегчить себе работу — перевести все строки в нижний регистр. Затем словам дать номера. Различным словам дать различные номера, а одинаковым — одинаковые.
     30 
     31 Затем, из всех строк нужно построить граф. Пусть каждое слово — просто вершина. А пара слов синонимов *X* и *Y* — ребро между вершинами, которые отвечают за данные слова. Ребра ориентированные. Также, для каждого слова мы должны хранить его длину и количество букв «*R*». Будем использовать номера, данные словам, для построения графа.
     32 
     33 После создания графа, у нас мог быть петли, кратные ребра, циклы. Поэтому нужно сжать все сильно связные компоненты в одну вершину. После чего задача состоит в том, чтобы посчитать *dp**ver* — пара, отвечающая за минимальное количество букв «*R*» и минимальную длину слова с минимальным количеством букв «*R*», которым можно заменить слово, за которое отвечает вершина *ver*.
     34 
     35 Пересчет очевиден — *dp**ver* = *max*(*dp**nextVev*, *dp**ver*), где *nextVer* — все вершины, в которые можно пойти из *ver*. Максимум из двух пар берется как у pair в C++.
     36 
     37 Затем нужно пройти по всем словам текста, получить номер вершины, который соответствует нужному слову. Пусть это *ver*. Тогда к ответу нужно прибавить *dp**ver*.
     38 
     39 Также, важно было не забыть использовать **long long** при вычислениях.
     40 
     41 Асимптотика: ![](https://espresso.codeforces.com/3ab373c0bd6b120909f530524a177b82629cebd8.png), где *w* — множество всех слов, которые есть в тексте и в словаре.
     42 
     43 [467E - Alex and Complicated Task](/contest/467/problem/E "Codeforces Round 267 (Div. 2)")
     44 
     45 Данная задача решалась жадно.
     46 
     47 Алгоритм решения такой:
     48 
     49 Набираем числа из массива *a* по очереди, пока в последовательности набранных чисел(далее *G*) не найдется нужная нам четверка. Напоминаю, что нужная четверка чисел имеет вид: [*c*1, *c*2, *c*3, *c*4] = [*x*, *y*, *x*, *y*]. Если набрали такую четверку чисел, то добавляем в ответ. Очищаем *G* и *v* (далее будет описано, что такое *v*).
     50 
     51 Очевидно, что этот алгоритм оптимален.
     52 
     53 Для удобности сжимаем числа в массиве *a*. То есть каждому числу присваиваем его порядковый номер в отсортированном списке всех уникальных чисел из массива *a*. Это делается, потому что в дальнейшем нам удобнее использовать числа порядка *O*(*N*). Теперь как быстро узнать, что в *G* найдется нужная нам четверка.
     54 
     55 Давайте для каждого уникального числа *X* хранить список его позиций в *G*. Назовем этот список *v**X*. Теперь просто можно обработать операцию добавления числа в *G*. Пусть добавляемое число — это *X*. Добавим число *X* в список *G*. Пусть *i* — позиция добавленного числа в список *G*.
     56 
     57 Теперь давайте добавим позицию *i* в список *v**X*.
     58 
     59 Можно заметить такой факт:
     60 
     61 Если размер списка *v**x* равен 4, то мы нашли нужную нам четверку.
     62 
     63 Можно заметить ещё один факт:
     64 
     65 Если до добавления мы не нашли нужную четверку чисел, а после добавления нашли, то последнее добавленное число является последним в четверке. То есть наше последнее добавленное число равно *c*4. Значит мы знаем позицию последнего числа из четверки. Давайте переберем позицию числа *c*2. Всего возможных позиций числа *c*2 не больше двух, так как всего позиций, на которых стоит число *c*2, не больше трех (смотреть предыдущий факт). Одна позиция уже занята числом *c*4. Итого остается максимум две позиции. Пусть мы проверяем, то что *c*2 имеет позицию *L*, а *c*4 имеет позицию *R*. Остается только проверить существование таких *c*1 и *c*3, что *c*1 = *c*3 и их позиции *P* и *Q* соответственно. *P* и *Q* должны удовлетворять следующим условиям: 1 < *P* < *L*, *L* < *Q* < *R*. Это очень легко проверить. Давайте заведем массив *T*. *T**i* =  максимальное *j*, что *G**i* = *G**j*. Поддерживать такой массив не составляет труда. Теперь проверка будет требовать только одного запроса: Максимум на отрезке [1, *L* - 1] в массиве *T*. Пусть результат запроса равен *Z*. Если он удовлетворяет условию *L* < *Z* < *R*, то четверка существует. Этим запросом мы нашли позицию числа *c*3 в списке *G*. По этим данным мы можем восстановить четверку.
     66 
     67 Чтобы найти максимум на отрезке за ![](https://espresso.codeforces.com/e864584c28b3beb52a5d9a7cbbcda3d80a9d4515.png), можно воспользоваться деревом отрезков или деревом Фенвика.
     68 
     69 Итоговая асимптотика: ![](https://espresso.codeforces.com/36f470bf769107e6d8d30da09625de1ca4144c7b.png).