Pull to refresh

Comments 101

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

Пусть функция f(X) работает так: ей на вход подаётся множество X, она делит его на 2 множества - в XA все элементы меньше или равны первого числа a исходного множества X, а во втором XB больше этого числа. Такое деление выполненяется за линейное время. Ключевой момент: если длина XA равна a, то в нем нет минимального числа и искать надо в XB. Таким образом функция знает что ей вызывать дальше рекурсивно - f(XA) или f(XB). "Легко видеть" (на самом деле нет), что сложность алгоритма O(N) так как алгоритм проходится сначала по всему множеству линейное время, потом по его половине, а вторую половину игнорирует и т.д. N + N/2 + N/4 + N/8 +... = 2*N т.е. время линейное.

Такой вариант решения приведен в статье. Только с учетом, что множество не является отсортированным. Сортированное вообще не проблема перебрать, только сортировка занимает кучу времени.
Я наверно что-то не понял, но где простейшие и оптимальные варианты?

Для случая когда мы ожидаем такое число ближе к началу:
for(int i=0; i<arr.length; ++i) {
  if(arr[i] != i)
    return arr[i-1]+1;
}


Для случая когда мы ожидаем его ближе к концу бинарный поиск по такому же условию.
O(N) и O(log(N)) соответвенно. По памяти везде O(1)

Краевые условия не писал, все понятно. Код для демонстрации идеи.
Это всё здорово, если у на отсортированное множество… А рассматриваются варианты — где значения лежат как попало. Сортировка рассматривается как раз в конце. И считается её производительность.
т.е. { 0, 12, 4, 7, 1 } здесь MEX равен 2-м.
Я поправился. Был сначала не прав.

Я начал рассказ с конкурса на OZON в котором я пробовал участвовал, сделав «предварительный вариант» алгоритма просеиванья, приз за него я так и не получил, OZON счел его неудовлетворительным… По каким именно причин — он так и не сознался… До и кода победителя я не видел. Может у кого-то есть идеи как можно решить задачу поиска MEX лучше?

Я бы ваше решение тоже не зачел. Оно откровенно неоптимальное.
Тогда так www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array
A O(n) time and O(1) extra space solution

А Вы сами это решение читали?

Чувак 4 раза перебирает массив
// Check if 1 is present in array or not
    for(int i = 0; i < n; i++)
    {
        if (arr[i] == 1)
        {
            ptr = 1;
            break;
        }
    }
   
    // If 1 is not present
    if (ptr == 0)
        return 1;
   
    // Changing values to 1
    for(int i = 0; i < n; i++)
        if (arr[i] <= 0 || arr[i] > n)
            arr[i] = 1;
   
    // Updating indices according to values
    for(int i = 0; i < n; i++)
        arr[(arr[i] - 1) % n] += n;
   
    // Finding which index has value less than n
    for(int i = 0; i < n; i++)
        if (arr[i] <= n)
            return i + 1;

4 раза!
О каком O(n) вообще может идти речь?
А Вы сами это решение читали?

Конечно. Оно простое и оптимальное для общего случая.

4 раза!
О каком O(n) вообще может идти речь?

Вы точно знаете что означает O(N)?
Вы точно знаете что означает O(N)?

В моем понимании — это количество итераций которое нужно совершить. Обычно рассматриваем самый кривой случай. Так вот коде парня аж 4 прохода по массиву. Может с точки зрения математики — это не в счет, но вот сточки зрения реальной задачи — бегать по сто раз по массиву не выглядит перспективной идеей.
Так. Получается по вашему — любая функция которая принимает одни аргумент — это O(n)?

Я хоть как-то попытался это рассчитать в базовых операциях.
Нет, это оценка с точностью до константы. Применяется к последовательностям. Например, последовательность

S n = n + 22 


при больших n у нас приблизительно S n = const*n

Но то же самое справедливо и для последовательности

S2 n = 2*(n + 22) 


При больших n аналогично S2 n = const*n

Таким образом, обе эти последовательности имеют асимптотическое поведение O(n).

Это, кстати, к вопросу о том, нужен ли университет для программирования.

А вы статью читали? Автор пишет O(n*3), это прямое свидетельство в том, что он не понимает О-нотации.

Строго говоря, алгоритмы, которые модифицируют исходный массив (в особенности - разрушают, как это делает предложенный алгоритм со сложностью O(N) и якобы О(1) по памяти), являются O(N) по памяти, т.к. для их использования вам придётся сделать копию массива. И если с сортировкой, эти данные могут еще понадобиться (и тогда этот алгоритм будет самым выгодным), то с изменением знака (кстати, использование знакового разряда, как мне кажется, ничем не отличается от использования отдельно выделенной битовой матрицы размера N).

Кстати, еще одно замечание для автора касательно второго варианта (где выделяется второй массив). Нам не надо искать максимум для выбора его размера, мы и так знаем, что результат находится в диапазоне от 0 до n, поэтому и массив нужен размера n, инициализировать можно нулями (при выделении ОС отдаст именно такую память, может даже время не потратиться, если будет заранее доступен кусок обнулённой памяти), а далее просто проходимая по массиву, отбрасывая числа >= n, проставляя 1 по индексу для чисел от 0 до n-1. Дальше быстрый проход по этому массиву до первого нуля.

Автор пишет O(n*3), это прямое свидетельство в том, что он не понимает О-нотации.


Ок. Предположим, что я не понимаю нотации.
Но вариант O(n) меня вообще не устраивает. Т.к. в таком случае непонятно какой размер у O. В итоге я стараюсь считать шаги в максимально простых действиях: в проверках, в бинарных расчетах. Что-то более менее понятное по скорости. И что позволяет хоть как-то сравнить три подхода.
Что-то более менее понятное по скорости. И что позволяет хоть как-то сравнить три подхода.


Это не позволяет, увы. Стоимости разных операций в процессоре совершенно разные. Причём это варьируется от процессора к процессору. Часть операций использует кэш-память, что резко ускоряет процесс в ряде случаев, раз в 40 запросто.

Поэтому модель RAM машины на современных десктопах/серверах работает с трудом. Соответственно, когда вы не используете O-нотацию, вы чаще всего получаете ошибку превышения точности (за которую тех же физиков «бьют линейкой по голове» :-)).
О-нотация — это асимптотика, её используют для выбора алгоритма когда понятно, что потребуется обрабатывать много данных, т.к., грубо говоря, если завтра объём обрабатываемых данных возрастёт в 50 раз, то не имеет значения, что алгоритм с O(n) реально выполняет 10*n операций, т.к. время исполнения этого алгоритма растёт гораздо слабее чем у алгоритма с O(n^2). На малых объёмах на асимптотическую сложность не смотрят, здесь всё решают реальные замеры. И не редкая ситуация, когда алгоритм с худшей асимптотической сложностью имеет меньший коэффициент, чем растущий медленнее. Это одна из причин, по которой худшие по О-нотации алгоритмы изучают. И именно это является причиной того, что библиотечные реализации сортировки, как правило, содержат две реализации — быструю сортировку и один из алгоритмов (какой конкретно не помню, подозреваю что пузырёк) с квадратичной сложностью. При чём выбор того, на каком количестве элементов следует переключаться на быструю сортировку, скорее всего продиктован реальными замерами.
Строго говоря, алгоритмы, которые модифицируют исходный массив (в особенности — разрушают, как это делает предложенный алгоритм со сложностью O(N) и якобы О(1) по памяти), являются O(N) по памяти, т.к. для их использования вам придётся сделать копию массива.

Массив в конце можно восстановить. Никаких необратимых изменений мы в нем не делаем.
Можно сказать что или массив можно менять или не thread safe или O(N) по памяти. Так совсем честно будет.
В представленном виде мы явно делаем необратимые изменения. См.

    // Changing values to 1
    for(int i = 0; i < n; i++)
        if (arr[i] <= 0 || arr[i] > n)
            arr[i] = 1;


Наверное, как-то можно исхитриться и при определённой статистике данных как-то сделать эти манипуляции обратимыми. Но я не вижу пока как.
Задачка у автора без отрицательных чисел. В ней все обратимо.
Чуть-чуть переписать и будет обратимо.

Спасибо за то, что собрали варианты вместе. По поводу оценки сложности, я заметил в статье некоторые проблемы в нотации. Буква О введена именно для того, чтобы показывать характер роста вычислений. Ровно один проход, ровно шесть проходов или ровно двадцать проходов - это все O(n), константные множители отбрасываются.

Аналогично с квадратами - O(n^2) это и есть O(n^2). Вы можете посчитать количество вычислений точнее и сказать, что их будет ровно 100n^2+72n+21, но сложность в этом случае будет O(n^2).

Кажется, для точного количества вычислений используется буква T у Кормена.

Надо поискать будет эту нотацию, спасибо.

А почему бы не сложить числа в двоичную кучу? Строим кучу по возрастанию, потом вытаскиваем оттуда дважды минимальный элемент и смотрим, насколько полученные числа отличаются. Если больше чем на единицу то прибавляем к минимальному значению 1 и вот ответ. Иначе достаём следующий минимальный элемент и сравниваем с предыдущим.

О(n) на построение и О(n) сравнений в худшем случае. В итоге сложность О(n).

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

Т.е. мы сортируем массив? Это «дорогая» операция если что.

Ужасный пост.
О проблемах с O-нотацией уже сказали, не буду повторять.
Скажу лучше про затраты памяти. То, что некоторые быстрые алгоритмы требуют дополнительной памяти — это приемлемо. Как говорится, "за всё надо платить", за скорость в том числе. (и наоборот — за экономию памяти алгоритмы, как правило, платят скоростью)
Стёб же над "математиками" — совершенно неуместен.


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


Примерно так:


  1. Тривиальное решение ("в лоб") — не требует дополнительной памяти, но является квадратичным — O(n^2). Впрочем, производительность приемлема на крошечных множествах.
  2. Решение, основанное на сортировке — работает с асимптотикой используемого алгоритма сортировки, т.е. не быстрее чем O(n*log_n). Алгоритм не зависит от размерности рассматриваемого множества.
  3. Просеивание — работает с асимптотикой O(n), но требует дополнительной памяти O(m), где m — размерность множества. Память O(m) серьёзно ограничивает применимость алгоритма на практике, тем не менее — где-то и он может пригодиться.

P.S.:
Вижу алгоритм, работающий за O(n), с дополнительной памятью тоже O(n).
(использовать хэш-таблицу)

Вижу алгоритм, работающий за O(n), с дополнительной памятью тоже O(n).

Hash таблицы хороши если мы пытаемся найти значение которое точно есть, или то которого нет. В других случаях нам всё равно придется устраивать перебор значений. Что в целом — та же сортировка…

А разве нам не достаточно находить, значение точно есть или его нет? Перекладываем значения в HashSet и ищем в нём числа по порядку, начиная с 0. Первое отсутствующее значение и будет ответом.

Перекладываем значения в HashSet и ищем в нём числа по порядку, начиная с 0.
Ну как бы это цикл по элементам которые еще сложнее чем массив.
Чуть HashSet 0 быстрое нахождение элемента, если он есть.

Но в этом цикле и вставка, и проверка наличия занимают O(1) времени. Итого O(n).

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

Так нам это и нужно!
Делаем в два прохода по набору исходных данных.
Проход 1 — запихиваем всё в хэш-таблицу.
Проход 2 — для каждого значения x в исходном наборе данных проверяем наличие в хэш-таблице значения, равного x+1. Если x+1 не найдено — значит, это потенциальное решение задачи.
Конечным результатом будет минимум между всеми отсутствующими в хэш-таблице x+1. Дополнительно надо проверить минимальное и максимальное значения в исходных данных (на любом из проходов).


P.S.:
Таким алгоритмом решается целый класс задач.
Вот ещё один пример: "найти в массиве все пары чисел, сумма которых равна числу m".

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

Короче, просто доп. массив такого-же размера, что и оригинальный, инициированный каким-то значением, которого нет в оригинальном наборе, хоть -1, хоть INT_MIN, не важно, а дальше с ним работаем, как с хэшем в вашем варианте.
И тут встает вопрос: но если у нас индексы совпадают со значением, зачем в этом массиве хранить целые числа, почему не хранить просто булевые значения: true/false? Хоп и мы пришли к алгоритму просеивания :)

Да, Вы правы.
После Вашего комментария, я понял идею оптимизированного алгоритма просеивания.
(тяжело понимать автора — у него вроде как берётся массив в размере множества; а Вы объясняете с оптимизацией по дополнительной памяти до размера входных данных)

О, кстати, вижу что я ошибся при оценке авторского алгоритма просеивания. Там же из-за инициализации массива будет асимптотика не O(n), а O(max(n,m)). Можно упростить до O(m), если во входных данных нет повторений, т.е. n<=m.


А хэш-таблицы не стоит выбрасывать из рассмотрения. И вот почему — алгоритм просеивания (хоть авторский, хоть оптимизированный) рассчитан только на работу со множеством целых чисел!
А что если множество состоит из других объектов? Да, к этому случаю возможно адаптировать просеивание, если назначить каждому объекту какой-то числовой (порядковый!) индекс. Для этого нужно определить порядок объектов во множестве — т.е. выполнить сортировку множества перед просеиванием. И сортировка эта будет стоить минимум O(m*log m), ухудшая асимптотику всего алгоритма.
Правда, если планируется выполнять алгоритм просеивания много раз на различных входных данных (но на одном и том же множестве объектов), то повторять сортировку множества не нужно — и получаем довольно быстрый алгоритм с предварительным расчётом.

В алгоритме просеивания нужно не O(m) памяти, а O(n).
Просто в булевском массиве должно быть столько же элементов, сколько в изначальном.

Тогда при первом проходе мы просто забиваем на числа, которые больше n — нас они не интересуют.

Вот, кстати, почему решение автора кривое. На тесте {1, 1000000000} эта версия алгоритма просеивания просто упадёт по памяти.
Принял и согласен, можно игнорить числа больше длинны множества. Т.к. они явно нам не интересны. Поправлю
P.S.:
Вижу алгоритм, работающий за O(n), с дополнительной памятью тоже O(n).
(использовать хэш-таблицу)

Да не надо хеш-таблицы даже. Чтобы найти минимальнео число, не встречающееся среди заданных n наужен лишь битовый массив на n бит.

А нельзя что-то типа вектора-индикатора прикрутить? Алгоритм примерно такой:
1) Выделить массив bool-переменных размера исходного массива (можно сжать и получить size/8 байтов). Это O(1) по времени, но O(n) по памяти.
2) Пройти в цикле исходный массив, заполняя в true соответствующие индексы этого bool-массива. Это O(n).
3) Пройти bool-массив, индекс первого false — это ответ. Тоже O(n).
Итого O(n) и даже константа небольшая.
Это и есть «просеиванье». там как раз создается boolean массив…
Перечитал повнимательнее, да, конечно, это оно и есть. Просто смутил в конце подсчет сложности, который получился O(n^2).
Это «просеивание». Вообще задача олимпиадная, а у них свои погремушки, часто редко встречающиеся в нормальной жизни. Например, если массив можно «уничтожить», то есть, изменить до неузнаваемости, то можно сделать O(n) по времени и O(1) по памяти (см ссылку выше).
Меня вот удивляет одна вещь, соревнования по скорости сортировки максимально оторваны от реальности, и всем на это глубоко пофиг. Сортировка одного массива — это почти академическая задача. Она требуется всего пару раз в жизни…

В реальности гораздо чаще нужно сортировать многомерный массив — результат сканирования таблиц, или любого большого количества данных хоть в какой-то структуре хранения. Массив в виде адресов, индексов, числовых и текстовых значений… То-есть изначально разношорстный комок данных.
Для этого есть готовые алгоритмы сортировки, но видимо они слишком сложны для рассмотрения.
Для этого есть готовые алгоритмы сортировки, но видимо они слишком сложны для рассмотрения.

Все алгоритмы сортировки сводятся фактически к quicksort. Ничего быстрее пока не придумали.

Это не так. Вопрос, какие случаи мы хотим лучше и какие данные мы хотим. Иногда и merge, иногда и хитрые комбинации.

Про быстрее. От данных зависит. Вдруг мы целые сортируем. Тогда и counting, и Radix за линейное можно.

Уже многие отметились. Попробую предложить что-то новое. Ищем за один проход. Перебираем поэлементно. Каждый элемент i образует либо новую цепочку LinkedList, либо присоединяется к существующей. Если есть цепочка с последним элементом равным i-1, то элемент присоединяется к ней в конец (становится ее последним элементом), если есть цепочка c первым элементом i+1 то в начало (становится ее первым элементом). Если нет ни одной такой подходящей цепочки — создается новая.
В третьем примере множества a={11, 10, 9, 8,15,14,13,12,3,2...106,104} последовательно перибирая элементы, дойдя до a[3] будем иметь одну цепочку от 8 до 11, на a[4] будет уже две цепочки {8:11}, {15}, a[7] — две цепочки {8:11}, {12:15} и т.д.
Для быстрого поиска нужной цепочки, корни всех цепочек будут образовывать дополнительное сопоставление число в корне — указатель цепочки, а вершины всех цепочек сопоставление число в вершине — указатель цепочки. Все цепочки также должны быть упорядочены по возрастанию своих корней. Если элемент подходит для конца одной цепочки и начала другой, то две цепочки склеиваются в одну через этот элемент.
После перебора всех элементов массива, будет образован набор цепочек. В любом случае первый отсутствующий элемент будет определен как либо:
а) n-1, где n первый элемент цепочки, при n-1 != 0,
б) либо k+1, где k — последний элемент первой цепочки.
Объяснение получилось громоздким, но думаю плюсы у данного алго найдутся: не требуется сортировка. Можно сделать за один проход. По памяти не требователен (сумма длин всех цепочек равна количеству элементов, правда нужна доп. память на быстрый поиск по корням и вершинам). Должен любить работать с множествами, где отсутствующих элементов почти нет.

прочитал несколько раз. Понял только, то что очень много памяти потребуется…

Да, согласен, описание такое себе. Что же, выложил на github эту версию алгоритма. Поиск за O(n) без всяких множетелей. Потребление памяти можно довести практически до константных значений. Это не продакшен версия, но ее можно доработать, что бы она работала в динамике.

Если у вас данные такие: {1, 3, 5, 7, 9, 11}, экономично получается? Как бы ищут универсальный алгоритм…

P. S. Надоело час ждать, напишу тут.

Можно уменьшить количество памяти для просеивания. Посчитать сколько чисел одинаковой разрядности (для двоичных трёхразрядных: 00X — 2 числа, 0XX — 4, XXX — 8) за первый проход и потом взять группу, где количество будет меньше максимума и уже от неё плясать. Подпортит статистику одинаковые числа, но «меньше», в любом случае гарантирует наличие вакансии.
По памяти расходы смешные, в худшем случае теряем только этот проход.
Для быстрого поиска нужной цепочки, корни всех цепочек будут образовывать дополнительное сопоставление число в корне — указатель цепочки, а вершины всех цепочек сопоставление число в вершине — указатель цепочки. Все цепочки также должны быть упорядочены по возрастанию своих корней. Если элемент подходит для конца одной цепочки и начала другой, то две цепочки склеиваются в одну через этот элемент.

Вот эта часть даст квадрат или n*logn в лушем случае если хорошо написать.
На данных вида:
1-3-5-7-9-2-6-4
Не годится. Просто отсортировать даст тоже самое…
Учитывая, что у вас фактически используется O(n) памяти, просеивание выходит лучше.
Спасибо, автор. Интересная идея алгоритма поиска.

В контексте исходной «озоновской» задачи можно попытаться ввести в структуру данных какие-нибудь инварианты, которые поддерживаются при её работе и облегчают выполнение операций.

В задаче требуется сделать только операции добавления и «шифрования». Оставим пока в стороне «шифрование» и рассмотрим только структуру данных с операцией добавления.

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

Дырки в нумерации могли бы образоваться за счёт удаления пользователей, но удаление нас реализовать не просят. Возможно, это от «Озона» специальная ловушка, и они ожидают, что вы: 1) зададите вопрос, а точно ли им не нужно удаление; 2) по своей инициативе сделаете удаление.

Если делать удаление — то массив занятых id останется отсортированным. А в отсортированном случае можно найти пропуск быстрее, чем за O(n), а именно, за O(log(n)). Смотрим на средний элемент массива и проверяем, есть ли в первой половине пропуски. Критерий: values[n/2]>n/2. Если есть — ищем дальше в первой половине массива, в противном случае — во второй.

Таким образом, отсортированный массив id — это второй возможный инвариант.

Теперь рассмотрим «шифрование». Даже если в массиве id до «шифрования» не было пропусков — то после «шифрования» они появятся. Но операция «шифрования», вероятно, выполняется реже, чем добавление новых пользователей. Поэтому есть смысл делать сортировку массива id при «шифровании», тогда для поиска свободного id будем всегда иметь отсортированный массив занятых id.

Можно также попытаться воспользоваться свойствами операции «исключающее или» для облегчения сортировки. Подозреваю, что, если исходный массив был отсортирован, а потом все его элементы сложили по модулю 2 с константой — то отсортировать полученный массив можно быстрее, чем в общем случае.
В контексте алгоритмических задач — предположение «операция шифрования выполняется реже» неверно. Напротив, решение должно выполняться за заданное время даже при последовательности операций «добавление-шифрование-добавление-шифрование».

И поэтому требуется придумать структуру, в которой mex фактически выполняется за сублинейное время. И я бы попробовал дерево по двоичным разрядам с отложенной операцией xor. Да, это кажется сработает. Асимптотика добавления нового числа O(log m), шифрования вообще O(1). Правда, нахождение текущего ID пользователя будет занимать O(n), но эту операцию от нас и не требуют. А в конце за тот же O(n) находим все ID.
Я тоже думал предложить отложенный xor. Более того, несколько операций «шифрования» эквивалентны одной, у которой ключ — исключающее «или» от всех предыдущих ключей.

Проблема в том, что отложить xor можно только до следующего добавления, так как до и после ксорки минимальные свободные ID различаются.

Да нет же: вместо шифрования базы можно шифровать входные данные. Просто поддерживайте, что в базе хранится то, что должно, если бы все элементы в базе про-xor-ились с заданным k. При добавлении числа x, добавляйте x xor k. При шифровании базы обновляйте k.

Учитывая, что у нас дерево, то в каждом поддереве хранится число, на которое это поддерево нужно xor-нуть. И когда спускаемся, продвигаем это число в child nodes.
Правда как подсказали ребята из Озона, отложенный xor не нужен.
Задачу также можно решить за O(n*logn) времени и O(1) памяти с помощью двоичного поиска без сортировки. Для этого воспользуемся тем, что все элементы в множестве уникальны. Поэтому мы можем просто взять и за один проход подсчитать количество элементов, меньших или равных k. Если это количество меньше k, значит MEX <= k.
На несортированном множестве мы ищем элемент меньше k.
Что за k? И каково будет минимальное отсутствующее число?
k можно взять равным половине количества учётных записей пользователей. Найдя кол-во чисел, меньших k, можно установить, находится ли минимальный отсутствующий элемент в первой половине массива. Если да — то применить этот же алгоритм рекурсивно для первой половины массива. Если нет — то применить его для второй половины массива и т.д.

Очень хорошая идея, кстати. По-моему этот алгоритм имеет сложность O(n), а не O(n*log(n)). И по сравнению с другими описанными здесь алгоритмами с O(n), он по памяти имеет сложность O(1) и не портит исходный массив. Так что очень привлекательный алгоритм.
так массив не сортирован. Тогда, сначала, его нужно отсортировать… что бы это работало. Кстати, сверху описан подобный алгоритм поиска именно на несортированном массиве.

Это не классический бинпоиск в массиве, а дихотомия или же "бинарный поиск по ответу". Взяв любое k и подсчитав, сколько элементов в массиве <= k мы можем понять если там дырка или нет (т.е. ответ < или > k). Это позволяет отбросить половину возможных ответов.


Грубо говоря, есть булевый массив, который заполнен true для индексов больше ответа и false для индексов меньше ответа. Мы делаем бинпоиск в этом массиве. Но вместо вычисления всего массива сразу мы вычисляем только те элементы, на которые смотрит бинпоиск. Вот и получается O(n log n). log n итераций бинпоиска, каждая за O(n) вычисляет элемент ответа.

Вот и получается O(n log n). log n итераций бинпоиска, каждая за O(n) вычисляет элемент ответа

По-моему здесь всё-таки сложность O(n), а не O(n log n), так как поиск по оставшейся половине требует просмотра каждый раз в 2 раза меньшего кол-ва элементов. И это существенно. Ведь сумма 1/2+1/4+1/8+… = 1. Общее количество просмотренных элементов не превысит n независимо от того, сколько раз алгоритм делил массив пополам.

Нет, вам надо каждый раз просматривать все n чисел, чтобы ответить на вопрос: "сколько чисел <= k". Вы же исхожный массив не сортируете, не трогаете, а только просматриваете. И это k меняется в бинпоиске.

Хорошо, уточню, ошибся. Первый раз вы просматриваете n элементов, потом n/2, потом n/4 и т.д. Сумма 1+1/2+1/4+1/8+… = 2.
Так что максимальное суммарное количество элементов, которые придётся просмотреть, равно 2n. А это означает O(n), не так ли?

Если бы было O(n log n) — то были бы другие зависимости. Например, для n=10 потребовалось бы 10 итераций, для n=100 — 200 итераций, для n=1000 — 3000 итераций и т.д., то есть количество итераций растёт быстрее, чем const*n. Или, что то же самое, отношение количества итераций к n растёт неограниченно (хотя и медленно).

В вашем же случае неограниченного роста отношения количества итераций к n нет, отношение остаётся константой, не зависящей от n.
Первый раз вы просматриваете n элементов, потом n/2, потом n/4

Опишите весь алгоритм. Почему потом просматривается n/2 элементов а не n?
Обсуждаемый в этой ветке алгоритм каждый раз просматривает все элементы, чтобы подсчитать, сколько из них меньше текущего перебираемого бинпоиском числа.

Вы правы, я ошибся. Конечно же, надо просматривать весь массив каждый раз, а не его часть, как мне первоначально показалось. Тогда, как вы и написали, будет O(n log n).
Многие придрались к O(n), мол все алгоритмы O(n) и по фигу, что «O» везде разное и не даёт фактически сравнить количество итераций.

В задаче от Озона явно написано "наиболее оптимальное с точки зрения асимптотики". Асимптотика — это O-нотация.


мы рассматриваем случай когда исходное множество НЕупорядоченное.

В задаче от Озона явно сказано: реализовать структуру [данных] с операцией добавления нового пользователя. Это значит, что вам недостаточно сделать поиск по множеству, вам еще и нужно сделать такое множество, в котором было бы эффективное добавление (и, до кучи, эффективное "шифрование").


Самый быстрый алгоритм сортировки — это «quicksort» (быстрая сортировка), которая имеет сложность в T1(n log(n)).

Это утверждение неверно. Быстрая сортировка (а) имеет сложность O(n log n), а не (какое-то там) T(n log n), и, что важнее (б) "самая быстрая" только для общего случая (в частности, для целых чисел есть сортировки O(n+r), где r — диапазон).

В задаче от Озона явно написано «наиболее оптимальное с точки зрения асимптотики». Асимптотика — это O-нотация.


Для меня, как для разработчика, важнее всего скорость и объем оперативной памяти с которой будет выполняться алгоритм.
Мне кажется, OZON, и имели всё же «скорость работы», пусть у упаковали это в описании O-нотации. Ибо решается практическая, а не теоретическая задача.

Это значит, что вам недостаточно сделать поиск по множеству, вам еще и нужно сделать такое множество, в котором было бы эффективное добавление (и, до кучи, эффективное «шифрование»).

Я не увидел в контексте этой задачи, что необходимо сделать собственную структуру данных.
Мне вообще не понравилось как поставлено условие. Что я могу сделать добавление данных как мне «удобно». Может мне удобно так, что без гайда по API вообще не понятно будет. А тестировать как? К самой загрузке данных — много вопросов. Они пишут про ограничение объема оперативной памяти, но не говорят, сколько она записей должна вмещать…

В общем мне сама формулировка вообще не нравится, а связаться с авторами конкурса вообще нельзя по-человечески.

Это утверждение неверно. Быстрая сортировка (а) имеет сложность O(n log n), а не (какое-то там) T(n log n), и, что важнее (б) «самая быстрая» только для общего случая (в частности, для целых чисел есть сортировки O(n+r), где r — диапазон).

На самом деле «просеиванье» тоже можно назвать «сортировкой», тут я согласен.
Для меня, как для разработчика, важнее всего скорость и объем оперативной памяти с которой будет выполняться алгоритм.

Ну так ровно для этого O-нотация и нужна — чтобы получить оценки скорости и объема памяти. А потом вам поможет только профилирование.


Я не увидел в контексте этой задачи, что необходимо сделать собственную структуру данных.

Там прямым текстом написано: "реализовать структуру, выполняющую два вида запросов". И это, кстати, очень узнаваемая формулировка, если вы читали или слушали Седжвика.


На самом деле «просеиванье» тоже можно назвать «сортировкой», тут я согласен.

Нет, нельзя назвать. Так что я не понимаю, с чем вы согласны.

Нет, нельзя назвать. Так что я не понимаю, с чем вы согласны.

Это почему нельзя?
Мы получаем упорядоченную структуру, в которой точно будет сохранен факт наличия данных в изначальным множестве. По факту это усеченная counting sort или сортировка подсчетом.
Мы получаем упорядоченную структуру

А вы в ней храните m флагов или n?

Да, признаю. Сейчас это алгоритм изменился в угоду быстродейственности и объему памяти в рамках задачи MEX. Изначально я находит максимально число в массиве и сам boolean-массив был длинной равный максимальному числу из множества. И мы как раз получали возможность узнать пустые значения на всем диапазоне изначального множества.
В процессе споров в комментариях я оптимизировал выборку первого элемента, сделал массив длинной с изначально множество, а значения больше это длинны игнорировал. Чем по факту “сломал” его переиспользования для поиска “второго” пустого значения. Тут я признаю, что поддался на уговоры.
Так что в целом справедливы оба решения. Если нам нужно выбрать только одно число mex из случайного множества, то текущий код в статье оптимальный. Если мы хотим переиспользовать полученный boolean-массив, то нужно вернуть вариант, где изначально ищется max на исходном множестве.

И, кстати, к разговору об O, мне здесь упорно доказали, что в данном случае операция поиска MAX, просеиванье и поиска по просеянным данным – это O(n). Что хоть и правильно с точки зрения теории, но мне в корне не нравится для оценки реальной бытродейственности.
Что хоть и правильно с точки зрения теории, но мне в корне не нравится для оценки реальной бытродейственности.

Оно, конечно, может вам не нравиться, но если внимательно посмотреть, у вас выбор не между разными O(n), у вас выбор между логарифмическим, линейным, линейным от другого порядка, O(n log n). Вот когда между ними выбор сделан, тогда уже можно на коэффициенты смотреть.

Нет, нельзя назвать. Так что я не понимаю, с чем вы согласны.

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

Сама по себе задача MEX банальна. Гораздо интереснее задача Ozon-MEX, которая включает в себя шифрование. Будем решать Ozon-MEX.
Алгоритм 1. Пусть обновился ключ шифрования и он равен x. Обратим внимание, что при шифровании пользователь с id=x принимает новый id, равный 0, а в более общем случае заметим, что если у пользователей ряд старших бит совпадает со старшими битами ключа, то новый id будет близок к 0.
Это все ведет к идее алгоритма поиска отсутствующих id пользователей, близких к текущему ключу x. Так как ключ на практике намного короче id (занимает O(k) памяти, k<<n). Для примера k=32, n=300 000 000 (русскоговорящее население планеты).
Делаем перебор в лоб, начиная со значения ключа x. Если пользователь id=x существует, то изменяем младшие биты. И так далее. Перебор в лоб имеет сложность O(2^k) по быстродействию и O(1) по памяти. С ключом длиннее примерно 32-бит алгоритм проигрывает по быстродействию алгоритму «просеивания» по быстродействию, но не по памяти.

Алгоритм 2. Мы понимаем, что ключ шифрования меняется гораздо реже, чем регистрируются пользователи. Следовательно, образуются частично упорядоченные наборы id, которые впоследствии «разрушаются» новым ключом шифрования.
Мы хотим иметь ключ длиной 512 бит, но при этом не перебирать 2^512 вариантов. Мы можем сохранить в памяти диапазоны id и сохранить старый ключ (компрометировать его). В принципе это нормально, но тогда важно генерировать новые ключи случайным генератором.
Допустим, выдали пул id от 0 до 10000, ключ был x=x1. Пришел запрос на шифрование новым ключом — сохраняем значения [0, 10000, x1], принимаем новый ключ x2, который пока нельзя компрометировать.
Зная предыдущие наборы [0, max1, x1], [0, max2, x2],… и текущий ключ x, можно находить «пустоты» намного быстрее, чем в алгоритме 1. Начало диапазона всегда 0, поэтому, в принципе, можно не сохранять в памяти.
Сам алгоритм заключается в том, чтобы не перебирать все комбинации как это делается в алгоритме 1. Оставляю возможность сформулировать алгоритм кому-то другому, мне дальше неинтересно.

Добрый день, @RussianDragon!
Правильных решений в этой задаче было много. По правилам конкурса, мы выбирали одно самое оригинальное. Победителем и обладателем суперприза стал участник с наиболее оптимальным и оригинальным кодом.
Вы, к сожалению, не так поняли задачу. Требовалось подготовить структуру, которая будет эффективно отвечать на все запросы участников. Учитывая, что запросов очень много, ваше решение на каждый запрос будет делать одни и те же действия. Одним из оптимальных решений может быть trie (Бор в русскоязычной литературе) —  структура для строк, которая позволяет нам добавлять строки за их длину. Давайте хранить все числа в двоичном виде trie, тогда добавление будет работать за O(log(n)), где n — максимальное число в структуре. Операцию же шифрования можно реализовать за O(1), так как a xor b xor c = a xor (b xor c). Теперь насчет операции нахождения mex. Его можно также найти за O(log(n)) просто спускаясь по бору и идя в нужную ветку (вы проверяете, чему равен этот бит в кодировании и если он 0 — идете в меньшие числа, иначе — в большие). Итого это решение уже работает за N*log(max).
Ваше же решение в любом случае будет работать за O(N * N), что гораздо дольше. Это решение уже почти оптимально, но так как его написали достаточно много участников, мы также смотрели на более быстрые и оригинальные.

Вы, к сожалению, не так поняли задачу.

Верю.
Но вы дали ограничение по скорости и по памяти, но не сказали объем данных, хотя бы примерно. 10, 20, 100, 1000 или 1 000 000 000. Тогда можно было бы хоть как-то тестировать свой алгоритм по условиям задачи, а учитывая, что подача всего одна узнать, что конкретно от меня хотят — целая проблема. Хотя бы дали файлик с записями и сказали — вот «ребята» txt с изначальными данными — выкручиваетесь. А может вам хватило бы рандомной генерации данных (без повторений)… В обще и целом стартовые данные — туманы.

Ваше же решение в любом случае будет работать за O(N * N), что гораздо дольше.

Да. я там вообще много «косяков» наделал. Начиная с того, что бегал одним блоком по массиву данных. Здесь вариант просеивания гораздо эффективней, чем был раньше. Но хоть в прошлый раз, хоть в этот, я дошел до решения своими размышлениями. И если бы было бы чуть больше информации объеме данных, я думаю, задачку бы сделал иначе.
вы дали ограничение по скорости и по памяти, но не сказали объем данных

Почему вы с таким упорством отрицаете O-нотацию? Вам уже десятки людей на неё указали, даже авторы задачи.

Там, где условие задачи неполное — надо его самостоятельно дополнять. Что мы знаем из условия? Что «Озон» хочет реализовать это решение для базы своих пользователей. Много ли пользователей у «Озона»? Наверное много, это большая фирма. Настолько ли много, что вся база не помещается в ОЗУ? Это вряд ли, так как такие задачи редко дают в качестве тестовых. В тестовых заданиях обычно идёт упор на академические знания.

А академические знания — это асимптотика и O-нотация.

И вот, в чём заключается её сила. Если алгоритмы O(n) могут отличаться друг от друга по скорости в разы или даже десятки раз — то O(n) от O(n^2) будет при больших n отличаться в тысячи, миллионы и миллиарды раз. Например, если при некотором большом n разные алгоритмы со сложностью O(n) выполняются 1, 5 и 10 минут каждый, то очень вероятно, что даже вылизанный и оптимизированный O(n^2) алгоритм будет работать неделями или месяцами. Здесь огромная разница, и «копейки» можно не считать.

Всегда можно найти такое n, что, начиная с него, любой наперёд заданный алгоритм O(n) будет работать быстрее, чем O(n^2).
Там, где условие задачи неполное — надо его самостоятельно дополнять. Что мы знаем из условия? Что «Озон» хочет реализовать это решение для базы своих пользователей. Много ли пользователей у «Озона»? Наверное много, это большая фирма. Настолько ли много, что вся база не помещается в ОЗУ? Это вряд ли, так как такие задачи редко дают в качестве тестовых. В тестовых заданиях обычно идёт упор на академические знания.

Там есть ограничение 256 мегабайт. т.е. 268 435 456 — байт… В int 4 байта, т.е. мы получаем число 67 108 864 пользователей забивают всю память.
67 108 864 — Это много или мало? И это я не учитываю еще «накладные расходы» C#…

А дальше мне начинают утверждать, что из задачи «предельно ясно», что нам нужна «древовидная структура» которая хранит «сколько там» еще ссылок… Ну допустим у каждого элемента по два предка. Т.е. так как минимум нужно хранить сам объект и две ссылки — 67 108 864 / 3. Ой уже 22 369 621… А нам еще нужно выполнять операции на этой структуре данных, да еще и за две секунды… Причем мы не знаем, порядок и частоту операций. Какая операция чаще проходит, какая нет. Может нам стоит использовать какой промежуточный кеш? Или вы конкретную хотите увидеть реализацию, тогда нужно говорить — сделайте «как мы хотим», но как хотим — не скажем. Т.е. от авторов решений просят тыкнуть пальцем в небо — может и угадают, что хотят авторы задачи.

А говорить — «наиболее оригинальное» решение — а кто оценивает оригинальность и по каким критериям? Быстродейственноть, количество строк кода, знание нетривиальных конструкций языка?

Где тут хоть какая-то ясность об условиях функционирования и оценки?

Вообще, если структуру хранить в массиве (дерево отрезков), то не надо никаких ссылок. Просто 2n ячеек для n элементов. У i-ой ячейки дети 2*i и 2*i+1. А если учесть, что тут еще можно и битовыми значениями обойтись, то достаточно 2n/8 байт памяти. Уже 1 миллиард какбы влезает. Понятно, что надо еще память на код, стек и все подряд выделить, так что по факту всего 512 миллионов пользователей можно легко в такой структуре поддерживать.


А если разменять время работы на память, то можно использовать дерево Фенвика и там надо ровно n битов для хранения n элементов. И работать будет всего-то в пару раз медленнее. Уже миллиард влез.


И все операции добавления и проверки за O(log n).

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

@RussianDragon, в нашем случае нужна была структура, которая постоянно отвечает на запросы за наилучшую асимптотику. Поэтому количество данных неважно. Мы всегда готовы ответить на дополнительные вопросы и прояснить условия. В следующий раз, если вам что-то будет непонятно, напишите нам. Победителем этого конкурса стал участник, который предложил оптимальное и самое оригинальное решение и продумал все нюансы.   

gektor2510, я тут понял, что Вам вообще MEX не уперся по своей сути согласно постановки задачи.
Еще раз, Вы хотите:
1) Зарегистрировать нового пользователя,
2) Защифровать все текущие данные с помощью нового ключа x

Тогда вот вам код, который будет выполнять вашу задачу.

class Item
    {
        public uint Id { get; set; }
        public Item Next { get; set; }
    }

    class Program
    {
        static Item First { get; set; }
        static Item Last { get; set; }
        static uint CountUsers { get; set; } = 0;
        static uint AcumHash { get; set; } = 0;
        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("Выбирите действие");
                Console.WriteLine("1 - Добавить новго пользователя");
                Console.WriteLine("2 - Зашифровать данные");
                Console.WriteLine("3 - выйти");
                string comand = Console.ReadLine();
                switch (comand)
                {
                    case "1":
                        AddUser();
                        break;
                    case "2":
                        while (true)
                        {
                            try
                            {
                                Console.WriteLine("Введите ключ (неотрицательное число)");
                                uint key = uint.Parse(Console.ReadLine());
                                HashingUsers(key);
                                break;
                            }
                            catch (Exception)
                            {
                               Console.WriteLine("Ошибка ввода");
                            }
                        }
                        break;
                    case "3":
                        return;
                    default:
                        Console.WriteLine("Ошибка ввода");
                        break;
                }
                PrintUsers();
            }
        }

        private static void AddUser()
        {
            var newItem = new Item()
            {
                Id = (CountUsers ^ AcumHash)
            };
            CountUsers++;
            if (First == null)
            {
                Last = First = newItem;
                return;
            }
            Last = Last.Next = newItem;
        }

        private static void HashingUsers(uint hash)
        {
            AcumHash ^= hash;
            var link = First;
            while (link != null)
            {
                link.Id ^= hash;
                link = link.Next;
            }
        }

        private static void PrintUsers()
        {
            var link = First;
            while (link != null)
            {
                Console.Write($"{link.Id}, ");
                link = link.Next;
            }
            Console.WriteLine();
        }
    }


Мы вставляем записи с 0 в односвязный список O(1).
Мы производим шифрование данных O(n)
Задача решена с минимум памяти (Без оптимизации на двоичном уровне.)
Искать MEX вообще не нужно, т.к. благодаря тому, что мы храним аккумулированный хеш, каждая новая вставка будет уже с учетом того, что подобного индекса точно нет в базе (а именно этого вы и пытаетесь добиться). Выйти за пределы uint мы тоже не можем, т.к. операции битовые.

Всё — задача решена. И зачем вы столько времени посветили описанию MEX, если вам нужно просто вставить значение в базу с уникальным ключом?

lair, wataru, MichaelBorisov или хотите сказать, что я опять неправильно понял задачу?

Да, вы опять неправильно поняли задачу. В задаче прямым текстом написано: новые пользователи получают минимальный id из возможных.

А зачем? Если мы так имеем разбросанные id-шники, то зачем нам при вставке нового пользователя брать минимальный? Более того, взятие минимального id — это в примере, а не в условии. В условии — взять id которого нет в базе.
— Говорю — авторы сами намудрили решением простой задачи, а потом попросили пользователей тыкнуть пальцем в небо и написать решение которое будет похоже на их мудрёное, которое не отражает суть изначально поставленной задачи.
А зачем?

По условиям задачи. Это задача на алгоритмы и структуры данных, там "зачем" не всегда применимо.


(хотя я могу придумать как минимум вариант "замедление роста длины идентификатора").


Если бы нужно было только уникальные идентификаторы, давно есть UUID.


Более того, взятие минимального id — это в примере, а не в условии. В условии — взять id которого нет в базе.

Это неправда.


Ладно, признаю. Натянули они Сову на глобус в условиях задачи. )
Да и фиг с ними.)

@RussianDragon, вы были бы правы, если бы по условиям задачи не нужно было находить mex. Это было прописано. Плюс, как отметил @lair, есть и другие известные способы решения такой задачи

Более общий алгоритм для мех:


Исходные данные: массив неотрицательных чисел, повторения разрешены, длина N.
Очевидно, что мех лежит в интервале [0;N].
Отсюда очевидно, что числа >N можно просто выкинуть.


Выполним сортировку-и-уникальность.


Мы знаем, что все числа лежат в [0;N].
Поэтому делаем так:
Пусть голова массива a[0..k) уже упорядочена: a[i]=i
Смотрим на a[k]=m.
Если m>=N, то это число, которое надо проигнорировать. обменяем a[k] <-> a[N-1] и сократим массив: N--.
Если k<m<N, то это число должно лежать в a[m];


  • если a[m]==m, то это копия, которую надо будет выкинуть: обменяем a[m] <-> a[N-1] и сократим массив: N--; будем повторять до тех пор, пока a[m] != m
  • обменяем a[k] <-> a[m]
    И будем так делать до тех пор, пока a[k] <= k.
    Если m==k, то это число на своём месте, идём дальше: k++.
    Если m<k, то это вакансия. То есть, k — MEX. Конец.

Если мы дошли до конца, k==N, то k — MEX.


Линейное время, константная память.

Автору поста рекомендую почитать про структуру данных BitTrie (Префиксное дерево).
Используя эту структуру для хранения id-шников, можно реализовать функцию вставки нового пользователя со сложностью O(logN), а ключ шифрования хранить в отдельной переменной и обновлять его простым xor-ом, типа oldKey ^= newKey.
Для хранения пользователей можно вообще односвязанный список использовать в контексте задачи. Так то вставка — O(1). Ключ шифрования вообще не нужно где-то хранить, о приходит как значение введенное в консоли и обновляет id записей.

Задача вообще про другое, для меня это задача поиска MEX на несортированном множестве.

Автору поста рекомендую почитать про структуру данных BitTrie (Префиксное дерево).

В целом, всё имеет право на жизнь… По крайней мере я увидел, что задача от OZON сформирована так криво, что каждый решил её по-своему…
Я здесь увидел только задачу поиска MEX на не сортированном массиве, кто-то решил, полностью поменять структурe данных. Кстати это не всегда возможно, если данных в базе излишне много. В общем и целом, хоть статью и заминуси, в первые в жизни для меня, это была интересная задачка и интересные мнения.
Для хранения пользователей можно вообще односвязанный список использовать в контексте задачи. Так то вставка — O(1).

O(N), потому что у вас вставка (по условиям задачи) должна возвращать новый идентификатор, а вы его находите за линейное время.


Задача вообще про другое, для меня это задача поиска MEX на несортированном множестве.

Вот в том-то и дело, что вы решаете задачу, которую решать не надо, а потом удивляетесь, что ваше решение не приняли. Выше уже есть ответ человека, ассоциированного с Озоном, который подтверждает мое мнение.

O(N), потому что у вас вставка (по условиям задачи) должна возвращать новый идентификатор, а вы его находите за линейное время.

Необязательно. Мне достаточно один раз «просеять» данные выкинуть всё, что является 1-цами и получить массив «свободных» чисел. И до следующей операции шифрования.
А в случае «сортировки MEX» поиск каждого нового свободного числа будет быстрее, т.к. массив частично сохраняет отсортированную структуру. А если еще сохранить максимальное число после прохода и потом сравнивать его с длинной массива, то мы точно будем знать, что нужно брать вообще новое число, а не искать свободное.
Эти варианты – не конечные с точки зрения оптимизации.

Вот в том-то и дело, что вы решаете задачу, которую решать не надо, а потом удивляетесь, что ваше решение не приняли. Выше уже есть ответ человека, ассоциированного с Озоном, который подтверждает мое мнение.

Да, уже прочел. Ну, уж как понял задачу, так и сделал.
Необязательно. Мне достаточно один раз «просеять» данные выкинуть всё, что является 1-цами и получить массив «свободных» чисел.

Ну вот вы и сделали свою структуру данных.


Да, подумайте о ее эффективности (по памяти особенно) для случая, когда у вас есть два числа: 1 и int.Max-1.


И до следующей операции шифрования.

Вот в ней-то и проблема. Она не зря есть в условиях задачи. У вас может получиться, что операции идут подряд: вставка, шифрование, вставка, шифрование, и так далее. Оценивать алгоритм надо и для этого случая тоже.


И не забывать для всех случаев еще и объем памяти оценивать.

У вас может получиться, что операции идут подряд: вставка, шифрование, вставка, шифрование, и так далее.

Вот непонятно как они идут. Задача сформулирована криво и очень размыто. Что чаще происходит — «шифрование» или «вставка». Или мы шифруем после каждой вставки. Или только вставки 1 000 000 записей решили «шифрануть».
И от это всего будет зависит и структура данных и способ поиска. А говорить — «наиболее оригинальное» решение — а кто оценивает оригинальность и по каким критериям? Быстродейственноть, количество строк кода, знание нетривиальных конструкций языка?
Без нормально ТЗ — результат ХЗ.

При этом нет даже банальной возможности спросить или хоть каких-то автоматических тестов — которые сказали бы «что-то не так».

И утверждать, что спустя три месяца после окончания конкурса чуть более подробную формулировку — это странно.
В тексте задачи в основном описывалась, что такое MEX, на это делался огромный уклон. Т.е. фактически самое главное — быстро находить MEX… А задача «шифрования» и «вставки» просто второстепенные, что бы проверить как эффективно работает MEX «без историчности».
Вот непонятно как они идут.

Ну так надо оценить, какая последовательность как будет влиять.


А то знаете ли, (некоторые) алгоритмы сортировки тоже зависят от того, какие данные на входе, но это не мешает их анализировать.


В тексте задачи в основном описывалась, что такое MEX, на это делался огромный уклон. Т.е. фактически самое главное — быстро находить MEX… А задача «шифрования» и «вставки» просто второстепенные, что бы проверить как эффективно работает MEX «без историчности».

Я боюсь, это вы себе додумали, что тут самое быстрое.

Ну так надо оценить, какая последовательность как будет влиять.

А то знаете ли, (некоторые) алгоритмы сортировки тоже зависят от того, какие данные на входе, но это не мешает их анализировать.

Что-то я уже сбился о чем спор…
Я говорю, в рамках того, что через три месяца авторы дали чуть больше данных об условиях задачи — это не означает, что изначально задача сформулирована «понятным языком».
Собственно Вы сами говорите, что разные алгоритмы могут совершенно по разному работать в зависимости от условий. И тут я полностью согласен. Поэтому нужно описать условия в которых они будут проверяться.

А не говорить потом, что мы не в таких условия проверяли… И я не против сделать иное решение, если на то пошло. Я не доказываю, что мое решение — идеальное для всех случаев жизни. Более того я сам прекрасно понимаю, где и как его оптимизировать в зависимости от условий в которых оно будет.
Я говорю, в рамках того, что через три месяца авторы дали чуть больше данных об условиях задачи — это не означает, что изначально задача сформулирована «понятным языком».

Для вас она оказалась непонятной, да. Для кого-то другого, кто предложил префиксное дерево — оказалась более понятной. Так бывает.


Это все, тем не менее, скажем, не повод отрицать О-нотацию, как вы упорно делаете.

Пусть Id 8-байтный, а пользователей меньше 4 миллиардов.

Среди Id с нулевыми байтами 4-7 найти пару байт 2, 3, встречающуюся меньше 2^16 раз. Пусть это пара XY.

Среди Id с байтами 2-7, равными 0000XY, найти не встречающуюся пару байт 0, 1.

Два прохода по списку Id и 4*2^16 = 256 kB дополнительной памяти.

Sign up to leave a comment.

Articles