Давайте считать, что $$$l_1$$$, $$$l_2$$$ и $$$l_3$$$ — это посортированные рабочие отрезки. Можем ли мы явно сказать что-то об одном из них?
$$$l_1$$$ должен равняться $$$1$$$.
Давайте считать, что $$$l_1$$$, $$$l_2$$$ и $$$l_3$$$ — это посортированные рабочие отрезки.
Если $$$l_1$$$ не равняется $$$1$$$, тогда мы можем уменьшить $$$l_1$$$ на $$$1$$$ и увеличить $$$l_3$$$ на $$$1$$$. Таким образом мы увеличим ответ.
Мы получили, что $$$l_1 = 1$$$, и нам осталось работать с $$$l_2$$$ и $$$l_3$$$.
Теперь задачу можно переписать как: $$$l_2 + l_3 = n - 4$$$, максимизируйте $$$min(l_2 - 1, l_3 - l_2)$$$.
И поскольку мы знаем, что $$$l_3 = n - 4 - l_2$$$, то даже:
максимизируйте $$$min(l_2 - 1, n - 4 - 2 \cdot l_2)$$$.
Если мы увеличим оба значение внутри минимума на один, то решения не изменятся, то есть можем решать:
максимизируйте $$$min(l_2, (n - 3) - 2 \cdot l_2)$$$.
Если мы выберем $$$l_2 = \left\lfloor\frac{n-3}{3}\right\rfloor$$$, тогда $$$min(l_2, (n - 3) - 2 \cdot l_2) = \left\lfloor\frac{n-3}{3}\right\rfloor$$$.
Если ответ больше, тогда $$$l_2 > \frac{n - 3}{3}$$$ and $$$(n - 3) - 2 \cdot l_2 > \frac{n - 3}{3}$$$, и это означает, что $$$2 \cdot (l_2) + ((n - 3) - 2 \cdot l_2) > n - 3$$$, но $$$2 \cdot (l_2) + ((n - 3) - 2 \cdot l_2) = n - 3$$$.
Единственное, что осталось сделать, это вычислить финальный ответ. И это $$$\left\lfloor\frac{n-3}{3}\right\rfloor - 1$$$. Или просто $$$\left\lfloor\frac{n}{3}\right\rfloor - 2$$$.
Выше был математический подход к решению.
Поскольку весьма очевидно, что $$$l_2$$$ — это примерно $$$\frac{n}{3}$$$, то вы могли проверить $$$l_2 = \frac{n}{3} \pm 5$$$ и выбрать лучший ответ.
Есть ли способ нарезать кусочки так, чтобы сохранить минимальный кусочек и удовлетворить потребности задачи?
Какое минимальное количество действий надо совершить для этого?
Есть ли решение лучше?
Начнем с простого решения.
Просто выберем минимальное значение из $$$a$$$ и предположим, что оно останется минимумом до конца. Поскольку массив посортирован, обозначим этот кусок как $$$a_1$$$.
То есть в конце все кусочки должны быть меньше либо равны $$$2 \cdot a_1 - 1$$$.
Мы можем ограничить снизу такое решение как $$$\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot a_1 - 1}\right\rceil}$$$.
Покажем, как достичь такой оценки. Для каждого кусочка, пока его размер строго больше чем $$$2 \cdot a_1 - 1$$$, давайте отрывать от него кусок размера $$$2 \cdot a_1 - 1$$$.
Единственная проблема в том, что мы можем получить кусок меньше чем $$$a_1$$$ в конце.
Но это означает, что перед последним отрыванием кусок имел размер в отрезке $$$[2 \cdot a_1, 3 \cdot a_1 - 2]$$$. Все размеры кусочков из этого отрезка могут быть легко разорваны на два кусочка правильных размеров одним действием.
Теперь остается вопрос: почему минимальным куском в конце мы хотим оставить именно кусок размера $$$a_1$$$.
На самом деле, могут быть и другие решения, но это решение дает лучший ответ в любом случае.
Как было описано выше, нижняя граница решения, где минимальный кусок имеет размер $$$x$$$ в конце — это $$$\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot x - 1}\right\rceil}$$$.
То есть, имея минимальный кусок меньшего размера, мы не можем получить результата лучше, потому что ограничение снизу на ответ будет таким же или большим для всех $$$x < a_1$$$.
Какой будет первая буква в ответе?
$$$a$$$, если $$$t$$$ не начинается с $$$a$$$, и $$$b$$$ иначе.
Задайтесь тем же вопросом как в Hint1 для каждой позиции.
Когда мы не можем просто взять минимальную неиспользованную букву?
Только если мы формируем цикл размера меньше чем $$$26$$$, создавая новый переход из одной буквы в другую.
Поддерживайте любую структуру, которая может это проверять.
Во-первых, процесс шифрования обратим. Если мы получили $$$t$$$ из $$$s$$$, используя $$$c$$$, то мы можем получить $$$s$$$ из $$$t$$$, используя тот же цикл $$$c$$$, но в обратном порядке. Таким образом, мы можем просто пытаться зашифровать $$$t$$$.
Лексикографическая минимальность сама по себе является жадной штукой. Поэтому мы можем сделать жадный алгоритм.
Давайте идти слева направо и генерировать результат буква за буквой. Мы можем выбирать лучший вариант на каждом шаге. Давайте опишем, какие варианты у нас есть
- Если буква на этом шагу уже встречалась раньше, то мы уже знаем, на что ее надо заменить.
- Иначе, мы бы хотели выбрать как можно меньшую букву. Но нам нужна какая-то структура, чтобы понимать, какие варианты приемлемы.
Давайте поддерживать круг, который уже сгенерирован(это некий граф). Для каждой буквы у нас будет одно входящее и одно выходящее ребро в конце. Давайте поддерживать их для каждой буквы: массивы $$$in[26]$$$, $$$out[26]$$$.
Когда мы хотим сгенерировать исходящее ребро на некотором шаге(определим буквы на этом шаге как $$$x$$$), мы должны выбрать минимальную букву, у которой еще нет входящего ребра. С одним исключением: если создание ребра создаст нам круг размера меньше $$$26$$$. Это бы означало, что мы не сможем получить полный круг в конце. Можно увидеть, что у нас есть не более одной такой буквы, поскольку такой буквой будет та, в которую мы упремся, стартуя по ребрам из $$$x$$$.
Чтобы проверить, что таковой маленький цикл не был сгенерирован, мы можем пройти по исходящему ребру $$$26$$$ раз, стартуя в $$$x$$$. Если мы закончим в $$$x$$$, или в какой-то момент у нас не было исходящего ребра, то добавленное ребро нам подходит.
Сложность $$$\mathcal{O}(26 \cdot 26 + n)$$$, то есть, $$$\mathcal{O}(n)$$$.
Как много сетов может быть среди $$$5$$$ карт?
Не более двух. Если есть два сета среди $$$5$$$ карт, то там будет "центральная" карта.
Переберите центральную карту.
Для любых двух карт всегда есть ровно одна карта, дополняющая их до сета.
[1] Это значит, что два любых сета пересекаются не более чем по одной карте.
Давайте покажем, что есть не более чем два сета в мета-сете. Обозначим $$$5$$$ карт как $$$c_1, c_2, c_3, c_4, c_5$$$. Предположим, что $$$(c_1, c_2, c_3)$$$ — это сет.
Все другие сеты содержат не более одной карты среди $$$(c_1, c_2, c_3)$$$ (потому что [1]), поэтому они обязаны включать $$$c_4$$$ и $$$c_5$$$. Получается, у нас есть не более одного другого сета, иначе бы они уже имели две одинаковые карты, что запрещено по [1].
Получается, каждый мета-сет выглядит как $$$2$$$ сета, пересекающиеся по одной карте. Давайте назовем ее центральной картой.
Теперь осталась простая комбинаторика. Для каждой карты мы хотим знать количество сетов, которые ее содержат. Если это количество $$$s$$$, то мы должны добавить $$$\frac{s(s-1)}{2}$$$ к ответу — это количество мета-сетов, где эта карта является центральной.
Чтобы получить количество сетов с каждой картой, проитерируемся по всем парам карт $$$(i, j)$$$, сгенерируем дополнение до сета, и добавим $$$1$$$ к этой карте в map/hashmap.
Сложность $$$\mathcal{O}(kn^2\log(n))$$$ или $$$\mathcal{O}(kn^2)$$$.
Как много возможных вариантов расстояния между $$$p_1$$$ и $$$p_2$$$.
Мы можем ограничить это значение $$$2 \cdot n$$$ вариантами.
Рассмотрим варианты $$$d_1[1] + d_2[i]$$$, $$$|d_1[1] - d_2[i]|$$$. Решите для каждого из них за линейное(почти) время.
Рассмотрим наибольшую дистанцию среди $$$d_1$$$ и $$$d_2$$$.
Можем ли мы ее сопоставить чему-то?
Можем явно.
Будем убирать такие, пока они превышают расстояние между $$$p_1$$$ и $$$p_2$$$.
Дальше задача очевидна.
Предположим, что рассматриваемые точка $$$p_1$$$ была левее чем рассматриваемая точка $$$p_2$$$.
Предположим, что мы знаем расстояние $$$l$$$ между рассматриваемыми точкам $$$p_1$$$ и $$$p_2$$$. Давайте покажем, как решить такую задачу за линейное время(почти линейное).
Пока у нас есть значение больше $$$l$$$, давайте будем брать наибольшее среди них(назовем его $$$x$$$). Предположим, что это значение из $$$d_1$$$.
Не трудно заметить, что дом с таким расстоянием должен быть правее рассматриваемой точки $$$p_2$$$ (потому что максимальное расстояние до точки $$$p_1$$$). Это означает, что мы можем сопоставить расстояние $$$x$$$ из $$$d_1$$$ расстоянию $$$x - l$$$ из $$$d_2$$$.
Когда не осталось значений больше $$$l$$$, все другие дома располагаются между рассматриваемыми точками. Мы можем сопоставить их просто сортировкой.
Это было решение за $$$\mathcal{O}(n log(n))$$$.
Давайте ограничим количество возможных расстояний $$$l$$$ — $$$\mathcal{O}(n)$$$ вариантами.
Если мы знаем, что какой-то дом имеет расстояния $$$x$$$ и $$$y$$$ до рассматриваемых точек, тогда у нас есть $$$2$$$ варианта для $$$l$$$: $$$x + y$$$ и $$$|x - y|$$$.
Давайте рассмотрим $$$2 \cdot n$$$ вариантов: $$$d_1[1] + d_2[i]$$$, $$$|d_1[1] - d_2[i]|$$$.
Сложность $$$\mathcal{O}(n^2 log(n))$$$.
Изобразите валюты на 2D плоскости.
Предположите, что вы можете выбросить любое количество денег в любой момент.
Как будет выглядеть область возможных точек?
Она будет выглядеть как выпуклый многоугольник в верхней правой четверти.
Поддерживайте его ребра.
Как меняется структура, когда приходит новый день?
Добавляется новый отрезок. Префикс старых отрезков сдвигается на вектор, а оставшийся суффикс на противоположный вектор.
Давайте изображать валюты на 2D плоскости. Если у нас есть $$$x$$$ камушков и $$$y$$$ бусинок, то изобразим это точкой $$$(x, y)$$$.
Предположим, что мы можем выбросить любое количество денег в любой момент. В таком случае, область возможных точек может быть описана выпуклым многоугольником в верхней правой четверти.
Изначально это прямоугольник $$$[(0, 0), (0, b), (a, b), (a, 0)]$$$.
В любой момент многоугольник может быть описан списком отрезков, начинающихся с точки $$$(0, y_0)$$$ и заканчивающихся в $$$(x_k, 0)$$$. В прямоугольнике, описанном выше, есть $$$2$$$ таких отрезка.
Давайте хранить эти отрезки посортированными по углу.
Когда приходит новый день, каждая точка может быть сдвинута на вектор $$$c\cdot(p_i, -q_i)\ \forall c \in [-1, 1]$$$, если у новой точки неотрицательные координаты.
Если мы забудем о том, что новые точки должны быть неотрицательными, как будут выглядеть новые сегменты?
Нам нужно лишь добавить отрезок $$$(2 \cdot p_i, -2 \cdot q_i)$$$, после чего сдвинуть префикс старых отрезков на $$$(-p_i, q_i)$$$ и оставшийся суффикс на $$$(p_i, -q_i)$$$.
Тогда единственное, что осталось сделать — это обрезать отрезки, чтобы поддерживать наш многоугольник неотрицательным.
Звучит классно, но звучит как $$$\mathcal{O}(n^2)$$$.
Надо ли нам поддерживать отрезки явно?
Нет!
Давайте просто поддерживать сет их длин и углов. Знания крайних точек $$$(0, y_0)$$$ и $$$(x_k, 0)$$$ достаточно.
Получается, нам надо:
- Вставить новый отрезок в сет. (Вам нужны только длины и углы).
- Сдвинуть крайние точки $$$(0, y_0)$$$ и $$$(x_k, 0)$$$ на $$$(-p_i, q_i)$$$ и $$$(p_i, -q_i)$$$ соответственно.
- Удалять и обрезать первые и последние отрезки, пока они все не уберутся в неотрицательной области.
Сложность $$$\mathcal{O}(nlog(n))$$$.
Есть другое простой подход за $$$\mathcal{O}(n^2log(n))$$$:
Поддерживаем область как многоугольник. На каждом шаге создадим две его копии, сдвинутые на соответствующие вектора. Построим выпуклую оболочку по ним. Обрежем выпуклую оболочку, чтобы она помещалась в неотрицательной области.
Это не зайдет. Упомянуто забавы ради.
