Разбор [B`-B]
algo_easyВсем привет, это НЕофициальный разбор от @algo_easy. @algo_easy - это...
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[B'-B] 1: СОП
Алгоритмы: бинарный поиск
Решение: Давайте будем перебирать первый элемент, который выберет Артем в качестве последовательности. Тогда давайте бинпоиском перебирать максимальную правую границу в исходном массиве, до которой мы можем достать. Пусть мы в индексе i и наш элемент – x, а сейчас рассматриваем в качестве правой границы в бинпоиске – m. Тогда количество чисел не равных x на отрезке [i...m] должно быть <= d. Тогда возьмем длину отрезка и вычтем количество x на этом отрезке, так мы получим кол-во чисел не равных x. Это можно делать разными способами, но один из самых легких – посортировать изначально для каждого значения от 1 до m его позиции в массиве и добавить в отдельный массив(получится m массивов), тогда можно взять от массива, где лежит x, такую штуку: upper_bound(m) – lower_bound(i). Так мы возьмем количество x на этом отрезке. Эта же формула будет работать, когда мы пробуем обновить ответ, чтобы считать количество x на найденном отрезке.
[B'-B] 2: Лабиринт в Майнкрафте
Алгоритмы: реализация, DFS
Решение: Первый массив – a, второй – b. Тогда a – эйлеров обход графа, b – легче всего объяснить через неявное ДД на массиве, но если вы не знаете ДД, то это если бы мы представили массив в виде дерева, где если мы идем влево, то все элементы из нового поддерева – слева, а если вправо, то все элементы справа. Тогда давайте сделаем такой рекурсивный алгоритм: запустимся от 1 (она также должна быть первой в a) и границ поддерева в b (изначально 0, n - 1). В цикле будем рассматривать следующие элементы в a, если он левее нашего в b и лежит в нашем поддереве, то скажем, что это левый сын и тогда мы знаем всё его поддерево (это от нашей левой границы до нас). Если же справа и входит в наше поддерево – то это правый сын и сделаем аналогично если бы это был левый сын. Если же ни одно ни другое не выполняется, то выйдем из цикла. Тогда наш алгоритм правильно построит дерево, если оно правильно задано. Чтобы это проверить давайте посмотри на то, сколько не 0 в итоговом ответе. Если их ровно n – 1, то это победа, а иначе надо вывести -1. Есть и другие способы это проверить, но это самый простой по мнению автора.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[B'-B] 3: Никита собирает апельсины
Алгоритмы: ДП
Решение: Давайте рассмотрим каждое имеющееся t. Тогда, когда мы закончим обходить на этом t все апельсины, то мы будем либо в самой левой точке, либо в самой правой. Почему это так? Потому что если мы допустим закончим в m, то мы когда-то были допустим в L, затем перешли в R, а затем в m. Но тогда по пути из L в R (где L и R – самый левый и правый апельсины с текущим значением t соответственно) мы могли забрать и в m, но тогда зачем мы туда вернулись, если это последний рассмотренный шаг. Значит нам есть смысл рассматривать только l и r на каждом слое t. Теперь можно просто написать dp[i][0/1], где i – последний рассмотренный слой t, а 0/1 – в L или R мы закончили. Тогда например рассмотрим, если мы хотим с L предыдущего перейти на L нового. Надо от L предыдущего пройти в R нашего и потом в L нашего. 3 оставшихся перехода рассматриваются аналогично. Для упрощения можно добавить на уровни -INF и INF по нулю для удобства, так как мы должны начать и закончить в 0.
[B'-B] 4: Это конец
Алгоритмы: сортировки, жадные алгоритмы
Решение: Сначала определим для каждой строки два параметра, которые нас действительно волнуют, а именно суммарный баланс (количество открывающих скобок минус количество закрывающих) и минимальный баланс на префиксе.
Давайте разделим наши строки на две группы: те, у которых суммарный баланс неотрицательный, и те, у которых он отрицателен. Сначала в каком-то порядке будут идти строки с положительным и нулевым суммарным балансом, а потом с отрицательным.
Интуиция здесь такая: сначала баланс у нас растет, а потом уменьшается, "так выгодно", ниже будет доказательство.
Теперь рассмотрим, как же упорядочить обе группы последовательностей.
--> Отсортируем строки с неотрицательным балансом по невозрастанию минимального баланса на префиксе.
--> Отсортируем строки с отрицательным балансом по невозрастанию разности суммарного баланса и минимального баланса на префиксе.
Теперь сконкатенируем сначала строки с неотрицательным балансом, а потом с отрицательным. Проверим является ли полученная строка ПСП.
Доказательство: Сразу предупредим, запаситесь бумагой, ручкой и мозгами)
Стандартный факт, который обязательно надо знать: если массив A не отсортирован по неубыванию, то существует индекс i, что a[i]>a[i + 1]. Также, надо понимать, что мы можем менять такие (i, i + 1) и в какой-то момент массив станет отсортирован по неубыванию. Потому что кол-во инверсий уменьшается на 1.
И еще немного обозначений: min_pref[i] - минимальный баланс на префиксе строки i. bal[i] - баланс строки i.
1) Разберемся сначала, почему надо ставить сначала неотрицательный баланс, а потом отрицательный(строки имеется ввиду). Пусть это не так, мы предполагаем, что такая последовательность строк существует, что дает псп. Значит(из факта выше) у нас будет такой момент, что сначала идет строка с < O балансом, а потом за ней строка с >= O балансом, пусть это строки i и j соответственно. Я утверждаю, что можно поменять их местами. Пусть это не так. Как устроена последовательность? Сначала идут какие-то строки, потом i, потом j, и дальше идут какие-то строки. Тогда заметим, что псп может нарушиться только где-то у этих двух строк, очевидно, иначе бы изначально не было последовательности строк, дающее псп. Меняем i и j местами. Если теперь псп нарушается в i в новой последовательности, то значит в изначальной строке нарушилось бы псп, потому что j только прибавляет баланс(делает "лучше"). Если нарушается в j, то значит в изначальной строке тоже нарушилось бы псп, так как там i прибавляло <O баланса.
2) "Отсортируем строки с неотрицательным балансом по невозрастанию минимального баланса на префиксе". Докажем оптимальность этого. Пусть это не так. Опять, по факту выше, найдутся соседние строки i и j, что min_pref[i] < min_pref[j]. И пусть до них был какой-то баланс bal. Опять поменяем их местами. Если псп нарушается в i в новой последовательности, то значит что bal + bal[j] + min_pref[i] < O(ноль). Но bal[j] >= O. Значит bal + min_pref[i] < O -> в изначальной последовательности тоже нарушено псп в i. Если псп нарушается в j в новой последовательности, то bal + min_pref[j] < O. Но min_pref[i] < min_pref[j], значит bal + min_pref[i] тоже < нуля, а значит в изначальной последовательности было бы нарушено псп в i. Значит можем поменять i и j. Из факта выше, делаем так несколько раз, пока не получится убывание(невозрастание).
3) "Отсортируем строки с отрицательным балансом по невозрастанию разности суммарного баланса и минимального баланса на префиксе". Сделаем всё тоже самое. Пусть это не так, значит есть соседние в последовательности строки i и j, что bal[i] - min_pref[i] < bal[j] - min_pref[j] <--> bal[i] + min_pref[j] < bal[j] + min_pref[i]. Поменяем строки i и j местами. Если псп нарушается в i, то значит bal + bal[j] +min_pref[i] < O. bal[j] +min_pref[i] > bal[i] + min_pref[j](выше), значит bal + bal[i] + min_pref[j] < O. А значит, что в изначальной последовательности псп нарушалось в j. Аналогично, если псп нарушается в j в новой последовательности, то bal + min_pref[j] < O, то bal + min_pref[j] + bal[i] < O, так как bal[i] < O. Но значит, что в изначальной последовательности нарушалась псп в j.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников
[B'-B] 5: Операция над строкой
Алгоритмы: конструктив
Решение: Предположим, что любая подстрока дает нам новую строку, тогда всего будет n*(n+1)/2 + 1 строк (+ 1 потому что есть исходная). Тогда давайте вычтем из этого количества те подстроки, которые не дают новых. Давайте рассмотрим какую-то подстроку, в которой самый правый и самый левый элементы равны. Тогда она нам не даст новый строки, потому что мы могли убрать эти 2 элемента с краев, перевернуть ту подстроку и получить такую же, потому что эти элементы равны. Все остальные строки дают какую-то новую строку. Тогда для какого-то конкретного элемента, если его количество x будет x*(x+1)/2 «бесполезных» подстрок, потому что это количество вариантов выбрать левую и правую границы.
[B'-B] 6: Работа дворником
Алгоритмы: реализация, структуры данных
Решение: Довольно очевидно, что ответ – сумма количеств клеток, которые покроет действие – то, сколько уже покрытых клеток покроет действие. Тогда нам для каждого действия нужно находить за быстро эти 2 величины. Если действие уже было, просто пропустим его. Давайте выделим самую левую и правые клетки, которые затронет действие (это делается довольно легко, но надо рассмотреть аккуратно много случаев). Тогда первая величина будет равно просто разности x этих величин + 1. А второе будем считать так: во-первых заметим, что четная диагональ никогда никак не пересечется с какой-то нечетной. Во-вторых, что диагонали одного типа тоже никак друг на друга не влияют. Также несложными формулами можно найти от уже найденных 2 точек границы, в которой должны лежать коэффициенты других диагоналей. Тогда нам нужно уметь искать из всех таких диагоналей то, сколько попадают в найденный отрезок. Это можно сделать различными структурами данных, например ДО, ДФ, ДД, но автор считает, что самый легкий способ – ordered_set.
Есть более простое решение с бинпоиском, напишем / обновим пост завтра.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников