O (N * LogN) алгоритм для следующей задачи

Question

Существует следующая проблема:

Самый престижный спортивный клуб в одном городе насчитывает ровно N членов.Каждый из его членов сильный и красивый.Точнее, i -й член этого клуба (нумерация членов к моменту их вступления в клуб) имеет силу S _i и красоту B _я .Поскольку это очень престижный клуб, его члены очень богатые и, следовательно, неординарные люди, поэтому они часто крайне ненавидят друг друга.Строго говоря, i -й член клуба г-н Х ненавидит j -ый член клуба г-н Y, если S _i ≤S _j и B _i ≥ B _j или если S _i ≥ S _j и B _i ≤ B _j (если оба свойства г-на Х больше, чем соответствующие свойства г-на Y, он даже не замечает его, с другой стороны, если оба его свойства меньше, он очень уважает г-на Y).

Чтобы отпраздновать новый 2003 год, администрация клуба планирует организовать вечеринку.Однако они боятся, что, если два человека, которые ненавидят друг друга, будут одновременно присутствовать на вечеринке, после одного или двух напитков они начнут драку.Поэтому нельзя приглашать двух людей, которые ненавидят друг друга.С другой стороны, чтобы сохранить престиж клуба на соответствующем уровне, администрация хочет пригласить как можно больше людей.

Будучи единственным из администрации, кто не боится прикасаться к компьютеру, вынаписать программу, которая бы выяснила, кого пригласить на вечеринку.

Ввод

* Первая строкаВходной файл содержит целое число N - количество членов клуба.(2 ≤ N ≤ 100 000).Следующие N строк содержат по два числа - S _i и B _i соответственно (1 ≤ S _i , B _i ≤ 109). *

Выход

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

Примеры испытаний

Ввод

  4
  1 1
  1 2
  2 1
  2 2

Выходные данные

  2
  1 4

Я пытаюсь решить проблему, но сложность моего алгоритма составляет O (N ^ 2) и так как 2 <= N <= 100000 необходимо улучшить алгоритм.Я решал проблему, используя алгоритм динамического программирования с наибольшей возрастающей подпоследовательностью, который имеет сложность O (N ^ 2).У кого-нибудь есть идеи, как улучшить алгоритм? </p>

Answer 1

Вот ответ O(n log(n)) с достаточным количеством деталей.

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

Пробежаться по списку.На ходу поддерживайте сбалансированное древо людей, которые, возможно, находятся на пути к тому, чтобы стать следующим человеком в максимальной восходящей цепи.Каждый человек должен храниться с длиной текущей цепочки и указателем на связанный список остальных людей в цепочке.Дерево должно быть отсортировано по силе.

Точнее, когда вы видите нового человека, найдите следующего самого слабого человека в дереве (никто не в порядке) и создайте триплет (person, length of chain, pointer to chain).Вставьте человека в дерево.Если у следующего более сильного человека в дереве цепочка не длиннее текущего человека, удалите этого человека.Все эти операции: O(log(n)).

Когда вы закончите обработку всех людей, максимальная запись в дереве будет иметь человека в конце максимальной цепочки людей, длину цепочкии указатель на связанный список с остальными людьми в цепочке.Это ваш ответ, распечатайте его.

Чтобы показать вам ваши примерные данные, вот что вы начинаете:

4
1 1
1 2
2 1
2 2

Это означает:

{person: 1, beauty: 1, strength: 1}
{person: 2, beauty: 2, strength: 1}
{person: 3, beauty: 1, strength: 2}
{person: 4, beauty: 2, strength: 2}

Сортировка по возрастанию красоты, затем уменьшению силы (нет дубликатов), чтобы получить:

{person: 3, beauty: 1, strength: 2}
{person: 1, beauty: 1, strength: 1}
{person: 4, beauty: 2, strength: 2}
{person: 2, beauty: 2, strength: 1}

Чтобы упростить вещи, я просто представлю дерево отсортированным набором.Это не так, как это должно быть представлено в памяти.

После ввода человека 3:

{person: 3, strength: 2, length: 1, next_person: null}

Следующий человек 1 ударяет человека 3.

{person: 1, strength: 1, length: 1, next_person: null}

Затем человек 4идет после человека 1. (Я написал связанный список как вложенную структуру данных, в действительности это должен быть связанный список.)

{person: 1, strength: 1, length: 1, next_person: null}
{person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}}

Тогда человек 2 сталкивается с человеком 1.

{person: 2, strength: 1, length: 1, next_person: null}
{person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}}

Чтобы найти свой ответ, посмотрите на конец дерева, на человека 4, указывает на человека 1. И ваш ответ - длина 2, а затем (от лучших к худшим) человек 4, затем 1.

Answer 2

Я не думаю, что ваше O(n^2) решение даже правильное, не говоря уже об эффективности.Если у вас есть что-то вроде этого:

3
2 2
1 1
3 3

Ответ 3. Однако классический алгоритм LIS даст 2.Вы учли это?

Что вы можете сделать, это отсортировать по S _i и применить LIS за O(n log n) раз на B _i .Для этого вы можете использовать либо деревья сегментов, либо более простой алгоритм, включающий бинарный поиск.Дайте мне знать, если вам понадобится дополнительная помощь.

Общая сложность составляет O(n log n): сортировка может быть выполнена в это время, как и LIS.

Answer 3

Если вы думаете о графе с членами клуба как вершинами и «как» как ребрами (то есть если два члена не ненавидят друг друга, то между соответствующими вершинами есть грань), можно переформулироватьЗадача выглядит следующим образом:

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

Фактически, подмножество, в котором все вершины имеют взаимные ребра, называется Клика или полный подграф.

Чтобы найти максимальную клику, требуется экспоненциальное время, еслине может использовать другие функции графа (см. эту ссылку ).В этой статье предлагается алгоритм Броня – Кербоша .

Рисуя элементы в плоскости (S,B), можно увидеть, что «подобный» край соответствует линиям, выходящим из вершины внаправление между 12 и 3 часами и между 6 и 9 часами.Легко построить пример, где такие ребра пересекаются, поэтому, к сожалению, это не планарный граф.

И, к сожалению, отношение «лайк» не является транзитивным , т. Е. Если A лайкиB и B любит C это не означает, что A также нравится C (опять же, это легко увидеть в плоскости (S,B)).

Answer 4

Вот несколько аргументов, как работает решение btilly:

• на самом деле respect и ignore симметричны в смысле что если A уважает B, то B игнорирует A, поэтому достаточно смотреть только на одно из отношений, например respect.

• Как указано пропущенным, соотношение respect транзитивно означает, что если A уважает B и B уважает C затем А также уважает С (и все те, кого уважает В).

• рассмотрим следующий график: вершины представляют членов и направленный край от A до B означает, что A уважает B (или, что то же самое, B игнорирует A). После устранения дубликатов (которые можно считать членов вес, соответствующий их кратности), мы понимаем, что не может быть никаких циклов (если A уважает B, это не возможно, что B уважает А через других членов, в какой-то момент нужно было бы есть край, который идет в неправильном направлении), то есть у нас есть направленный ациклический граф .

• рассмотрим путь через граф: если член A находится на этом пути, все другие вершины на пути либо соблюдаются A (далее «вниз по течению») или игнорируется A (далее «вверх по течению»). Таким образом, любой путь через граф представляет группу членов, которые все любят друг друга.

• С другой стороны, если нет пути между А и В, они ненавидят друг друга (в противном случае, например, между их).

• , поэтому мы переформулировали проблему, чтобы найти самый длинный путь через направленный ациклический граф (где каждое ребро имеет весовой единицу), что можно сделать в линейное время, как только мы построили такой граф.

Проблема, которая остается, состоит в том, чтобы построить график быстрее, чем O (N ^ 2) то есть без необходимости проходить все возможные пары вершин.

Вот пример btilly в графической форме (где стрелки означают respect):

• при достижении вершины A нам нужно только добавить «ближайших» соседей в некотором смысле, то есть не таких, как D, которые мы можем достичь через других как B и C.

• это где сортировка по возрастанию по одной координате и по убыванию в другой координате происходит от: после того, как мы добавили ребро из A к B, мы не добавили бы прямое ребро от A к D (потому что от A до D через B или C лучше), поэтому нам нужно только смотреть на вершины, которые находятся справа и ниже B (те, которые не может иметь преимущество с B)

Answer 5

Два человека с одинаковой силой и красотой ненавидят друг друга, и границы силы и красоты довольно тесны ...