Задачка о дискретной функции

[LexiBender]

Помогите придумать алгоритм для этой задачки : http://acm.timus.ru/problem.aspx?space=1&num=1010 Есть какие - нибудь идеи?

[Aritaborian]

А у вас? И неплохо бы перенести условие задачи сюда вместо невнятной ссылки.

[LexiBender]

Дана дискретная функция. Она определена для целых аргументов из диапазона от 1 до N (2 ≤ N ≤ 100000). Функция может принимать значения от −231 до 231−1. Требуется найти такие две точки A и B на графике функции, для которых все точки между ними расположены ниже прямой AB. Среди всех допустимых пар нужно выдать такую, для которой модуль углового коэффициента прямой AB максимален.


Дублирую условие. У меня нет идей. Меня нужно подтолкнуть в правильном направлении..

[Urnwestek]

(Оффтоп)

Какая-ж то невнятная ссылка! Это же тимус! На нём поколения школьников и студентов олимпиадников по инфе росли (:

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

[sup]

Странное условие. Ну вот есть такая пара с коэффициентом K и абсциссами n,m. Рассмотрим пары $(n,n+1), (n+1,n+2) ... (m-1,m)$. Очевидно, что в одной из этих пар коэффициент еще больше (ну или они все равны между собой). Поскольку точки соседние, между ними нет других точек и условие "лежат ниже" тривиально верно.

[LexiBender]

sup в сообщении #807116 писал(а):

Странное условие. Ну вот есть такая пара с коэффициентом K и абсциссами n,m. Рассмотрим пары $(n,n+1), (n+1,n+2) ... (m-1,m)$. Очевидно, что в одной из этих пар коэффициент еще больше (ну или они все равны между собой). Поскольку точки соседние, между ними нет других точек и условие "лежат ниже" тривиально верно.

Мне кажется, этот тривиальный случай не надо рассматривать, я тоже об этом подумал сразу
ПС. Кажется, про выпуклую оболочку есть рациональное зерно) Правда, первый раз с этим термином сталкиваюсь, смотрел на википедии)

[Urnwestek]

LexiBender в сообщении #807119 писал(а):

Очевидно, что в одной из этих пар коэффициент еще больше

Я что-то туплю. Почему?
Кстати, условие «между» я не увидел, так что решал вроде как более общую задачу.

-- 28.12.2013, 12:09 --

Понял. Всё верно. LexiBender про выпуклую оболочку можете не читать (:

[LexiBender]

Почему? Неправильная мысль?

[Urnwestek]

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

-- 28.12.2013, 12:18 --

А если убрать условие «между» и потребовать, чтобы ВСЕ точки лежали под искомой прямой, задача слишком сложнее станет?

[LexiBender]

Urnwestek в сообщении #807124 писал(а):

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

-- 28.12.2013, 12:18 --

А если убрать условие «между» и потребовать, чтобы ВСЕ точки лежали под искомой прямой, задача слишком сложнее станет?

Наоборот, задача станет много проще. Мы просто соединим два наибольших локальных максимума и все..

[Urnwestek]

LexiBender в сообщении #807128 писал(а):

Наоборот, задача станет много проще. Мы просто соединим два наибольших локальных максимума и все..

100000 - 100000
999999 - 999999
1 - 999998

точка 1 не лежит под прямой, порожденной двумя локальными максимумами.

[LexiBender]

Urnwestek в сообщении #807130 писал(а):

LexiBender в сообщении #807128 писал(а):

Наоборот, задача станет много проще. Мы просто соединим два наибольших локальных максимума и все..

100000 - 100000
999999 - 999999
1 - 999998

точка 1 не лежит под прямой, порожденной двумя локальными максимумами.

Согласен.. разность между этими максимумами может быть слишком большой, и часть точек окажется вообще "отрезанной" данной прямой.. Возвращаясь опять к началу, и что же делать?) (раз Вы говорите, забыть про оболочку)

[Urnwestek]

LexiBender в сообщении #807131 писал(а):

Согласен.. разность между этими максимумами может быть слишком большой, и часть точек окажется вообще "отрезанной" данной прямой.. Возвращаясь опять к началу, и что же делать?) (раз Вы говорите, забыть про оболочку)

Пусть мы нашли требуемые точки $(x_1,f(x_1)),(x_3,f(x_3))$. Докажите, что если $x_1<x_2<x_3$ то по крайней мере один из вариантов:
$(x_1,f(x_1)),(x_2,f(x_2))$
$(x_2,f(x_2)),(x_3,f(x_3))$
будет не хуже.

[iifat]

Ну, как это примерно видится... Нарисуем график в вертикальной плоскости и бросим сверху горизонтальную длинную палку. Она упадёт одной точкой на самый максимум и (ну, предположим, не серединой) начнёт наклоняться, пока второй точкой не обопрётся на другой максимум. Вот точки опоры и будут вариантом решения. Естественно, наклоняясь, она может уйти с максимума на некую окрестность, да и вторая точка обопрётся не на сам, возможно, максимум.
Если этое дело развить, мож, чего и получится, имхо.
С выбором из вариантов как-то, по-моему, и правда намучено лишнего. Если понимать как написано, то решение — именно, как уже сказали, две соседние точки, максимально различающиеся значениями: всё пустое множество точек между ними лежит под прямой, а круче сделать невозможно.