Как найти наибольшее значение у такой функции?

Question

[BitNeBolt]

Ответ должен находиться на [lo; hi]

Как можно адаптировать под неё бинпоиск? Как проверять, слева или справа от mid находится наибольшее значение?

Comments

[Alexandroppolus]

В каком виде задана функция? Массив точек, с которых начинаются отрезки?

Answer 1

[Wataru]

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

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

Но если функция может принимать одинаковые значения на произвольном промежутке, то никаких логарифмических алгоритмов поиска максимума тут нет. Если обе промежуточные точки выдадут одно и то же значение, то никак не определить, в каком из трех промежутков лежит максимум.

Comments

[BitNeBolt]

Спасибо. У меня основная проблема как раз в том, что функция может принимать одинаковые значения на произвольном промежутке, буду искать другое решение.

[Wataru]

Давайте больше данных. Что у вас за задача, откуда функция взялась? Как она задана? Какие-то еще свойства? Может можно свести к чему-то быстрому.

А если просто вот такая кусочно константная функция, то представьте себе функцию, которая везде принимает значение 0, кроме одного отрезка длины 0.000001 где-то. Так вот, единственный способ найти этот максимум - это перебрать все точки с шагом 0.000001.

[BitNeBolt]

Wataru, эту задачу я дорешаю на полный балл, она не должна быть сильно сложной.

[Wataru]

BitNeBolt, Вы чего-то не до конца расказали. В текущей постановке задача имеет только наивное решение (очевидно, слишком медленное). Дайте, что ли, ссылку на задачу.

[BitNeBolt]

Wataru,

Раз

два"

.

Я выразил увеличение (защитный слой) по вертикали и горизонтали в зависимости от количества модулей в ряду или колонке, выбираю минимальное из двух. Количество модулей в строке - число, которое я перебираю бинпоиском, остальное выражаю. Оценка бинпоиска - само d. Потом меняю местами a, b (модули повернуты на 90 градусов) и все повторяю.

В случае, когда слева и справа значения равны я сразу выводил f(mid), но один из тестов ломался. Прописал, что нужно идти влево, решение почти прошло (88 баллов), скопировал метод, прописал что нужно вправо, выбрал лучший - результат не изменился.

Использовал бинпоиск, оценивал монотонность, запрашивая значения от x+1 и x-1, x - аргумент. Скорее всего, из-за неточной оценки программа и ломается, поэтому и решил спросить, что делать в таких случаях, когда возможен произвольный отрезок (на тестовом случае были ряды нулей, в другом случае может быть как минимум 3 равных значения).

[Wataru]

BitNeBolt, Чем больше защитный слой - тем меньше модулей влезает. Логично?

Значит функция количества впихуемых модулей f(d) - монотонна. Тут работает бинпоиск. Перебирайте им ширину защитного слоя d, а там уже внутри функции перебирайте 2 варината ориентации модулей, считайте сколько их в ширину и в высоту поместится, перемножайте. Вам надо найти максимальное d, при котором модулей влезает >= n.