Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от KADR
А нахождение этого расстояния не займет N*N времени? Из каждой точки до каждой точки?
Хотя конечно чуть меньше, но все же
Да нет, я же в следующем предложении написал, как в сразу для всех точек находить эти суммы расстояний за O(NlogN). И не надо здесь ничего сводить к алгоритмам на графах, оно без них прекрасно решается.
Ну, например, можно повернуть все на 45 градусов и растянуть (а точнее, сделать замену x' = x-y, y' = x+y), тогда метрика станет манхеттенской. Теперь, сумма расстояний раскладывается в 2 суммы: сумма расстояний по иксу и по игреку. Можно отдельно найти эти две величины для каждой точки, а затем сложить. Найдем, например, сумму расстояний по иксам. Для этого отсортируем все точки по их абсциссе и пройдем по этому массиву слева направо. При переходе к следующей точке мы легко можем посчитать, как изменится искомая сумма. Сложность решения O(NlogN).
Я кодил ее давно и декартово дерево написано ужасно криво, но кроме ввода никаких хаков не делал. Правда, работает оно 1.85 секунд. Кстати, выводил я не puts, а обычным printf.
Можно все ребра обычного (не сжатого) бора сложить в один большой хешмап. У меня так влезло.
В иллюстрации к алгоритму Мейна-Лоренца перепутаны l1 и l2.
Да, действительно, можно и в онлайне с двоичными прыжками. Я думал, может как-то при построении можно только для нужных нам подстрок запоминать состояния, чтобы в сумме за линию было.
Есть ли нормальный способ для поиска состояния суффиксного автомата, соответствующего подстроке строки, на котороый он был построен, заданной ее левым и правым индексами? Формально, есть суффиксный автомат, построенный на строке S. Поступают запросы вида "найти состояние в автомате, соответствующее подстроке S[l]...S[r]".
Вроде бы ясно, как это можно сделать в оффлайне за O((N + M)logN). Для этого достаточно предпосчитать двоичные прыжки по суффиксным ссылкам, отсортировать запросы по правому концу и для фиксированного правого конца за O(logN) находить следующее интересующее нас состояние.
Можно ли это делать в онлайне и быстрее? Даже если можно в оффлайне делать это быстрее и проще, тоже было бы интересно услышать.
В условии столько воды, что вообще не понятно, что действительно следует принимать во внимание, а что написано просто так.
Если это ограничение про 10% используется, то тем более эта задача не является примером. Ведь существуют решения, которые работают быстрее и которые не используют никаких дополнительных неестественных ограничений.
Насчет дерева отрезков. Я никогда не пробовал реализовывать двумерное дерево отрезков с подобными операциями, но в теории вершин должно быть O(NlogN). Решение полностью аналогично двумерному случаю. Только теперь у нас не сканирующая прямая, а плоскость. Когда встречаем начало или конец параллелепипеда, делаем обновление на прямоугольнике.
Эта задача уж точно не является классической задачей на применение формулы включений-исключений. Тем более, что без нее она делается за O(N log^2(N)) стандартными методами (при помощи двумерного дерева отрезков). Ну или можно за O(N^2 log N) при помощи одномерного. Да и не понятно, откуда берется 2^(N/10) в асимптотике. Почему там не чистое 2^N?
Кстати, вроде бы в этой статье есть еще опечатка в разделе о нахождении позиции первого вхождения. Там где написано "При клонировании вершины q в clone мы ставим: firstpos(clone) = firstpos(cur)". Видимо, должно быть "firstpos(clone) = firstpos(q)".
Ну можно за MN/32. Это оно?
На самом деле можно восстанавливать кратчайший путь и не храня его явно. Если мы уже нашли расстояния до всех вершин от стартовой, то в текущую вершину B мы могли прийти только из тех вершин A, для которых dist(A)+cost(A,B)=dist(B). Таким образом, можно перебрать всех потенциальных предков данной вершины в кратчайшем пути и пойти сразу в несколько, а не в один.
Почему он принимает только 2 значения? Он проходит по всему пути, который мы и хотим вывести.
Насчет всех цепочек - их-то можно вывести после небольшой модификации, но зачем это нужно? Количество путей может быть очень велико (растет экспоненциально от длины).
Да, за линейное время можно со стеком. А именно, посчитаем частичные суммы двух видов. Пусть L - минимальная длина интересующего нас отрезка. Тогда S1(i) = a(0) + ... + a(i), а S2(i) = a(0) + ... + a(i - L). Заметим, тогда, что для отрезка с концами в i и j (i >= j), среднее арифметическое значение будет равно X = (S1(i) - S2(j + L - 1)) / (i - j + 1). Сделаем замену t = j + L - 1, тогда получаем: X = (S1(i) - S2(t)) / (i - t + L). Нам требуется максимизировать X. Теперь у нас уже нет ограничения на минимальную длину отрезка, зато считаем мы уже не совсем среднее арифметическое значение.
Домножив обе части на знаменатель, имеем: S1(i) - X * (i + L) = S2(t) - X * t (*).
Слева и справа стоят уравнения прямых, где X - независимая переменная. Для фиксированного i нам требуется найти такое t, что точка пересечения соотв. прямых лежит как можно правее. Можно заметить, что оба угловых коэффициента отрицательные, причем у прямой с левой части он строго меньший, чем у прямой с правой части. Это значит, что если мы будем хранить нижнее огибающее множество прямых в левой части (lower envelope), то оптимальная точка пересечения будет достигаться при пересечении прямой S1(i) - X * (i + L) с одной из прямых, принадлежащих этому множеству. Поддерживая все прямые в стеке, можно за О(Н) вычислить эту точку пересечения для каждой из прямых. Достаточно знать, что задача нахождения нижнего огибающего множества прямых вида y = kx + l эквивалентна нахождению нижней цепи выпуклой оболочки точек вида (k, l).
Этот метод обобщается и для такой задачи: дан массив из N чисел, а также число L. Поступают запросы вида: "Дан отрезок чисел из этого массива, требуется в онлайне выдать подотрезок этого отрезка, длины не менее L, с максимальным средним арифметическим значением". Для обобщения алгоритма нужно сделать несколько наблюдений:
1. Как уже сказано выше, если зафиксировать правый конец отрезка и помнить нижнее огибающее множество всех прямых из правой части равенства (*), соответствующим числам, которые лежат левее правого конца, то для нахождения оптимального отрезка с этим правым концом, достаточно пересечь соотв. прямую из левой части равенства (*) с этим нижним огибающим множеством.
2. Аналогично для случая, когда зафиксирован левый конец отрезка и есть верхнее огибающее множество всех прямых из левой части равенства (*), соотв. числам справа от этого конца.
3. Если отрезок поделить на 2 части, для левой найти нижнее огибающее множество прямых из правой части (*), а для правых - верхнее огибающее множество прямых из левой части (*), а также предположить, что правый конец лежит в правой половине, а левый - в левой, то оптимальные концы можно найти, если пересечь эти 2 множества прямых. Пересекающиеся прямые и будут соответствовать концам оптимального отрезка. Можно показать, что точка пересечения всегда будет одна.
Можно пересекать такие множества за O(log^2(N)), делая 2 вложенных двоичных поиска: один по иксу, а второй по номеру соотв. отрезка или луча в каждом из множеств.
Вернемся к исходной задаче. Перед тем, как начинать отвечать на запросы, построим 2 дерева отрезков: в одном будут храниться прямые из левой части равенства (*), во втором - из правой. Оба они займут O(NlogN) памяти. Времени на построение уйдет столько же. Для каждой вершины из этих ДО найдем оптимальный отрезок, лежащий в них.
При ответе на запрос, мы поделим данный нам отрезок на O(logN) подотрезков, которым соответствуют вершины в деревьях отрезков. Для начала, найдем самый лучший подотрезок, целиком лежащий внутри одного из этих отрезков. Затем, можно пересечь все пары отрезков из разных деревьев описанным выше методом, и сравнить полученный ответ с уже найденным.
Последний этап занимает O(log^4(N)) времени. Но если вместо пересечения всех пар, зафиксировать один подотрезок, а затем последовательно идти от него вправо и сливать все огибающее множества в одно (можно неявно), то в сумме получится O(log^3(N)) времени.
Алгоритм вышел довольно сложный. Я давал практически такую же задачу на летние сборы в Петрозаводске 2011, так что если что-то непонятно - можно там в разборе глянуть.
Я на код почти не смотрел. Но, насколько знаю, эта задача решается максимальным паросочетанием.
Эта задача решается поиском в глубину. Ну точнее, динамикой с запоминанием, которая оформляется в виде одного поиска в глубину.
Вот отличный пост от Антона Лунева, который содержит неплохую подборку задач на ТЧ.
Да, точно, INF поставил маленьким 
Отправил в приват реализацию.
Интересно. Вроде бы такое решение пропускает все что можно дфсом, но тем не менее, на SPOJ получает TL, при том что мой Диниц там за 0.41 проходит (ТЛ 5 секунд).
Насчет Диница: нет, это не быстрее. Такой код выходит эквивалентным алгоритму Эдмондса-Карпа, только константа больше. Ведь на каждой итерации бфса поток пропускается только через один путь.
На всех нормальных онлайн джаджах при ошибке компиляции выдает лог компилятора. Нужно его только поискать.
Код не может падать при ошибке компиляции, т.к. он даже не запускается.
Обычно при компайл эрроре пишут еще и сообщение об ошибке. Полезно бывает его прочитать и разобраться, в чем дело.
Ну и не видя условия тяжело что-то сказать. Возможно, где-то в нем кроется какое-то дурацкое ограничение из-за которого код падает.
Только что заметил, что добавилась статья где описывается решение задачи поиска отрезка с максимальным средним значением за O(N * logW). На самом деле, если мы будем искать отрезок, у которого длина лежит в заданном диапазоне (иначе всегда выгодно отрезок длины 1 брать), то задачу за линейное время можно решать. Мало того, если длина просто ограничена снизу, то можно добиться еще более крутого результата и в онлайне для запроса "найти подотрезок заданного отрезка с максимальным средним значением" находить ответ за O(log^3(N)).
Да там просто от каждой вершины надо самую дальнюю найти и запомнить, как мы туда шли: сразу вниз или вверх до куда-то, а потом вниз. Делается двумя дфсами.
Ну а после этого можно либо двоичным подъемом на все запросы в онлайне отвечать, либо еще одним дфсом в оффлайне за линию.
Я возненавидел алгоритм Карацубы после того, как на втором раунде Facebook Hacker Cup первая задача отработала за 6:20 при таймлимите в 6 минут. Фурье тогда проходил на ура. Теперь по возможности пишу только Фурье.
MAXimal :: φορυμ » Сообщения от KADR