Не хочется изобретать велосипед

[spamsink]

Есть программистская задачка, на которую я не знаю правильного ответа.

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

Например, пусть дан массив [99, 99, 99, 0, 0, 0, 100, 0, 0, 0].

Если мы возьмем подмассив, состоящий только из элемента 100, то среднее остальных элементов будет 3*99/9 = 33, а разность средних - 100-33 = 67.
Если брать в качестве подмассива группу из трех нулей, то среднее остальных равно (3*99+100)/7 = 56.714..., что хуже.
Если мы возьмем подмассив, состоящий из трех элементов, равных 99, то его среднее будет 99, среднее остальных элементов - 100/7 = 14.285..., а разность - 99-14.285... = 84.714... (максимум).

Но при увеличении количества нулей результат меняется. Пусть массив таков:
[99, 99, 99, (триста нулей), 100, (триста нулей)].

Тогда если взять подмассив [99, 99, 99], получим разность средних 99-100/601 = 98.8..., а если взять подмассив [100], получим 100-3*99/603=99.5..., и в этом случае подмассив [100] оптимален.

Comments

[rezkiy.livejournal.com]

посчитать среднее, мин и макс за один проход. Подмассив из одного элемента в котором мин или подмассив в котором макс будут ответом.

[rezkiy.livejournal.com]

Вру. Не увидел слова 'остальных'

[spamsink]

Более того, подмассив, в котором содержится максимум, вовсе не обязан иметь большее среднее:

99, 99, 99, 0, 0, 0, 100, 0, 0, 0

100-3*99/9 = 67
99-100/7 = 84

[rezkiy.livejournal.com]

да, конечно. Я пропустил очень важное слово.

[spamsink]

Ну и сразу скажу, что вычесть из каждого элемента среднее по массиву и воспользоваться https://en.wikipedia.org/wiki/Maximum_subarray_problem правильного ответа не даёт.

[vak]

Разве что за N^2 пополам проходов.

[spamsink]

Это, естественно, не очень интересно, хотя для маленьких массивов сойдёт, конечно.
Но вот даже вышеупомянутую maximum subarray problem сформулировали в 1977 году, а линейное решение придумали далеко не мгновенно, так что я не оставляю надежды.

[yatur.livejournal.com]

В таких задачках шаг влево или вправо - и опаньки, линейного решения нет, только полный перебор.

[spamsink]

Я придумал линейную эвристику, которая сгодится на первое время.

[sab123.livejournal.com]

Есть ли некое требование про размер этого подмассива?

Потому что иначе ответ прост:
За один проход находим среднее массива, а так же самое большое и самое маленькое число в нем (и их позиции). Смотрим, что дальше от среднего в массиве - самое большое или самое маленькое число, и соответственно выбираем его как подмассив из 1 элемента.

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

Вот если размер подмассива фиксирован - то сложнее.

[spamsink]

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

[kcmamu.livejournal.com]

Это всё для исправления шрифта надо?
Тогда, подозреваю, более адекватная постановка была бы с поиском не максимальной разницы средних, а минимальной суммы квадратов отличий чисел от соотв. средних.

[spamsink]

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

[archaicos.livejournal.com]

Это пахнет проблемой Longest Common Substring, которая решается через Dynamic Programming за квадратичное время.

[spamsink]

Я сделал апдейт с примерами.

[spamsink]

Не вижу связи, но судя по немонотонности решения (см. апдейт), увы, похоже, что без квадратичности не обойтись.

[kcmamu.livejournal.com]

Я нечто похожее творил так: берем окрестность пиксела, упорядочиваем все значения по возрастанию яркости и ищем границу в этом упорядоченном списке. Новое значение яркости := среднее по тому подмножеству, куда попал сам этот пиксел. Устроившие меня результаты -- такие, как на картинке (она уменьшена на 50%, а если кликнуть, будет в полный размер):



Должно хорошо работать в тех случаях, когда картинка не слишком зашумлена и типичные "береговые линии" (если всё, что ниже порога, -- море, а выше -- суша) достаточно гладкие, без островков и луж.

[archaicos.livejournal.com]

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

[spamsink]

Я уж подобных алгоритмов наперепробовал. У меня есть три способа выбора "нового белого" и "нового черного":

1. Максимум и минимум в окрестности.
2. Среднее среди элементов, больших среднего по окрестности, и среднее среди меньших.
3. Граница выбирается по максимуму разницы между соседними упорядоченными элементами (если таких несколько, делается взвешенное усреднение), и вычисляются средние по двум подмножествам, которые и становятся "новым белым" и "новым черным".

Алгоритм "если центральный пиксель светлее среднего, сделать его новым белым, а если темнее - новым черным" (максимизация контраста) у меня тоже есть. Он применяется в предобработке перед усреднением. Но хотелось бы уметь в постобработке отъедать жирные черные наплывы, как, например, в верхней части букв (особенно I) тут

не сильно трогая остальное. Сейчас я использую эрозию (сделать пиксель новым белым).
Также я экспериментировал с методом new = max(old, max + min - old), т.е. чем темнее был, тем светлее станет, но не темнее прежнего. Итеративно это красиво, но пользы мало.

Еще я с сегодняшнего дня умею делать в точности круговые окрестности (а не просто множество пикселей, попадающих центрами в круг) и вычислять взвешенные минимум и максимум (тут уж не локально, а пользуясь известными границами области значений). Если радиус не больше sqrt(2.25), т.е. если пиксель с весом 100% всего один - центральный, то эрозия получается плавная, чем я сейчас и пытаюсь пользоваться. Но будь у меня возможность делать направленную эрозию, я бы, возможно, мог достичь более красивого результата.

[sab123.livejournal.com]

Приходит в голову вариант с двумя проходами:

На первом проходе определяем среднее массива.

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

Введение ограничения числа X ограничивает оптимальность, но и ограничивает время выполнения O(X*N), то есть при малом X выходит O(N).

[spamsink]

Для простоты формулировки алгоритма предлагаю предположить, что массив уже нормализован, т.е. его среднее равно нулю.

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

[sab123.livejournal.com]

Пардон, в алгоритм вкралась неточность. Вот исправленный вариант:

На первом проходе определяем среднее массива.

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

Введение ограничения числа X ограничивает оптимальность, но и ограничивает время выполнения O(X*N), то есть при малом X выходит O(N).

Если X=N, то получается в худшем случае квадратичный алгоритм, который находит оптимальную точку.

[sab123.livejournal.com]

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

И средневзвешенная точка оказывается фиксированной, это среднее изначального полного массива.

[spamsink]

И так не будет оптимума, потому что иногда может оказаться полезно выбросить несколько первых добавленных чисел для улучшения результата.
Например, допустим массив из 10 чисел уже нормализован:

[1, 7, -1, -1, ...]

Берем 1 - разница средних 10/9. Добавляем 7, разница средних 5, отлично. Дальше хуже. Твой алгоритм вернет [1, 7], что неверно, потому что оптимально [7], разница средних 70/9.

[sab123.livejournal.com]

Да уж, действительно. Я подозреваю, что это можно исправить через более лучший анализ "производной", т.е. как каждое число влияет на среднее. Или может даже "второй производной".

[spamsink]

Я подумал и решил, что находить линейным алгоритмом в нормализованном массиве подмассив не длиннее 50% исходного с максимальной по абсолютной величине суммой, а потом пытаться отъедать у него элементы с краев, пытаясь увеличить разброс средних, будет достаточным приближением к тому, что я хочу. И не беда, что он будет всегда отвечать на тестовом примере [99, 99, 99].

[sin-gular.livejournal.com]

А если отсортировать сохраняя массив индексов и пройти по индесам аналогом максимального подмассива?

[spamsink]

И как бы оно работало на тестовом примере?
Ну будет у нас

[100, 99, 99, 99, 0, 0, 0, 0, 0, 0]
[  6,  0,  1,  2, 3, 4, 5, 7, 8, 9]

,
и дальше?

[sin-gular.livejournal.com]

Не полное решение, но с предложенным тестовым примером справится, или я ошибаюсь?

[spamsink]

Так нет же, ведь правильный ответ зависит от размера массива. Максимальный подмассив в обоих случаях - тот, который получится из 3х99, а ответы должны получаться разные.

[sevabashirov.livejournal.com]

Чем-то напоминает феномен Уилла Роджерса.

[sin-gular.livejournal.com]

Ну допустим если для каждого подмассива считать именно Сумаа/Длина-(ВсяСумма-Сумма)/(ВсяДлина-Длина) с этими тестами справится.
Но [99, 99, 15, 99, 99, 0, 0, 0, 100, 0, 0, 0] уже непройдёт...

[sin-gular.livejournal.com]

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