Задачки про деку и сферку

[sim0nsays]

Задачку про деку задал elephantum во времена, когда работал в Невале, кодал Героев5, вел перепалки за Петон и в общем и целом сколько-то относился к геймдев-тусовке (как это я забыл его зафрендить). Вот пусть расскажет о том, как ему тот геймдев и Невал видиццо столько времени опосля.
Задачка типа сложная и на просветление. Помнится, первый решил zemedelec минут

Comments

[jakobz]

Что-то типа половинного деления:
предполагаем что длина дека от n = 1 до m = 1
Меняем один элемент в начале, прокручиваем на m, считая сумму элементов по модулю 2, прокручиваем назад. Меняем элемент обратно, повторяем процедуру. Если суммы равны - то n = m; m *= 2 иначе мы имеем границы длины очереди. Когда границы есть - продолжаем в том же духе, только как следующее приближение берем середину интервала. В общем половинное деление получается, N*log(N).
Вот как-то так, как будет время - напишу в коде.

[sim0nsays]

Йеп. Это решение. Я сейчас стал задумываться, что у решения с маркером наверно меньшая сложность по вероятности.

Вопрос автору решения

[baturadima]

Что делать после того как проверили середину, и она не подходит?

Re: Вопрос автору решения

[sim0nsays]

Автор что-то не отвечает. Если середина не подходит - значит, решение между нижней границей и серединой, иначе между серединой и верхней границей.

Re: Вопрос автору решения

[baturadima]

Думаю можно в это решение добавить маркер (может это в среднем добавит эффективности).
Если бежать на m вперед и считать не сумму эл-в, а сумму маркеров.

Не посмотрел на даты, думал это все совсем недавно. Спасибо за ответ. Когда прочитал решение протупил)

Re: Вопрос автору решения

[sim0nsays]

Мне кажется, это не изменит алгоритмической сложности.

Re: Вопрос автору решения

[baturadima]

Я имел в виду доходить всегда до маркера (не дописал этого).

Re: Вопрос автору решения

[baturadima]

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

Тогда сложность будет O(n*log(кол-во маркеров)), кол-во маркеров длины k в среднем примерно равно n/2^k.

log(n/2^k) = log(n) - k.
Так что если угадать с длиной маркера (log(n)), то сложность в среднем получиться O(n).

Re: Вопрос автору решения

[sim0nsays]

Будут неконстантные затраты памяти на маркер.

Re: Вопрос автору решения

[baturadima]

При выборе длины маркера, мы не знаем размер дека, поэтому размер маркера не может зависеть от размера дека (константен).

Более строго наверно сказать так:). При затратах памяти C, мы со средней сложностью O(n) сможем определять размер дека, при log(n) <= C. :)

Я не утверждаю, что таким алгоритмом можно получить решение со средней сложностью O(n), это только попытка описать влияние длины маркера на среднюю сложность алгоритма.

Спасибо за замечание.

Re: Вопрос автору решения

[sim0nsays]

Мне кажется, это все равно неконстантные затраты памяти. Т.е. либо мы ограничиваем длину маркера неким C, и для достаточно больших N получаем O(n*log(n)) (длина маркера уходит в коэффициент перед O), либо С начинает зависить от N для лучшей сложности, и тогда затраты памяти неконстантны.

Решение O(n)

[baturadima]

1. Делаем тоже самое (m*=2), пока m не привысит размер дека (скажем используя маркер). Сложность O(n). При этом m < 2 * size.
2. Ищем в послед-ти эл-в длины m, максимальное число(k) идущих подряд маркеров (возможно их неск-ко). Берем любую и добавляем еще один -> теперь у нас есть уникальный маркер в деке (послед-ть k+1 выбранного маркера) и сложность его определения O(n).
3. Бежим по кругу и считаем ск-ко элем-в (с учетом уникального маркера легко). O(n).
4. Вытираем добавленный маркер.

По-моему лучше всего использовать маркер единичной длины.