В вершинах правильного $n$-угольника расставлены целые числа $t_1, t_2, \ldots, t_n$. Нужно выбрать среди них некоторые вершины, образующие тоже правильный многоугольник, сумма чисел в которых максимальна. $1 \leq n \leq 20000$.
Тема: Теория чисел
Достаточно просто перебрать все правильные многоугольники, вписанные в этот правильный $n$-угольник. Заметим, что $k$-угольник можно вписать в $n$-угольник тогда, и только тогда, когда $n$ делится на $k$. Просто переберем все делители числа $n$ за $O(\sqrt n)$.
Для выбранного числа вершин $k$ осталось проверить $\frac{n}{k}$ возможных многоугольников. Суммарно на одно $k$ мы обходим $n$ вершин, значит суммарная асимптотика будет $O(n \sqrt n)$.
Дан простой неориентированный граф с $n$ вершинами и $m$ ребрами. Некоторые вершины являются столицами - они не могут находиться в одной компоненте связности. Сколько можно максимально провести ребер, чтобы столицы все еще не оказались в одной компоненте связности? $1 \leq n \leq 1000, 1 \leq m \leq 100000$
Темы: DFS, Жадный алгоритм
Запустим DFS, найдем компоненты связности. Заметим, что каждую из компонент связности можно дополнить до полного графа в любом случае, прибавим это к ответу. Теперь остались компоненты связности, в некоторых из них есть столица, а в некоторых - нет.
Воспользуемся жадным алгоритмом - давайте возьмем компоненту связности со столицей, содержащую больше всего вершин. Давайте соединим ее (все ее вершины) со всеми компонентами связности (со всеми вершинами в них), в которых нет столицы. Утверждается, что больше ребер получить нельзя.
Почему? Оптимальный ответ - это граф, в котором каждая столица лежит в отдельной компоненте связности - полном графе, и других компонент нет. Давайте возьмем все вершины, которые не лежали в одной компоненте со столицами, а теперь лежат в одной компоненте со столицей, но не с максимальной из них. Тогда если вместо этого все их соединить с максимальной компонентой со столицей, то ребер станет больше.
Алгоритм работает за $O(n + m)$ - так как это просто DFS.
Есть $n$ точек на прямой, разбитые на $m$ видов. Нужно поменять координату у как можно меньшего числа точек так, чтобы точки шли упорядоченно по виду - сначала точки вида $0$, потом точки вида $1$ и так далее. $1 \leq m \leq n \leq 5000$
Тема: НВП
Переформулируем задачу. Вместо того, чтобы минимизировать число точек, которые мы передвинем, давайте максимизировать число точек, которые останутся на месте - они должны уже лежать в правильном порядке. А именно, нам нужна максимальная по длине подпоследовательность, в которой номер вида не убывает. Она же Наибольшая Неубывающая Подпоследовательность.
$n < 5000$, так что зайдет даже алгоритм, работающий за $O(N^2)$ с классической одномерной динамикой.
Заметим, что сами координаты использовать не надо - важен лишь порядок видов точек.
На прямой разложены $n$ куч коробок, размерами $a_1, a_2, \ldots, a_n$ коробок. Есть $m$ учеников, каждый из них изначально стоит левее всех куч коробок. Каждую секунду времени каждый учение может сделать одно из двух действий:
Влево ученики ходить не умеют. За какое минимальное число секунд $m$ учеников уберут все коробки? $1 \leq n, m \leq 10^5$
Темы: Бинарный поиск по ответу, Жадный алгоритм
Постановка задачи - минимизация времени - классическая для бинпоиска по ответу. Давайте по числу $t$ научимся понимать, можно ли за $t$ секунд убрать все коробки, после чего запустим бинпоиск с изначальными значениями $left = 0$ (за 0 секунд точно нельзя убрать все коробки), $right = n + \sum\limits_{i=1}^n a_i$ (за это время даже один студент разберет все коробки).
Как промоделировать ситуацию, когда у нас есть $t$ секунд? Давайте моделировать ее жадно и с конца. Давайте возьмем ученика, и заставим его пойти к самой последней непустой куче за время, равное ее индексу в массиве. Если он не успевает даже дойти до нее, то за $t$ секунд взять все коробки нельзя. Если он успевает дойти, то пусть берет как можно больше коробок оттуда. Если куча закончилась, то давайте он еще перед этим возьмет как можно больше из предпоследней кучи, и так далее. Заканчиваем его обрабатывать, когда у него заканчиваются $t$ секунд. Всех учеников прогоняем по этой стратегии. Если в конце все коробки оказываются пустыми - то за $t$ секунд можно убрать все коробки, иначе нет.
Моделирование работает за $n + m$ (если не исктаь каждый раз заново последнюю непустую коробку, а поддерживать ее индекс), а значит итоговое время работы равно $(n + m) \log(n + \sum\limits_{i=1}^n a_i)$.
Давайте докажем жадный алгоритм. Возьмем оптимальный ответ. Кто-то точно дойдет до последней непустой кучи. Пусть во-первых он такой не один, а во-вторых, он взял еще что-то не из последней кучи. Тогда давайте перекинем эти коробки из предыдущих куч другому ученику, дошедшему до последней кучи, взамен отобрав у него коробки из последней кучи. Так одно из условий перестанет выполняться - либо у нашего ученика будут взяты только коробки в последней куче (и итерация алгоритма доказана), либо последнюю кучу единолично будет забирать только наш ученик, в этом случае переходим от последней кучи к предпоследней и делаем такое же рассуждение.
Есть две стены, каждая состоит из $n$ участков, расположенных вертикально. Ниндзя находится на нижнем участке левой стены. Он может за секунду сделать одно из действий:
Некоторые участки непроходимы. А также есть вода, которая каждую секунду затапливает один участок на обеих стенах. Надо вывести, может ли вообще ниндзя дойти до самого верха (до любой клетки, которая выше, чем самый верхний участок стены).
$1 \leq n, k \leq 10^5$
Тема: BFS
Аккуратно построим граф: вершинами являются проходимые участки стены, а ребрами соединены участки, между которыми по заданным правилам ниндзя может переместиться. Также удобно завести фиктивную вершину для самого верха.
Запустим на этом графе BFS из изначального места ниндзи. При этом осталось только учесть воду. Если мы добавляем в очередь вершину $x$ с высотой $h$, и при этом $dist[x] > h$, то давайте не будем ее добавлять, ведь мы дойдем за нее минимум за $dist[x]$ секунд, и за этой время она будет уже затоплена, ведь она будет затоплена как раз за $h$ секунд.
BFS работает за $O(n)$ (в графе $O(n)$ вершин и $O(n)$ ребер).
Дана скобочная последовательность длины до $10^6$. Нужно вывести длину наибольшей подстроки в ней, которая является правильной и скобочной. Также нужно вывести количество таких подстрок.
Тема: Стек, сканирующая прямая (немножко)
Давайте посчитаем для каждого префикса баланс, пройдясь один раз по массиву. В каком случае подстрока $[i, j]$ является правильной скобочной последовательностью? Ровно в том случае, если
Давайте для каждого баланса хранить самый первый индекс, после которого ни разу не было баланса меньше.
Удобно хранить эту величину в стеке! А именно хранить там пары $(balance, first\_index)$. При этом $balance$ там будет идти по возрастанию с шагом $1$.
Глеб загадал число $A$ и дал вам $n$ запросов вида количество битов в $A \bigoplus B$ четно/нечетно, требуется найти $k$-е подходящее $A$
Тема: Математика/Динамика
Первым делом поймем, когда ответ -1:
1 случай) для каких-то $b_{i}, b_{j}$ количество бит по четности в $a \bigoplus b_{i}$ != количество бит по четности в $a \bigoplus b_{j}$, но при этом количество бит по четности в $b_{i}$ = количество бит по четности в $b_{j}$
2 случай) для каких-то $b_{i}, b_{j}$ количество бит по четности в $a \bigoplus b_{i}$ = количество бит по четности в $a \bigoplus b_{j}$, но при этом количество бит по четности в $b_{i}$ != количество бит по четности в $b_{j}$
Доказать это не сложно(к примеру можно пойти от противного предположить, что такая пара существует, но каждая единица дает +1/-1 к количеству бит в ксоре)
Данная задача позволяет очень много решений, рассмотрим сначала авторское.
Допустим $k = 1$, научимся решать тогда задачу.
Утверждается, что есть два возможных решения : 0, 1, проверить это очень просто : рассмотрим $0 \bigoplus b$, если четность нам подходит, тогда просто возьмем его иначе 1, так как она всегда меняет четность бит на 1.
Вернемся к полному решению, можно заметить, что если мы нашли $k$-ое число, то $k + 1$-ое это число после следующего перехода по четности количества бит, но найдем в каком случае меняется четность бит - она меняется только, если число - четное, таким образом у нас всегда есть три варианта ответа $2k - 1, 2k-2, -1$, тогда нам достаточно проверить первые два и если не одно не подходит, то честно вывести -1
Также есть альтернативные решения динамикой, но в них больше 300 строк код или они сделаны только для второй части и они рассматриваться здесь не будут.