задачка на алгоритм
Стандарная задачка, сформулирована только необычно формальным языком.
Вот в более узнаваемой формулировке: http://www.careercup.com/question?id=12691671
Вот в более узнаваемой формулировке: http://www.careercup.com/question?id=12691671
Сильно похожа, но я почему-то не уверен в эквивалентности.
И она заставляет ещё больше поверить в невозможность O(N)
И она заставляет ещё больше поверить в невозможность O(N)
Эквивалентность точно есть.
Пусть у тебя есть очередь с линейными enqueue/dequeue и константным findmax.
Сначала enqueue'ишь в нее все элементы до N-K+1, а потом делаешь while(!empty) { print(findmax; dequeue; }.
Я только по ссылке правильного решения не вижу, хотя они вокруг него ходят.
Пусть у тебя есть очередь с линейными enqueue/dequeue и константным findmax.
Сначала enqueue'ишь в нее все элементы до N-K+1, а потом делаешь while(!empty) { print(findmax; dequeue; }.
Я только по ссылке правильного решения не вижу, хотя они вокруг него ходят.
Вообще, написал бы ты свое решение за nlogn. Есть у меня подозрение...
Пусть у тебя есть очередь с линейными enqueue/dequeue и константным findmax.вроде, по ссылке про сложности операций ничего не сказано?
Сначала enqueue'ишь в нее все элементы до N-K+1
а тут разве N**2 не вылезет?
UPD ты, наверное, имел в виду не "до N-K+1", а "до К" - тогда получается K**2 и все счастилвы )
написал бы ты свое решение за nlogn.Ну вроде это-то совсем тривиально:
кладешь первые k элементов в std::multiset, печатаешь max, потом a[1] из сета выкидываешь, а a[k + 1] добавляешь, повторить.
Ммм. Там решение забавное получается. Хоть и в худшем случае вставка одного элемента O(n тем не менее, вставка всех n элементов тоже O(n)... Мне стоило это уточнить, да, сорри.
Тоже верно...
А я в своем "псевдокоде" налажал. Ну да бог с ним, для доказательства эквивалентности не принципиально.
А я в своем "псевдокоде" налажал. Ну да бог с ним, для доказательства эквивалентности не принципиально.
Ну вроде это-то совсем тривиально:
кладешь первые k элементов в std::multiset, печатаешь max, потом a[1] из сета выкидываешь, а a[k + 1] добавляешь, повторить.
откуда там N*logN берется-то?
Log k, разумеется.
То есть еще меньше.
Мне надо было это явно проговорить, дес ка?
То есть еще меньше.
Мне надо было это явно проговорить, дес ка?
дес ка
просто NlogK вполне подходит под критерий топикстартера, а nlogn - нет
Сначала enqueue'ишь в нее все элементы до N-K+1, а потом делаешь while(!empty) { print(findmax; dequeue; }.
вот это совсем неправда: по условию надо вывести максимум во всех "непрерывных" подпоследовательностях длины K
кладешь первые k элементов в std::multiset, печатаешь max, потом a[1] из сета выкидываешь, а a[k + 1] добавляешь, повторить.
да, именно так у меня.
просто NlogK вполне подходит под критерий топикстартера, а nlogn - нетэто одно и то же!
K = N^(1-delta)
K = N^(1-delta)
Ммм. Даже если k == n-1?
Энивей, можно без logk.
Энивей, можно без logk.
Ладно, херню сморозил (хотя мне норм)
Имел в виду:
K может расти с той же скоростью, что и N. Поэтому O(log K) = O(log N)
Имел в виду:
K может расти с той же скоростью, что и N. Поэтому O(log K) = O(log N)
Ммм. Даже если k == n-1?
ну O(N) значит, что при данном K с ростом N время будет расти линейно
если K зависит от N, то это надо явно указывать. Если нужно еще какое-то ограничение сложности по K - надо это явно указывать. Мне постановка задачи как-то так видится
тогда надо не O(N) требовать, а, например, O(N+K)
Выбираем такую подпоследовательнось b_i с сохранением изначального индекса, что
1. b_1 - маскимальный из a_1 .... a_K.
2. за b_i = a_{k_i} следует такой ближайший из последующих элемент b_{i+1}, что либо b_{i+1} > b_i, либо это максимальный из a_k_{i+1}... a_k_{i+K}.
Это делается линейным проходом.
По этой последовательности опять же линейно восстанавливается искомая последовательность (искомое c_i - это ближайшее предыдущее к индексу i+K b_j с небольшим видоизменением).
ПО памяти плохо, но вроде можно соптимизировать, если делсть за 1 проход.
1. b_1 - маскимальный из a_1 .... a_K.
2. за b_i = a_{k_i} следует такой ближайший из последующих элемент b_{i+1}, что либо b_{i+1} > b_i, либо это максимальный из a_k_{i+1}... a_k_{i+K}.
Это делается линейным проходом.
По этой последовательности опять же линейно восстанавливается искомая последовательность (искомое c_i - это ближайшее предыдущее к индексу i+K b_j с небольшим видоизменением).
ПО памяти плохо, но вроде можно соптимизировать, если делсть за 1 проход.
тогда надо не O(N) требовать, а, например, O(N+K)
Какой смысл этого обозначения в твоём понимании вообще?
Как по мне, верны такие равенства, например:
O(N) = O(N + K) = O(2*N) = O(3*N) = O(const*N)
Ну блин. Решение такое же, как и у , просто вместо мультисета моя волшебная очередь.
Подсунули задачку и сказали, что решается за O(N)я бы предположил, что решение опирается на общеизвестную структуру данных heap : http://en.wikipedia.org/wiki/Binary_heap
пусть у нас есть реализация такой структуры данных с таким интерфейсом (мета-код, напоминающий плюсы):
class heap
{
iterator add(int value);
void erase (iterator it);
int max const;
};
тогда используем так:
heap heap;
queue<iterator> s;
//init
for (int i = 0; i < K; ++i)
{
s.push(heap.add(a[i];
}
for (int i = 0; i < N - K; ++i)
{
cout << "max for range [" << i << " , " << i + K << "] is " << heap.max << endl;
heap.erase(s.front;
s.pop_front;
s.add(heap.add(a[K + i];
}
класс heap реализуем классически (как описано на вики только в качестве итератора возвращаем указатель на узел в дереве
1) add возвращает только что добавленный узел, сложность O(K)
2) удаление ноды делаем аналогично удалению максимального элемента, только еще ссылки с родителя надо подфиксить, если того требует представление дерева, сложность O(log(K
3) max возвращает значение рута. сложность O(1)
изначальная инициализация heap потребует O(K * log(K действий, ее можно заменить make_heap типа такого: http://www.cplusplus.com/reference/algorithm/make_heap/
итоговая сложность будет (N - K) * O(log(K + O(K * log(K. опять же надо продумывать какие именно действия мы оцениваем в сложности и каким является K относительно N (можно ли заменит K на константу или нет)
доп память оцениваю в O(K)
в данном случае представлять дерево в виде массива невыгодно, т.к. итератор не должен инвалидироваться при вставке.удалении эелементов
зы: мог налажать в оценке сложности, налетайте, коршуны
мой смысл линейной сложности [O(N)] таков, что dO/dN = const
а твой?
а твой?
Ну есть более общая задача RMQ (Range minimum/maximum query которую можно решать за O(N) предподготовки и O(1) на запрос. Получается общая сложность O(N+K) = O(N) (т.к. K <= N в нашем случае).
А. Ну, справедливо, пожалуй, если буквоедствовать. Там не хватает слов "линейное для любых К".
Зачет.
которую можно решать за O(N) предподготовкиА памяти сколько та структура ест? O(N)?
Не помню. Но точно не больше O(N).
Ладно, теперь простое решение для этого конкретно случая.
Нам потребуется двусторонняя очередь q длиной не более K. Для текущего положения окна ([i, i + K - 1]) в очереди будут храниться индексы элементов массива по следующему правилу:
q[0] = max(i, i + K - 1) (max возвращает индекс максимума)
q[j + 1] = max(q[j] + 1, i + K - 1)
пока q[j] < i + K - 1
Научимся сдвигать окно на 1 за O(1) аммортизированной сложности.
Шаг 1:
если q[0] = i выкидываем головной элемент из очереди
иначе ничего не делаем
Шаг 2:
пока a[q[last]] < a[i + K] выкидываем последний элемент из очереди
затем добавляем i + K в ее конец.
Каждый элемент один раз попадает в очеред и один раз из нее убирается за O(1). Общая сложность O(N).
Для каждого окна ответ - головной элемент очереди.
Вусе.
Нам потребуется двусторонняя очередь q длиной не более K. Для текущего положения окна ([i, i + K - 1]) в очереди будут храниться индексы элементов массива по следующему правилу:
q[0] = max(i, i + K - 1) (max возвращает индекс максимума)
q[j + 1] = max(q[j] + 1, i + K - 1)
пока q[j] < i + K - 1
Научимся сдвигать окно на 1 за O(1) аммортизированной сложности.
Шаг 1:
если q[0] = i выкидываем головной элемент из очереди
иначе ничего не делаем
Шаг 2:
пока a[q[last]] < a[i + K] выкидываем последний элемент из очереди
затем добавляем i + K в ее конец.
Каждый элемент один раз попадает в очеред и один раз из нее убирается за O(1). Общая сложность O(N).
Для каждого окна ответ - головной элемент очереди.
Вусе.
я бы предположил, что решение опирается на общеизвестную структуру данных heap : http://en.wikipedia.org/wiki/Binary_heapи в чем принципиальное отличие (решения) от мультисета?
мой смысл линейной сложности [O(N)] таков, что dO/dN = constтак зачем тогда ты хочешь O(N) заменить на O(N + K) ?
я же согласился ниже там, что это неудачный пример
Шаг 1:
если q[0] = i выкидываем головной элемент из очереди
иначе ничего не делаем
Шаг 2:
a[q[last]] < a[i + K] выкидываем последний элемент из очереди
затем добавляем i + K в ее конец.
А что если:
q[0]=i+1 и a[i+K] > a[i+1] ?
я же согласился ниже там, что это неудачный пример
прости, но я до сих пор не вижу, где и с чем ты согласился.
просто NlogK вполне подходит под критерий топикстартераАга, в Скале так же обосновывают константность их векторов (которые есть префиксные деревья по индексу, что ли): индекс же 32 бита, и каждый уровень дерева по пять бит, то есть у дерева не больше семи уровней, то есть доступ к элементу за константное время.
Ну да, логарифм по основанию 32 от 32-битного числа очевидно ограничен константой, как и любой другой, тут не поспоришь.
Моё видение.
На каждом шаге максимум определять по информации от предыдущего шага.
Реально определять максимум (пробегаться по элементам) надо только в одном случае:
если новый элемент a_j (который попадает в окно) меньше элемента,
вышедшего из окна a_i и a_i == max предыдущего окна max_1. (a_j < a_i && a_i == max_1)
В других случаях значение определяется как max(max_1, a_j).
Для первого случая придумать хитрожопое хранилище аля счётчик.
Если поддержание структуры на каждом шаге и определение максимума O(1) то всё вместе O(N).
На каждом шаге максимум определять по информации от предыдущего шага.
Реально определять максимум (пробегаться по элементам) надо только в одном случае:
если новый элемент a_j (который попадает в окно) меньше элемента,
вышедшего из окна a_i и a_i == max предыдущего окна max_1. (a_j < a_i && a_i == max_1)
В других случаях значение определяется как max(max_1, a_j).
Для первого случая придумать хитрожопое хранилище аля счётчик.
Если поддержание структуры на каждом шаге и определение максимума O(1) то всё вместе O(N).
Если поддержание структуры на каждом шаге и определение максимума O(1)ты невероятно прав. если поддержание структуры и определение максимума занимают O(1 то задача будет решена.
Ну а структура следующая.
Для максимального числа в окне вычисляем и храним максимум элементов справа от него в этом окне.
Т.е. что-то в таком духе (для int и > 0)
subWindowMax = 0
currentItem;
void Add(int a_j)
if (currentItem < a_j)
{
subWindowMax = 0
currentItem = a_j
return
}
subWindowMax = max(a_j, subWindowMax)
Для максимального числа в окне вычисляем и храним максимум элементов справа от него в этом окне.
Т.е. что-то в таком духе (для int и > 0)
subWindowMax = 0
currentItem;
void Add(int a_j)
if (currentItem < a_j)
{
subWindowMax = 0
currentItem = a_j
return
}
subWindowMax = max(a_j, subWindowMax)
Ну а структура следующая.Хотя фигня получилась.
А что если:я слово "пока" пропустил (уже исправил)
q[0]=i+1 и a[i+K] > a[i+1] ?
последний элемент выкидывается пока новый больше последнего (ну или очередь не пуста)
потом новый в нее добавляется.
Если q[0] = i + 1 и a[i + K] > a[i+1] после выполнения как раз получится один элемент в очереди равный i + K.
Хотя фигня получилась.Не уверен, что фигня...
то же самое предложил, если вчитаешься.
И я за минуту еще не понял, правильно это или нет.
Каждый элемент один раз попадает в очеред и один раз из нее убирается за O(1)Не совсем правда, но итоговая сложность похожа на O(N)
Блин, и правда несложно...
Не совсем правда, но итоговая сложность похожа на O(N)Почему не совсем?
Почему не совсем?Добавление нового элемента иногда будет K итераций занимать. Это не O(1).
Но попутно в очереди останется единственный элемент, так что в среднем верное утверждение.
Энивей, спасибо огромное. Тебе в первую очередь
И всем другим откликнувшимся тоже!
ps: хотя я еще буду думать над решением, ибо жутко простым выглядит по итогу.
И всем другим откликнувшимся тоже!
ps: хотя я еще буду думать над решением, ибо жутко простым выглядит по итогу.
Тут O(1) было про добавление элемента в очередь, а не шаг нашего алгоритма. Шаг алгоритма да, там O(K) в худшем случае, но N шагов будут за O(N) работать при этом.
в чем принципиальное отличие (решения) от мультисета?ничем, что-то перемудрил я
ну а по сложности плохая оценка получилась?
ну да, log K тут является слишком большим довеском
Нам потребуется двусторонняя очередь q длиной не более K.А сколько займет построение исходного состояния этой очереди?
Если делать это в лоб, то сначала мы ищем максимум из K за K операций, потом максимум из K-1 (в худшем случае) за K-1 операций, и т.д. Итого O(K^2) в худшем случае.
Ну так не строй в лоб. Возьми пустую очередь и прокрути шаг 2 алгоритма K раз.
Шаг 1 алгоритма сдвигает начало окна на 1 вперед, укорачивая окно.
Шаг 2 алгоритма сдвигает конец окна на 1 вперед, увеличивая окно.
Если начать с пустого окна [0, 0) (пустая очередь) и выполнить шаг 2 K раз получишь как раз то что тебе надо.
Шаг 1 алгоритма сдвигает начало окна на 1 вперед, укорачивая окно.
Шаг 2 алгоритма сдвигает конец окна на 1 вперед, увеличивая окно.
Если начать с пустого окна [0, 0) (пустая очередь) и выполнить шаг 2 K раз получишь как раз то что тебе надо.
Обсуждение не читал, если кому интересно, вот статья с алгоритмом, в котором сложность не больше 3N http://arxiv.org/abs/cs.DS/0610046
Оставить комментарий
Chirkina77
Подсунули задачку и сказали, что решается за O(N)При желании, можно добавить в условие ограничение по памяти O(K).
Решение "в лоб" работает за O(N^2).
Если его чуть-чуть оптимизировать (не затрагивая, по сути, алгоритм то выйдет O(N*Ln K) = O(N*Ln N)
Я уже весь мозг сломал. Если кто решит / знает решение - поделитесь в личке, пожалуйста.