Думаю почти каждый участник олимпиад хорошо знаком с алгоритмом нахождения подотрезка массива с наибольшей(наименьшей) суммой элементов за O(n).
Просматривая список задач по универским лабам, увидел в одном номере под разными буквами три, вроде бы схожие задачки. а)/b) классика — найти подотрезок с max/min суммой. А вот с) — найти подотрезок массива с суммой, наиболее близкой к нулю. Подумал немного и осознал, что не вижу решения ни за O(n), ни за n*log(n). То ли меня клинит и не вижу чего-то простого, то ли составитель методички отнесся халатно к расположению задач и оформлению требований к ним.
Собственно вопрос к сообществу CF — есть ли решение этой задачи с асимптотикой лучшей, чем квадратичная?
UPD за предложенное решение n*log(n) спасибо I_love_Tanya_Romanova. Остается вопрос о существовании линейного решения...
Заводим какой-нибудь set (или можете вручную дерево поиска писать, если хотите :D) для частичных сумм на префиксах, дальше просто идем по массиву, считая сумму на текущем префиксе, рассматривая upper_bound/lower_bound этой суммы в нашем set и сравнивая эти варианты с лучшим на данный момент. Так как сумма на отрезке должна быть максимально близкой к 0, то сумма на префиксе до конца отрезка должна быть максимально близкой к сумме на префиксе до его начала.
Т.е., если мы зафиксируем место окончания нашего отрезка, как p2, то нам нужно выбрать такое p1, чтоб abs(pref_sum[p2]-pref_sum[p1-1]) было минимально. А для этого нужно проверить два варианта выбора — тот, у которого pref_sum[i] максимальное среди значений не выше нашего, и тот, у которого оно минимальное среди значений, выше нашего. Что мы и делаем с нашим сетом.
Upd. Немного подумал... Кажется, можно все упростить. Перейдем к массиву частичных сумм на префиксах и найдем в нем два самых близких за значением элемента. После сортировки это можно сделать в один проход. Все те же n*log(n), зато без сложных структур данных; и константа должна быть ощутимо меньше.
Спасибо, действительно вот оно и есть достаточно элегантное и простое в реализации решение за n*log(n).
Хотя эти задачки составлялись для студентов, которые будут писать на делфи. Т.е. для этого придется писать некоторое подобие Java`вского TreeSet для получения значений, максимально близких к текущему префиксу. Да и еще работающего за log, т.е. как минимум писать сбалансированное дерево... Не вяжется рядом с классическими задачками, которые пишутся в 5 строк...
И все-таки остается вопрос, что делает эта задача среди линейных...
UPD: да, учитывая предложенную Вами модификацию получается проще реализовывать: сортировка быстрее пишется, чем сбалансированное дерево.
Можно воспользоваться поразрядной сортировкой:) Это к вопросу о линейности.
Есть у меня подозрения, что константа от поразрядной сортировки (ну например log(10^9) для int) будет хуже чем log(n) для n, с которыми можно пытаться решить эту задачу в формате лаб/олимпиад, т.е. при времени работы до минуты скажем. Хотя формально согласен — получаем линейную асимптотику.
Ну так отсортировать можно не по одной цифре, а по половинам чисел(для int) и по четвертям(для long). То есть решение фактически 2*n или 4*n соответственно( если написать грамотно). А в обычной сортировке логарифм двоичный, т.е. это будет около 20.
Не, Вы слишком поверхностно рассуждаете. Что такое 2*n? Это два раза надо найти для каждого значения список мест, где оно встречается, всё это с арифметическими операциями, а потом выписать все элементы в другом порядке. Я думаю, Jovfer прав, что это будет не быстрее. Но не прав насчёт линейной асимптотики — ведь реально получается O(n*log(max)).
Такая сортировка в два прохода на самом деле значительно быстрее стандартной, единственный ее недостаток — она не in-place, и нужно n + 65536 дополнительной памяти.
Никакие списки мест там строить не надо, вот пример кода.
Блин, я писал абсолютно такой же код на java, и он работал также — ну, чуть-чуть, быстрее, чем Arrays.sort()
Да, я немного не точно выразился. Линейная асимптотика относительно числа элементов. Мощность словаря (точнее log(max)) можно считать константой.
тут был бред.
Вроде ясно, что задача эквивалентна поиску двух ближайших чисел в массиве. Интуитивно кажется, что в разумной модели это не должно быть можно сделать за время O(n), хотя доказательства я не знаю.
Вот информация про эту задачу: http://en.wikipedia.org/wiki/Element_uniqueness_problem .
На самом деле, Gautam Kamath объяснил мне, как найти два ближайших числа за время O(n). Делается с помощью рандомизации и хеширования. Если кому интересно, могу расписать детали.
Очень даже интересно услышать.
Насколько я понял, примерно так. Рассмотрим случайную перестановку точек. Далее пусть D -- текущее расстояние между ближайшими точками. Изначально это расстояние между первой и второй точкой. Дальше будем добавлять третью, четвертую и т д точки следующим образом. Поддерживаем хэш-таблицу, где хеш точки x -- это [(x — s) / (100 D)], где s случайное число от 0 до 100 D. Вот попала наша новая точка куда-то. Переберем все остальные точки в ее корзинке, если какая-то пара на расстоянии меньше D, то обновляем D и все перехешируем.
Во-первых, ясно, что в каждой корзинке в каждый момент не более 100 точек. Во-вторых, ясно, что мы обнаружим ближайшую пару с вероятностью не менее 0.99. В третьих, и это самый нетривиальный момент, на k-й итерации у нас будет перехеширование с вероятностью не более O(1 / k). Таким образом, ожидаемое сумарное время перехеширования O(n).
Не понял, но ведь сумма гармонического ряда — это log(n)!
А почему нельзя посмотреть в соседние корзинки и обнаруживать ближайшую точку с вероятностью 1? Слишком часто будет перехеширование?
а что такое соседняя корзинка в случае хэша?
Это [((x — s) + 100D-1) / (100D)] и ([((x — s) — 100D) / (100D)])
Upd: здесь просто понятие корзинки с используемой структурой данных никак не связано(несмотря на то, что при описании этой структуры данных слово "корзинка" является очень популярным), важно просто, что это ассоциативный массив(какой-то unordered_map<int,vector>)
И правда, более того, зачем вычитать случайное S? Разве не правда, что таким образом мы будем перехешировать только в случае, если новая точка обязательно(не с какой-то вероятностью) входит в ближайшую пару среди всех обработанных, а в силу симметрии очень похоже на то, что вероятность этого O(1/k)?
Upd: И если всё это правда, то вместо отрезков длиной 100D хватит отрезков длиной просто D, и мы избавимся от константы 100 в решении.
Да, вроде так будет работать. Спасибо за уточнение.