O (N * LogN) для следующей задачи

Возникает следующая проблема:

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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

{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.

Ответ 3

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

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

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

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

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

И, к сожалению, отношение "как" не transitive, т.е. если A нравится B и B нравится C это не означает, что A также нравится C (опять же, это легко увидеть в плоскости (S,B)).

Ответ 4

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

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

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

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

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

Ответ 5

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