2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 16:07 


05/08/17
18
Дана последовательность $N$ прямоугольников различной ширины и высоты $(w_{i},h_{i})$. Прямоугольники расположены, начиная с точки $(0, 0)$, на оси $Оx$ вплотную друг за другом (вправо). Требуется найти $M$ - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.
Изображение

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 18:08 
Заслуженный участник


20/08/14
11066
Россия, Москва
А что в ней олимпиадного? Можно же втупую двойным циклом вычислить:$$M=\max\left(\min(h_{i\ldots j})\cdot\sum\limits_{k=i}^j w_k \right), \;\forall i,j: 1\le i \le j \le N$$Ну да, $O(N^2)$, ну и что, ведь не ограничивалось же.

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 18:18 
Заслуженный участник


04/05/09
4582
Почему $O(N^2)$?
Тело цикла можно легко сделать $O(1)$.

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 18:23 
Заслуженный участник


20/08/14
11066
Россия, Москва
venco в сообщении #1332954 писал(а):
Тело цикла можно легко сделать $O(1)$.
Только при дополнительном условии $i=1$, т.е. результат должен начинаться в крайней левой точке, тогда да, достаточно пройти правым краем по множеству. Но этого в условии не оговорено. При произвольном же положении левого края результата нужен второй цикл или хитрые эвристики расширения текущего прямоугольника, что совсем не факт что будут быстрее (и вообще найдут глобальный максимум).
Пример: $S_{1..3}=3, S_{5..8}=5, S_{7..9}=4$ - как при таких площадях найти $S_{5..8}$ одним циклом?

-- 16.08.2018, 18:35 --

Даже не так, можно попытаться (примерно за $O(N)$) тянуть за собой и левую границу пока площадь от сдвига правой границы растёт, но на это тоже будет контрпример типа трёх массивов высоких блоков с очень низкими между ними, причём средний максимальный по площади. Низкие блоки не дадут перескочить анализу в среднюю часть и увидеть там максимальную площадь.

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 18:43 
Заслуженный участник


04/05/09
4582
Да, это я пропустил.
Но $O(N\ln N)$, я думаю, можно получить.

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 18:54 
Заслуженный участник


20/08/14
11066
Россия, Москва
Нет, все контрпримеры плохи. Я пытался сказать что может быть ситуация, когда в матрице площадей NxN глобальный максимум со всех 4-х сторон окружён глубокими провалами с малой площадью и к нему не существует непрерывного пути неуменьшения площади от любой из 4-х границ. И соответственно одного цикла не хватит. Ну как-то так: высоты (10,10,1,15,10,15,1,15,5) при равной 1 ширине всех, тут решение выделено жирным.

venco в сообщении #1332962 писал(а):
Но $O(N\ln N)$, я думаю, можно получить.
Да, это вероятно можно, где-то в книгах сборников алгоритмов даже описывалось как именно (типа строить дерево/лес иерархии площадей за те самые $O(N\ln N)$, потом просто взять его (максимальный) корень).
Но ведь вопрос оптимальности в условии тоже не стоял. :mrgreen:

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 18:58 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Идем слева направа, храня последовательность (самый низкий прямоугольник слева, самый низкий из тех что правее чем он, ...). Каждый прямоугольник максимум один раз в нее добавляется и максимум один раз удаляется, поэтому проход за линейное время. В итоге для каждого прямоугольника запоминаем, где самый правый прямоугольник слева от него с высотой меньше чем у данного. Аналогично идем справа налево.
В итоге для каждого прямоугольника считаем его высоту, умноженную на расстояния до найденных прямоугольников - это площадь, которую можно получить, если упираться в его верхнюю границу.

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 20:26 
Заслуженный участник


20/08/14
11066
Россия, Москва
mihaild в сообщении #1332967 писал(а):
поэтому проход за линейное время.
Это при стоимости операций с последовательностью $O(1)$, а они точно будут таковы? Не уверен, мне больше верится в $O(\ln N)$, т.к. это сильно похоже на добавление/удаление произвольных элементов сортированного массива/дерева/кучи, для которых обе операции кажется не могут быть одновременно $O(1)$. Так что количество операций да, линейно $O(N)$, но вот сами операции не $O(1)$, а $O(\ln N)$, и в итоге те же $O(N \ln N)$.
Или я что-то недопонял про построение последовательности.

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 20:31 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Dmitriy40 в сообщении #1332979 писал(а):
Это при стоимости операций с последовательностью $O(1)$, а они точно будут таковы?
Точно. Тут даже последовательность не нужна, нужен стек. При проходе через очередной прямоугольник достаем из стека все прямоугольники выше текущего и добавляем текущий.

 Профиль  
                  
 
 Re: Задача на линейные структуры данных и алгоритмы
Сообщение16.08.2018, 21:20 
Заслуженный участник


20/08/14
11066
Россия, Москва
Ага, со стеком теперь понял. Здорово, да, получается $O(N)$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group