Перестановка строк в массиве для устранения возрастающих подпоследовательностей

Следующая задача взята из Problems on Algorithms (Проблема 653):

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

Я не уверен, как это решить. Я думаю, что он может использовать своего рода повторение по принципу «разделяй и властвуй», но я не могу его найти.

У кого-нибудь есть идеи, как это решить?


algorithm dynamic-programming greedy divide-and-conquer
person GEP    schedule 30.08.2011    source источник
comment
длиннее, чем квадратный корень из n?   -  person andrew cooke    schedule 31.08.2011
comment
это задача 653 из книги "Задачи на алгоритмы"   -  person GEP    schedule 31.08.2011
comment
Вот ссылка на книгу в формате pdf:larc.unt.edu/ian /books/free/license.html   -  person GEP    schedule 31.08.2011
comment
я думаю, что его разделяй и властвуй, я подозреваю, что шаг слияния также включает в себя некоторую математику.   -  person GEP    schedule 31.08.2011

Ответы (1)


arrow_upward
5
arrow_downward

Вот мое решение.

1) Сортировать строки по первому элементу от наибольшего к наименьшему.

1 6    5 1
3 3 -\ 3 3
2 4 -/ 2 4
5 1    1 6

2) Разделите его на группы по ⌈√n⌉ и то, что осталось (не более ⌈√n⌉ групп)

5 1    5 1
3 3 -\ 3 3
2 4 -/ 
1 6    2 4
       1 6

3) Отсортируйте строки в каждой группе по второму элементу от большего к меньшему.

5 1    3 3
3 3    5 1
    -> 
2 4    1 6
1 6    2 4

Подтверждение правильности:

Возрастающие подпоследовательности в столбце 1 могут происходить только в одной группе (размер ‹= ⌈√n⌉),

Никакие 2 элемента возрастающих подпоследовательностей в столбце 2 не находятся в одной группе (не более ⌈√n⌉ групп)

person kilotaras    schedule 31.08.2011
comment
Ааа, так просто. Почему я этого не видел? Молодец. - person flight; 31.08.2011
comment
Около 5 минут. Я начал с размышлений о том, как решить задачу 1xn (один столбец). - person kilotaras; 31.08.2011
comment
Карандаш и бумага всегда помогут. - person kilotaras; 01.09.2011