@kalbasa

Здравствуйте. Дана перестановка целых чисел от 1 до n. Необходимо разбить ее на 2 монотонные подпоследовательности (не обязательно одного характера монотонности) или известить пользователя о том, что этого сделать нельзя. Сделать это нужно за O(n log n).

Написал функцию, которая извлекает из перестановки все монотонные последовательности максимальной длины за O(n log n). Однако для каждой такой последовательности необходимо проверить, является пара для нее монотонной. Получается O(n^2). Мне нужно быстрее.

Как к этой задаче лучше подступиться?

0

@Igor3D

А почему не просто отсортировать 2 половинки исходного мвссива?

0

@kalbasa

Плохо понимаю, причем здесь половинки и как эта сортировка поможет решить мою задачу. Поясните, пожалуйста.

Вот пара тесткейсов.
Input:
1 3 6 5 2 4
Output:
1 3 4
6 5 2

Input:
8 7 5 6 4 3 1 2
Output:
8 7 5 4 3 1
5 2

0

@Igor3D

Input:
1 3 6 5 2 4

Первая половинка 1, 3, 6
Вторая половинка 5, 2, 4

После сортировки (1, 3, 6) и (2, 4, 5). Чем не устраивает?

0

@Mysterious Light

Допустим, возможно такое разделение.
Есть два варианта: одного характера монотонности и разного.

1) Без о.о. две последовательности возрастают. В противном случае делается по аналогии.
Допустим, мы уже знаем, как распределять элементы. Первое число — в первую посл., второе — во вторую (например), и т.д. На каждом этапе мы добавляем одно число в одну последовательность, а потому последнее (наибольшее) число и уже добавленных будет возрастать ровно у одной последовательности.
Следствие: если встречается число A на позиции K, то распределив K чисел у одной из последовательностей наибольшее (последнее) будет A, очевидно.
Следствие: если встретится число B<A на позиции L>K, то в последовательность, куда попала A, уже не положишь B, поэтому требуется, чтобы во второй последовательности не было чисел, больше B.
Это я веду к тому, что после распределения K чисел, нужно минимизировать последнее число в одной из последовательностей. Эта задача — типичная на динамическое программирование.
Ещё раз: имеем две последовательности, одну из них специально делаем поменьше.
Если уже были распределены K-1 элемент, последние элементы двух последовательностей X и Y (X<Y), следующий элемент A, то
* A>Y => во вторую
* X<A<Y => в первую
* A<X => разбиение невозможно
Сложность O(n).

2) Одна возрастает, другая убывает.
Такие же рассуждения. Пусть мы уже разбросали K-1 элемент и следующий A. Наибольший (последний) элемент возрастающей посл. X, наименший элемент убывающей — Y.
* A<Y<X => в убывающую
* A<X<Y => в убывающую
* A>X>Y => в возрастающую
* A>Y>X => в возрастающую
* Y<A<X => не возможно
* X<A<Y => есть варианты
Последний случай предоставляет два варианта и мне видится это таким образом, что в этом месте нужно рассматривать оба параллельно (т.е. независимо).
Сложность алгоритма сходу оценить не могу. Если последний случай не возникнет — O(n). Если будет только последний случай, что невозможно, — O(2^n). Мне кажется (на интуитивном уровне), что количество выборов, то есть число последних случаев, зависит от n очень слабо, например, логорифмически.

Примечание: предполагается, что пустая убывающая последовательность имеет последний (минимальный) элемент +Infinity, а возрастающая — -Infinity. Просто для того, чтобы было понятно, когда появляется первый элемент.

После сортировки задача изменится. Порядок нужно сохранять, пока не известно, в какую последовательность каждый элемент входит.

P.S. в тесткейсах потерялась шестёрка.

1

@kalbasa

Во втором случае (возрастающая-убывающая) можно представить мысленно бинарное дерево, в каждом узле которого находится какое-то состояние двух стеков в случае X<A<Y. В каждом листе такого дерева находится либо состояние невозможности такого исхода, либо решение задачи. Таким образом сложность будет равна O(n * m), где m - максимальное кол-во листьев в дереве с n вершинами. Я знаю, что m всегда на единицу больше количества узлов со степенью 2. m явно меньше n, только вот как его оценить, интересно.

Сейчас попробую реализовать вашим способом.

P.S. Верно, ее нужно либо в начало второй последовательности, либо после 7 в первой.

0

@Igor3D

Ага, значит нельзя менять порядок следования - об этом автор не сказал.

Изложенные соображения понятны и логичны, но сами по себе сходимости они не гарантируют. "Алгоритм с развратом" (по существу разговор о 2 стеках сводится к нему) сработает, но найдутся случаи когда до логарифма будет далеко.

Это "динамическое" - интересная вещь. Если нетрудно дайте ссылки на теорию, дедушка почитает на досуге
Спасибо

0

@Mysterious Light

Развратом? Что это такое? Динамическое в том смысле, что по первым K элементам из n можно уже сказать, в какие последовательности какие идут. Это справедливо для двух возрастающих (убывающих) последовательностей. Идея-то простая, тут можно и без теории.

0

@Igor3D

Сказать можно, но это ничего не гарантирует. Допустим Вы видите только первые К элементов. Что бы Вы ни решили я всегда смогу приклеить такой "хвост" из последних элементов что Ваше решение не поведет к успеху. Тогда остается возвращаться и пытаться делать др (допустимый) ход - вот и возвратный алгоритм практически в чистом виде. (классический пример - задача о 8 ферзях)

0

@Mysterious Light

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

0

@kalbasa

Есть подозрение, что задачу для возрастающей и убывающей подпоследовательностей тоже можно сделать за O(n).

0

@Igor3D

Не вижу никакого обоснования этого утвержения. Да, здесь хорошая "отсечка" - но и только

Ваше "нет смогу" напоминает "казнить нельзя помиловать" - неясно что Вы хотели сказать Конечно это Ваше право, просто если я чего-то не понимаю - Вы можете прямо сказать, нет проблем.

0

@Mysterious Light

я попробовать доказать это в первом посте.

все, я в отпуске.

0

@Igor3D

Немного подумал - вырисовывается так

- находим максимальный элемент. Он делит массив на 2 части - левую и правую
- проверяем на упорядоченность обе части (не включая макс элемент), варианты
--- обе не упорядочены - решения нет
---обе упорядочены - проверяем сможем ли пристроить макс элемент. Если да - решено, иначе решения нет
---только одна упорядочена - здесь пока не знаю как дальше

0

@salam

поставьте условие более конкретно. нужно ли сохранять порядок элементов? может ли одна последовательность в исходном массиве быть внутри другой?

Добавлено через 1 минуту
т.е. можно ли в массиве 1 5 4 3 2 8 выделить первую как индексы {1, 5, 6}, а вторую {2, 3, 4} или они должны быть строго непрерывны?

Добавлено через 19 минут
в общем-то не суть. в обоих случаях ее можно решать за O(n).

0

@kalbasa

Порядок элементов нужно сохранять. Каждый элемент последовательности должен находиться ровно в одной из двух подпоследовательностей, на которые разбивается последовательность. Подпоследовательности не обязаны быть непрерывны по индексам.

Добавлено через 5 минут
Нужно решение за O(n).
Еще было бы неплохо найти доказательство или опровержение того факта, что, в случае выделения подпоследовательностей разного характера монотонности, достаточно найти наибольшую возрастающую подпоследовательность и проверить, составляют ли элементы, не входящие в нее, убывающую подпоследовательность (то есть O(n log n)).

0

@salam

пожалуйста, ставьте задачу всегда максимально конкретно.
при таком условии все довольно просто.
1. посчитаем динамикой за O(n*logn) наиб. возр. подпосл. и так же наиб. убыв. подпосл.
2. проверим, образуют ли остальные элементы убывающую или соответственно возрастающую посл. за O(n).
3. поймем:
а. является ли вся последовательность строго возр. или убыв. если да, то как-нибудь поделим ее пополам.
б. выполняются ли условие 2)
в. если нет, то "нет".
умеете считать пункт 1) за O(n*logn)?

0

@kalbasa

salam, Ваш вариант не сработает в случае наличия нескольких наибольших возрастающих/убывающих подпоследовательностей максимальной длины в исходной последовательности.

Рассмотрим на примере с маленьким n.
1 3 6 5 2 4

Алгоритм, который за O(n*log n) находит подпоследовательность максимальной длины, может найти любую такую подпоследовательность. Например, алгоритм нашел 1 3 6. Проверил 5 2 4 и выдал неверный ответ, т.к. нужно было взять 1 3 5 и 6 5 2. Точно так же он мог найти 6 5 4 и проверить 1 3 2 (в случае поиска сначала убывающей подпоследовательности) и выдать неверный результат.

Найти все возрастающие подпоследовательности максимальной длины можно за O(n*log n), но в этом случае нужно их всех перебрать и сделать для каждой O(n) проверку. А это уже не O(n*log n).

0

@Igor3D

А если так: нашли
1,3, (6), 5, 2, 4 (см рассуждения выше). Теперь 1, 3 - железно начало одной, и она возрастает. Поэтому если наименьший из правой будет перенесен в левую - это никак не повредит. Здесь такой 4. Др словами монотонный интервал останется монотонным при удалении из него любых элементов

(1, 3, 4) и (6, 5, 2) будьте внимательнее, трудно въехать

0

@kalbasa

Я уже писал по сути про тоже самое выше, только представил эту структуру решения в виде бинарного дерева состояний (разветвление происходит в узле, после которого появляется вопрос: "в какой из двух стеков возрастающий или убывающий добавлять следующий элемент?"). В этом случае непонятно, каким образом оценить m - количество листьев в таком дереве, для того чтобы посчитать асимптотику O(n * m). Такое решение мною реализовано и оно работает, но медленно на больших объемах данных.

Парадокс еще в том, что я реализовал для возрастающего-убывающего случая решение salam за O(n*log n) и пока не могу подобрать к нему антитесткейс (1 3 6 5 2 4 проходит на ура, т.к. выделяется 6 5 2).
Но ведь теоретически это решение не должно работать. Я написал почему выше.

Прошу прощения, постараюсь.

0