Comments 36
Поясните пожалуйста по 1 задаче, что понимается под максимальным по размеру? что нужно найти?
1 максимальное по количеству отрезков ( найти подмножество непересекающихся отрезков с наибольшим числом элементов )
или
2 максимальное по суммарной длине ( найти подмножество непересекающихся отрезков с наибольшей суммарной длиной )
1 максимальное по количеству отрезков ( найти подмножество непересекающихся отрезков с наибольшим числом элементов )
или
2 максимальное по суммарной длине ( найти подмножество непересекающихся отрезков с наибольшей суммарной длиной )
> У каждого отрезка i есть левый конец L[i] и правый конец R[i]. Отсортируем отрезки в порядке возрастания R[i]. В таком порядке будем перебирать отрезки. Очередной отрезок будем добавлять в ответ, если его левая граница больше максимума правых границ уже добавленных отрезков.
А с чем сравнивать L, если у нас в ответах пока что пусто?
Какой первый отрезок туда попадет? А если у нас самый «левый» отрезок самый длинный, то мы получим неверное подмножество?
А с чем сравнивать L, если у нас в ответах пока что пусто?
Какой первый отрезок туда попадет? А если у нас самый «левый» отрезок самый длинный, то мы получим неверное подмножество?
UFO just landed and posted this here
UFO just landed and posted this here
Может быть, она и решается проще, но не так: ответ совсем не всегда представляет собой цикл.
UFO just landed and posted this here
[0,3], [2,5], [4,7], [6,9], [8,1], M=10.
Массив next будет выглядеть как
[0,3] -> [4,7]
[2,5] -> [6,9]
[4,7] -> [8,1]
[6,9] -> [0,3]
[8,1] -> [2,5]
Решением будут любые два несоседних отрезка. Но в графе они циклом не будут.
Цикл наибольшего веса надо бы искать в графе, где каждый отрезок ссылается на два — ближайший после своего правого края (вес такого ребра равен 1) и ближайший после своего левого края (вес равен 0). При этом надо как-то записать, что цикл обходит окружность ровно один раз.
Массив next будет выглядеть как
[0,3] -> [4,7]
[2,5] -> [6,9]
[4,7] -> [8,1]
[6,9] -> [0,3]
[8,1] -> [2,5]
Решением будут любые два несоседних отрезка. Но в графе они циклом не будут.
Цикл наибольшего веса надо бы искать в графе, где каждый отрезок ссылается на два — ближайший после своего правого края (вес такого ребра равен 1) и ближайший после своего левого края (вес равен 0). При этом надо как-то записать, что цикл обходит окружность ровно один раз.
UFO just landed and posted this here
Похоже, что да. Более того, в цикле они будут идти подряд.
Отсюда, кстати, получается решение за O(n+sort):
Строим три массива:
next — как в статье
mask — маска проверенных циклов
loop — массив для хранения текущего цикла.
Пока есть отрезок K, для которого mask[K]==false:
— строим цикл: loop[0]=K, loop[1]=next[K],… Для отрезков X, попавших в цикл, устанавливаем mask[X]=true.
— методом двух указателей находим в цикле самый длинный фрагмент, в котором последний отрезок ещё не пересекается с первым (и путь между ними занял меньше одного оборота).
Самый длинный из найденных фрагментов и будет решением.
Не уверен, что оно работает. Найдётся ли контрпример?
Строим три массива:
next — как в статье
mask — маска проверенных циклов
loop — массив для хранения текущего цикла.
Пока есть отрезок K, для которого mask[K]==false:
— строим цикл: loop[0]=K, loop[1]=next[K],… Для отрезков X, попавших в цикл, устанавливаем mask[X]=true.
— методом двух указателей находим в цикле самый длинный фрагмент, в котором последний отрезок ещё не пересекается с первым (и путь между ними занял меньше одного оборота).
Самый длинный из найденных фрагментов и будет решением.
Не уверен, что оно работает. Найдётся ли контрпример?
Массив loop, кстати, не нужен. Достаточно идти двумя указателями по циклу, определённому массивом next, и помечать пройденные элементы для поиска следующего цикла.
Не работает. Граф не обязательно состоит из циклов :(
UFO just landed and posted this here
Например, если в массиве идут отрезки [1,2], [3,5], [4,6],… то на [4,6] никто не ссылается.
Другое дело, что всегда можно найти подмножество максимальной мощности, не содержащее отрезков без предков — например, в данном примере [4,6] можно заменить на [3,5]. Продолжая по индукции, получаем, что участки, не принадлежащие циклам, можно вообще не рассматривать.
Другое дело, что всегда можно найти подмножество максимальной мощности, не содержащее отрезков без предков — например, в данном примере [4,6] можно заменить на [3,5]. Продолжая по индукции, получаем, что участки, не принадлежащие циклам, можно вообще не рассматривать.
Получается, что от каждого отрезка идет какая-то цепочка, которая потом упирается в цикл. В итоге алгоритм может деградировать до O(N^2), но работать будет
UFO just landed and posted this here
В итоге алгоритм может деградировать до O(N^2),
Не может. Будем идти по цепочке и помечать её кодом 2, пока не уткнёмся в отрезок с ненулевым кодом. Если у этого отрезка код 2 — мы нашли цикл, перекрашиваем цепочку в код 1, и начинаем обработку цикла с найденного отрезка. Если уткнулись в код 1 — значит, цикл уже обработан раньше. Перекрашиваем цепочку в код 1 и ничего больше не делаем.
Мы не можем (во-всяком случае, я не уверен, что можем) останавливаться, пока левый указатель не дойдет до элемента цикла. А правый указатель может пройти путь порядка N уже с первым значением левого указателя, которое еще не в цикле.
То есть даже так: уверены ли Вы (и можете ли доказать), что ответ — обязательно часть цикла? Иными словами, что нет такой цепочки, которая дает (вместе со следующим за ней циклом) лучший ответ?
Пусть у нас есть отрезок X=[A,B], который не является next ни для какого отрезка. Рассмотрим последний (при сортировке по правому краю) отрезок Y=[C,D], для которого D < A. Пусть next[Y]=Z=[E,F]. Тогда E > D, F <= B, F >= A, и нет ни одного отрезка, правый край которого лежит между D и F.
Допустим, что некоторое допустимое подмножество содержит отрезок X. Утверждается, что его можно заменить на Z без появления пересечений отрезков подмножества.
Разность отрезков Z-X является либо пустым множеством — и тогда Z лежит внутри X, и новых пересечений точно не возникнет, либо является полуинтервалом [E,A). Если какой-то отрезок имеет общую точку с этим полуинтервалом, но не пересекается с отрезком X, то его правый край должен принадлежать этому полуинтервалу. Но из приведённых выше условий следует, что таких отрезков в исходном множестве нет.
Таким образом, для любого максимального подмножества, содержащего отрезок, не являющийся next, мы можем построить подмножество той же мощности, которое этого отрезка не содержит. Значит, все отрезки, являющиеся началами цепочек, мы можем исключить из исходного множества.
Продолжая этот процесс, мы придём к ситуации, когда каждый отрезок будет next для какого-то другого. А это значит, что граф распадается на циклы. И ещё кое-что, но с этим надо разбираться подробнее.
Допустим, что некоторое допустимое подмножество содержит отрезок X. Утверждается, что его можно заменить на Z без появления пересечений отрезков подмножества.
Разность отрезков Z-X является либо пустым множеством — и тогда Z лежит внутри X, и новых пересечений точно не возникнет, либо является полуинтервалом [E,A). Если какой-то отрезок имеет общую точку с этим полуинтервалом, но не пересекается с отрезком X, то его правый край должен принадлежать этому полуинтервалу. Но из приведённых выше условий следует, что таких отрезков в исходном множестве нет.
Таким образом, для любого максимального подмножества, содержащего отрезок, не являющийся next, мы можем построить подмножество той же мощности, которое этого отрезка не содержит. Значит, все отрезки, являющиеся началами цепочек, мы можем исключить из исходного множества.
Продолжая этот процесс, мы придём к ситуации, когда каждый отрезок будет next для какого-то другого. А это значит, что граф распадается на циклы. И ещё кое-что, но с этим надо разбираться подробнее.
А теперь это «кое-что»:
Действительно, при сортировке в случае равных правых концов будем располагать отрезки по возрастанию длины, чтобы более короткий встретился раньше. Тогда:
Если в множестве оставшихся отрезков есть только циклы, то:
— ни один отрезок не является подмножеством другого (иначе при поиске next более короткий всегда побеждал бы более длинного)
— следовательно, концы отрезков идут в том же порядке, что и их начала, и все начала различны (как и все концы)
— следовательно, next возвращает первый отрезок, который начинается после конца нашего
— следовательно, начала и концы на окружности чередуются (если начало одного отрезка совпало с концом другого, то мы сдвинем конец чуть вправо, чтобы точку пересечения превратить в отрезок)
— следовательно, структура множества оставшихся отрезков полностью регулярна — внутри каждого отрезка начинается и заканчивается одно и то же число других отрезков, и это число одинаково для всех отрезков множества
— следовательно, нам достаточно найти любой цикл в массиве next, и начать цепочку с любого отрезка этого цикла. Она гарантированно будет иметь максимальную длину :)
Действительно, при сортировке в случае равных правых концов будем располагать отрезки по возрастанию длины, чтобы более короткий встретился раньше. Тогда:
Если в множестве оставшихся отрезков есть только циклы, то:
— ни один отрезок не является подмножеством другого (иначе при поиске next более короткий всегда побеждал бы более длинного)
— следовательно, концы отрезков идут в том же порядке, что и их начала, и все начала различны (как и все концы)
— следовательно, next возвращает первый отрезок, который начинается после конца нашего
— следовательно, начала и концы на окружности чередуются (если начало одного отрезка совпало с концом другого, то мы сдвинем конец чуть вправо, чтобы точку пересечения превратить в отрезок)
— следовательно, структура множества оставшихся отрезков полностью регулярна — внутри каждого отрезка начинается и заканчивается одно и то же число других отрезков, и это число одинаково для всех отрезков множества
— следовательно, нам достаточно найти любой цикл в массиве next, и начать цепочку с любого отрезка этого цикла. Она гарантированно будет иметь максимальную длину :)
Доказал себе сам, Вы правы, цепочки можно отбросить и сложность получится O(N). Но для уверенности я бы сортировал сначала по правой границе, потом по длине (в случае равных правых границ).
UFO just landed and posted this here
UFO just landed and posted this here
1) В вашем случае массив next надо строить сразу на окружности, до перевода на удвоенный отрезок, иначе цикла не будет.
2) [0,1], [2,3],… [100,101], [102,101]. В таком случае первые 51 отрезок связаны последовательно один за другим, а из последнего — переход к нему самому.
2) [0,1], [2,3],… [100,101], [102,101]. В таком случае первые 51 отрезок связаны последовательно один за другим, а из последнего — переход к нему самому.
А нельзя вторую задачу решать так:
режем окружность в любом месте и «дорисовываем» справа от правого края точки отрезков, которые оказались разрезанными, слева «огрызки» стираем
режем окружность в любом месте и «дорисовываем» справа от правого края точки отрезков, которые оказались разрезанными, слева «огрызки» стираем
Обе задачи также можно решить через поиск максимального полного графа. Вершинами графа являются отрезки. Если отрезки не пересекаются, то соответствующие вершины связаны.
Решить то можно, только время получится экспоненциальное, так как «поиск максимального полного графа» — NP-трудная задача.
К первой задаче из статьи свелась задача о клике графа специфического вида. Огромное спасибо за статью!
Sign up to leave a comment.
Задачи по алгоритмам