Разбор контеста

Контест:

https://codeforces.com/group/g92L0id9Yb/contest/234394

1) Ледяные скульптуры

Условие

В вершинах правильного $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)$.

2) Коровоконг объединяет нацию

Условие

Дан простой неориентированный граф с $n$ вершинами и $m$ ребрами. Некоторые вершины являются столицами - они не могут находиться в одной компоненте связности. Сколько можно максимально провести ребер, чтобы столицы все еще не оказались в одной компоненте связности? $1 \leq n \leq 1000, 1 \leq m \leq 100000$

Решение

Темы: DFS, Жадный алгоритм

Запустим DFS, найдем компоненты связности. Заметим, что каждую из компонент связности можно дополнить до полного графа в любом случае, прибавим это к ответу. Теперь остались компоненты связности, в некоторых из них есть столица, а в некоторых - нет.

Воспользуемся жадным алгоритмом - давайте возьмем компоненту связности со столицей, содержащую больше всего вершин. Давайте соединим ее (все ее вершины) со всеми компонентами связности (со всеми вершинами в них), в которых нет столицы. Утверждается, что больше ребер получить нельзя.

Почему? Оптимальный ответ - это граф, в котором каждая столица лежит в отдельной компоненте связности - полном графе, и других компонент нет. Давайте возьмем все вершины, которые не лежали в одной компоненте со столицами, а теперь лежат в одной компоненте со столицей, но не с максимальной из них. Тогда если вместо этого все их соединить с максимальной компонентой со столицей, то ребер станет больше.

Алгоритм работает за $O(n + m)$ - так как это просто DFS.

3) Теплица

Условие

Есть $n$ точек на прямой, разбитые на $m$ видов. Нужно поменять координату у как можно меньшего числа точек так, чтобы точки шли упорядоченно по виду - сначала точки вида $0$, потом точки вида $1$ и так далее. $1 \leq m \leq n \leq 5000$

Решение

Тема: НВП

Переформулируем задачу. Вместо того, чтобы минимизировать число точек, которые мы передвинем, давайте максимизировать число точек, которые останутся на месте - они должны уже лежать в правильном порядке. А именно, нам нужна максимальная по длине подпоследовательность, в которой номер вида не убывает. Она же Наибольшая Неубывающая Подпоследовательность.

$n < 5000$, так что зайдет даже алгоритм, работающий за $O(N^2)$ с классической одномерной динамикой.

Заметим, что сами координаты использовать не надо - важен лишь порядок видов точек.

4) GukiZ ненавидит коробки

Условие

На прямой разложены $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)$.

Давайте докажем жадный алгоритм. Возьмем оптимальный ответ. Кто-то точно дойдет до последней непустой кучи. Пусть во-первых он такой не один, а во-вторых, он взял еще что-то не из последней кучи. Тогда давайте перекинем эти коробки из предыдущих куч другому ученику, дошедшему до последней кучи, взамен отобрав у него коробки из последней кучи. Так одно из условий перестанет выполняться - либо у нашего ученика будут взяты только коробки в последней куче (и итерация алгоритма доказана), либо последнюю кучу единолично будет забирать только наш ученик, в этом случае переходим от последней кучи к предпоследней и делаем такое же рассуждение.

5) Прыжки по стенам

Условие

Есть две стены, каждая состоит из $n$ участков, расположенных вертикально. Ниндзя находится на нижнем участке левой стены. Он может за секунду сделать одно из действий:

  • подняться на участок выше
  • опуститься на участок ниже
  • прыгнуть на другую стену, при этом на ровно $k$ участков выше

Некоторые участки непроходимы. А также есть вода, которая каждую секунду затапливает один участок на обеих стенах. Надо вывести, может ли вообще ниндзя дойти до самого верха (до любой клетки, которая выше, чем самый верхний участок стены).

$1 \leq n, k \leq 10^5$

Решение

Тема: BFS

Аккуратно построим граф: вершинами являются проходимые участки стены, а ребрами соединены участки, между которыми по заданным правилам ниндзя может переместиться. Также удобно завести фиктивную вершину для самого верха.

Запустим на этом графе BFS из изначального места ниндзи. При этом осталось только учесть воду. Если мы добавляем в очередь вершину $x$ с высотой $h$, и при этом $dist[x] > h$, то давайте не будем ее добавлять, ведь мы дойдем за нее минимум за $dist[x]$ секунд, и за этой время она будет уже затоплена, ведь она будет затоплена как раз за $h$ секунд.

BFS работает за $O(n)$ (в графе $O(n)$ вершин и $O(n)$ ребер).

6) Наибольшая правильная скобочная подстрока

Условие

Дана скобочная последовательность длины до $10^6$. Нужно вывести длину наибольшей подстроки в ней, которая является правильной и скобочной. Также нужно вывести количество таких подстрок.

Решение

Тема: Стек, сканирующая прямая (немножко)

Давайте посчитаем для каждого префикса баланс, пройдясь один раз по массиву. В каком случае подстрока $[i, j]$ является правильной скобочной последовательностью? Ровно в том случае, если

  • $a_{i - 1} = a_j$
  • если $i-1 \leq k \leq j$, то $a_{i-1} \leq a_k$

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

Удобно хранить эту величину в стеке! А именно хранить там пары $(balance, first\_index)$. При этом $balance$ там будет идти по возрастанию с шагом $1$.

  • Если мы на $cur\_index$-ом шаге встретили открывающую скобку, то баланс увеличился на один и стал равен $balance$, положим в стек $(balance, cur\_index)$, так как прямо перед этим шагом баланс был меньше, поэтому в стеке точно ничего про этот баланс не лежит.
  • Если мы на $cur\_index$-ом шаге встретили закрывающую скобку, то баланс уменьшился на один и стал равен balance, при этом надо вынуть из стека последнюю пару $(balance + 1, first\_index)$, это значит, что отрезок $[first\_index, cur\_index]$ образует ПСП (и большего ПСП, который заканчивается в $i$ не существует). Таким образом мы переберем все максимальные ПСП-подотрезки.

7) Взломать за секунду

Условие

Глеб загадал число $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 строк код или они сделаны только для второй части и они рассматриваться здесь не будут.