Yury_Bandarchuk's blog

By Yury_Bandarchuk, 5 years ago, In Russian,

467A - George and Accommodation

В этой задаче нужно было просто посчитать количество пар, у которых qi - pi ≤ 2

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

467B - Fedor and New Game

В этой задаче нужно было уметь считать количество различных битов в двух числах. Как вариант, можно просто побежать по битам и посчитать количество различных. Ещё, как вариант, если исходные два числа X и Y, то количество различных битов равнялось бы количеству единиц в числе X xor Y, где xor — операция исключающего или.

Асимптотика O(M·N)

467C - George and Job

Решение этой задачи — динамическое программирование. Изначально нужно посчитать psumR, где psumR — сумма на префиксе массива p длиной R.

Обозначим dpi, j — максимальная прибыль которую может получить Юра, если мы уже выбрали i последовательностей и последний элемент в i-ой последовательности имеет индекс j.

Очевидно, что если i·m > j, то dpi, j = 0. Иначе dpi, j = max(dpi, j - 1, dpi - 1, j - m + psumj - psumj - m) Ответом будет dpk, n.

Ещё нужно было не забыть использовать long long при вычислениях.

Асимптотика: O(N·K)

467D - Fedor and Essay

Первое, что нужно сделать, чтобы облегчить себе работу — перевести все строки в нижний регистр. Затем словам дать номера. Различным словам дать различные номера, а одинаковым — одинаковые.

Затем, из всех строк нужно построить граф. Пусть каждое слово — просто вершина. А пара слов синонимов X и Y — ребро между вершинами, которые отвечают за данные слова. Ребра ориентированные. Также, для каждого слова мы должны хранить его длину и количество букв «R». Будем использовать номера, данные словам, для построения графа.

После создания графа, у нас мог быть петли, кратные ребра, циклы. Поэтому нужно сжать все сильно связные компоненты в одну вершину. После чего задача состоит в том, чтобы посчитать dpver — пара, отвечающая за минимальное количество букв «R» и минимальную длину слова с минимальным количеством букв «R», которым можно заменить слово, за которое отвечает вершина ver.

Пересчет очевиден — dpver = max(dpnextVev, dpver), где nextVer — все вершины, в которые можно пойти из ver. Максимум из двух пар берется как у pair в C++.

Затем нужно пройти по всем словам текста, получить номер вершины, который соответствует нужному слову. Пусть это ver. Тогда к ответу нужно прибавить dpver.

Также, важно было не забыть использовать long long при вычислениях.

Асимптотика: , где w — множество всех слов, которые есть в тексте и в словаре.

467E - Alex and Complicated Task

Данная задача решалась жадно.

Алгоритм решения такой:

Набираем числа из массива a по очереди, пока в последовательности набранных чисел(далее G) не найдется нужная нам четверка. Напоминаю, что нужная четверка чисел имеет вид: [c1, c2, c3, c4] = [x, y, x, y]. Если набрали такую четверку чисел, то добавляем в ответ. Очищаем G и v (далее будет описано, что такое v).

Очевидно, что этот алгоритм оптимален.

Для удобности сжимаем числа в массиве a. То есть каждому числу присваиваем его порядковый номер в отсортированном списке всех уникальных чисел из массива a. Это делается, потому что в дальнейшем нам удобнее использовать числа порядка O(N). Теперь как быстро узнать, что в G найдется нужная нам четверка.

Давайте для каждого уникального числа X хранить список его позиций в G. Назовем этот список vX. Теперь просто можно обработать операцию добавления числа в G. Пусть добавляемое число — это X. Добавим число X в список G. Пусть i — позиция добавленного числа в список G.

Теперь давайте добавим позицию i в список vX.

Можно заметить такой факт:

Если размер списка vx равен 4, то мы нашли нужную нам четверку.

Можно заметить ещё один факт:

Если до добавления мы не нашли нужную четверку чисел, а после добавления нашли, то последнее добавленное число является последним в четверке. То есть наше последнее добавленное число равно c4. Значит мы знаем позицию последнего числа из четверки. Давайте переберем позицию числа c2. Всего возможных позиций числа c2 не больше двух, так как всего позиций, на которых стоит число c2, не больше трех (смотреть предыдущий факт). Одна позиция уже занята числом c4. Итого остается максимум две позиции. Пусть мы проверяем, то что c2 имеет позицию L, а c4 имеет позицию R. Остается только проверить существование таких c1 и c3, что c1 = c3 и их позиции P и Q соответственно. P и Q должны удовлетворять следующим условиям: 1 < P < L, L < Q < R. Это очень легко проверить. Давайте заведем массив T. Ti =  максимальное j, что Gi = Gj. Поддерживать такой массив не составляет труда. Теперь проверка будет требовать только одного запроса: Максимум на отрезке [1, L - 1] в массиве T. Пусть результат запроса равен Z. Если он удовлетворяет условию L < Z < R, то четверка существует. Этим запросом мы нашли позицию числа c3 в списке G. По этим данным мы можем восстановить четверку.

Чтобы найти максимум на отрезке за , можно воспользоваться деревом отрезков или деревом Фенвика.

Итоговая асимптотика: .

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There's also a nice and short solution for E which uses only stack and map/dictionary, check my implementation — 7902705. The idea is taken from enesoncu's code

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since this was in Russian, I don't think proper discussion happened on this one, so can someone propose a better solution for D?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the solution to B more clearly ? It is difficult to understand why the TC is O(n*m).

»
6 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to question C in English clearly? I think google translate messed up the translation.