Обратите внимание на бонусы в некоторых задачах, и если вы умеете их решать, пожалуйста, напишите об этом в комментариях.
В задаче нужно было найти время ожидания для каждой очереди, просуммировав покупки по всем людям, и найти минимум.
В задаче нужно было найти максимально длинную гирлянду, которую можно составить из тех элементов, что у нас есть.
Во-первых, если какой-то цвет нужен, но его нет, то ответ — -1.
Иначе, ответ всегда существует, и является целым числом.
Просуммируем ответы по всем цветам по отдельности.
Пусть у нас есть a кусков бумаги некоторого цвета, а нужно — b. Тогда если a > = b, то к ответу можно прибавить b — повесить b кусков по одному метру, а если a < b, то к ответу можно прибавить a, использовав все куски, что есть в наличии. Итого, каждый цвет дает к ответу min(a, b).
В задаче требовалось расположить прямоугольный треугольник с катетами a, b на плоскости с вершинами в целых точках.
Если искомое расположение существует, то катет a всегда можно представить как вектор с целыми координатами A{x;y}, при чем a2 = x2 + y2. Переберем все возможные x (1 ≤ x ≤ a - 1), проверим, что y получается целым числом.
Вектор, перпендикулярный вектору {x;y} — { - y;x}. Возьмем вектор B{ - y / g;x / g}, где g = gcd(x, y). Треугольник можно уложить на плоскость лишь тогда, когда b делится нацело на |B|, где |B| — длина вектора B. Кандидат на ответ — треугольник (0;0)(x;y)( - y / g * b / |B|;x / g * b / |B|), нужно лишь не забыть проверку на то, что гипотенуза не параллельна осям координат.
Сложность решения — O(n).
В задаче требовалось промоделировать путь персонажа по графу.
Заметим, что если мы пришли в вершину i, то ребра во всех вершинах с номерами меньшими, чем i, повернуты в pi. Это дает нам возможность заметить рекуррентную формулу: пусть dpi — число шагов, необходимое, чтобы добраться из вершины 1 в вершину i, если все ребра изначально повернуты назад, в pi. тогда dpi + 1 = 2dpi + 2 - dppi. Ответом будет dpn + 1.
Сложность решения — O(n).
BONUS: Умеете ли вы решать задачу, если нет ограничения, что pi ≤ i? В такой формулировке задача становится более интересной, но я пока не знаю решения.
В задаче требовалось научиться прибавлять в оффлайне на отрезке числа сочетаний.
Будем смотреть, как изменяется задача при увеличении k от малых чисел к большим.
1) Все запросы имеют K = 0
Прибавляется каждый раз единица на отрезке.
Для решения задачи нужно прибавить на некотором массиве b[] в ячейку b[L] единицу, вычесть из b[R + 1] единицу, а после выполнения всех операций построить массив a как массив сумм на префиксах массива b.
2) Все запросы имеют K = 1
Прибавляется арифметическая прогрессия 1 2 3 4 ...
Для решения задачи нужно прибавить на некотором массиве c[] в ячейку c[L] единицу, вычесть из с[R + 1] единицу. После выполнения всех операций можно построить массив b как массив сумм на префиксах массива c. В таком массиве мы на каждом отрезке прибавили единицу. Если после этого для каждого запроса вычесть из b[R + 1] число C(R — L + 1, 1) = (R — L + 1), и построить массив а как массив префиксных сумм над массивом b, несложно увидеть, что массив а будет ответом.
3) Все запросы имеют произвольное k
Пускай у нас есть массив a[N][K].
обобщая предыдущие случаи, можно понять, что если поступает запрос L, R, K, нужно сделать операции
a[L][K + 1] += 1
a[R + 1][j] -= C(k + 1 — j + r — l, k + 1 — j) для всех 1 <= j <= K + 1
после чего построить необходимые суммы на префиксах для всех значений K спускаясь от больших K к меньшим.
Доказать, что нужно отнимать именно такое число сочетаний, проще всего, если посмотреть, как расположены эти числа в треугольнике Паскаля — легко увидеть, что это число является суммой всего ряда чисел перед ним.
Сложность решения — O((n + m)k).
407D - Наибольшая подматрица 3
В задаче требовалось найти наибольшую по площади подматрицу, состоящую из различных чисел.
Будем идти от медленных решений к более быстрым.
1) Решение за O(n6): Перебираем две противоположные вершины прямоугольника-ответа и проверяем, что все числа внутри различны.
2) Решение за O(n4): Фиксируем верхнюю и нижнюю границы прямоугольника-ответа (O(n2)).
Используем метод двух указателей при переборе левой и правой границы: пока в прямоугольнике нет одинаковых чисел, двигаем правую границу, пока есть — двигаем левую границу. Проверка при сдвиге границы — O(n), сдвигов — O(n).
3) Решение за O(n3logn): Введем функцию maxR(Left): наибольшее значение Right, такое, что при фиксированных Up и Down в прямоугольнике (Up, Down, Left, Right) нет одинаковых чисел. Заметим, что для всех i выполняется maxR(i) <= maxR(i + 1).
Как изменяются значения этой функции при сдвиге Down вниз? Каждое значение maxR(Left) может либо остаться таким же (если отрезок(Down, Down, Left, maxR(Left)) добавил лишь новые числа), либо уменьшиться.
Когда maxR(Left) уменьшается? Лишь тогда, когда одно из чисел с только что добавленного отрезка уже было в прямоугольнике.
Сдвигая Down вниз рассмотрим все числа в ряду Down. Для каждого числа в столбце j найдем индексы i и k такие, что i <= j, в столбце j есть вхождение числа a[Down][j] между строками Up и Down-1, i — максимально; k >= j, в столбце k есть вхождение числа a[Down][j] между строками Up и Down-1, k — минимально. Найдя такие индексы i и k (для этого удобно использовать set, для каждого цвета храня столбцы, где он встречался на данный момент между строками Up и Down), можно обновить maxR[i] = j — 1, maxR[j] = k — 1. Этого будет достаточно. Несложно заметить, что после описанных действий, если мы прокинем по всем i = m..1 maxR[i] = min(maxR[i], maxR[i + 1]), то мы вновь будем иметь корректные значения функции maxR(Left), и можно пересчитать ответ для данных Up и Down за O(n).
4) Решение за O(n3):
Предыдущее решение, несмотря на хорошую асимптотику, требует хранения большого количества set'ов. Это работает очень медленно даже на небольших тестах.
Избавимся от логарифма. Set используется лишь при поиске ближайших слева и справа чисел, равных данному, лежащих в строках с номерами от Up до Down. Заметим, что при сдвиге границы Up ближайший сверху элемент для данного a[i][j] отдаляется. Это наводит на мысль, что, двигая Up снизу вверх, можно заставить ближайший к a[i][j] элемент приближаться к столбцу j, и теперь, сдвигая Up вверх, мы можем, взяв число с верхнего ряда, быстро (за O(n)) определить все числа такие, что он будет для них ближайшим, и обновить для них ближайшее число.
Такое решение использует O(n2) памяти и O(n3) времени.
BONUS: Умеете ли вы решать эту задачу быстрее, чем за O(n3)? У меня не получилось, но никаких предпосылок того, что решения нет, я не нашел.
На контесте задачу, к сожалению, никто не решил, но в дорешивании первым оказался hza, с чем мы его и поздравляем.
В задаче требовалось найти наидлиннейший подотрезок, удовлетворяющий условию.
Сведем задачу к d = 1.
Если d = 0, то ответ — наидлиннейший подотрезок из равных чисел, этот случай обрабатываем отдельно.
Если d ≠ 0, то заметим, что если на некотором отрезке есть два числа ai, aj таких, что ai % d ≠ aj % d, то этот отрезок не может быть хорошим.
Разобьем исходную подпоследовательность на отрезки подряд идущих чисел, дающих равные остатки от деления на d, поделим каждое число на d, будем решать для каждого отрезка задачу отдельно, сказав, что d = 1.
Заметим, что отрезок [L, R] является хорошим тогда и только тогда, когда max(L, R) — min(L, R) — (R — L) <= k, и на отрезке с L по R нет одинаковых чисел. Объясняется это просто — если на отрезке нет повторяющихся чисел, то max(L, R) — min(L, R) — (R — L) — именно количество чисел, которые необходимо добавить, чтобы отрезок состоял из всех чисел с min(L, R) по max(L, R).
Для каждого L найдем такое maxR[L], что на отрезке с L по maxR[L] нет повторяющихся чисел, а maxR[L] — максимально. Это делается за O(nlogn) любым способом, например, проходом с map'ом.
Научимся для каждого фиксированного L поддерживать массив a[R] = max(L, R) — min(L, R) — (R — L). Если у нас есть такой массив, то для того, чтбы найти ответ, необходимо быстро найти такое наибольшее R, что a[R] <= k.
Нам потребуются два стека и дерево отрезков с операциями "Прибавить число на отрезке", "Найти минимальный элемент на отрезке" и "Найти самое правое число, такое, что оно не превышает k". Будем перебирать L справа налево (от n до 1). Как выглядит функция max(L, R) при фиксированном L? Ее значения представляют собой набор отрезков, на которых максимумом является первый элемент отрезка. (пример: для массива 6 4 8 0 7 9 функция max(1, R) будет иметь вид 6 6 8 8 8 9) Как изменяется функция при сдвиге L влево? Некоторые отрезки поглощаются новым элементом, если новый элемент больше значения на отрезке. Заметив, что все значения массива не убывают, будем хранить все такие отрезки в стеке, а при добавлении нового элемента a[L] вытаскивать отрезки из стека, пока значение на вершине меньше нового, и добавим на стек новый отрезок, который покроет L и все, что мы вытащили. Если каждую операцию со стеком сопровождать запросом "Прибавить число на отрезке", то мы уже можем получить массив a[R] = max(L, R).
Функция min(L, R) ведет себя абсолютно аналогично, и используя второй стек мы получаем a[R] = max(L, R) — min(L, R). Для того, чтобы получить член (R — L) достаточно просто каждый раз при сдвиге L влево отнимать единицу на отрезке [L, n].
Теперь запрос "Найти самое правое число, такое, что оно не превышает k". Сначала дерево отрезков разбивает отрезок запроса L..R на log(n) отрезков длиной степени двойки. Разобьем запрос на такие отрезки и выберем самый правый отрезок, минимум на котором <= k. Теперь будем спускаться по этому отрезку вниз в дереве отрезков — если в правом сыне min <= k, то в правого, иначе в левого. Так мы найдем искомый элемент.
Итак, для каждого фиксированного L делаем запрос на отрезке L..maxR(L) о самом правом числе, не превышающем k. Это один из кандидатов на ответ. Все. Раз мы делаем запрос на отрезке, на котором нет различных чисел, то любое число на этом отрезке неотрицательно, и min работает корректно.
Суммарное время работы — O(nlogn).
BONUS: Задача и сама по себе не из простых, но умеет ли кто-нибудь решать ее по методу "навороти побольше"? Интересно, как решать хотя бы на дереве.
BONUS2: Есть очень быстрое решение за O(n2). Давайте для отрезка [L; R] так же посмотрим на значение f(L, R) = max(L..R) — min(L..R) — (R — L) — K. f(L, R) можно считать для отрезка за O(1). Если f(L, R) <= 0, то отрезок — кандидат на ответ. Если f(L, R) > 0, то следующий отрезок, который стоит рассмотреть — [L; R + f(L, R)], потому что для всех r: R < r < R + f(L, R) отрезок [L; r] не будет k-d последовательностью, поскольку при добавлении одного числа в отрезок f(L, R) может либо возрасти на произвольное число, либо уменьшиться на единицу. Если так написать решение за квадрат, используя для начального R при фиксированном L значение L + curAns, то решение в среднем работает очень быстро, и получает ТЛ лишь на специальных тестов. Вполне возможно, что это решение можно оптимизациями довести до такого, что оно пройдет все тесты.
