Как стать автором
Обновить
-4
Карма
0
Рейтинг

Пользователь

MEX (Minimum EXcluded) Алгоритм поиска минимального отсутствующего числа

Учитывая, что у нас дерево, то в каждом поддереве хранится число, на которое это поддерево нужно xor-нуть. И когда спускаемся, продвигаем это число в child nodes.
Правда как подсказали ребята из Озона, отложенный xor не нужен.

MEX (Minimum EXcluded) Алгоритм поиска минимального отсутствующего числа

Учитывая, что у вас фактически используется O(n) памяти, просеивание выходит лучше.

MEX (Minimum EXcluded) Алгоритм поиска минимального отсутствующего числа

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

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

MEX (Minimum EXcluded) Алгоритм поиска минимального отсутствующего числа

Задачу также можно решить за O(n*logn) времени и O(1) памяти с помощью двоичного поиска без сортировки. Для этого воспользуемся тем, что все элементы в множестве уникальны. Поэтому мы можем просто взять и за один проход подсчитать количество элементов, меньших или равных k. Если это количество меньше k, значит MEX <= k.

Если у вас нет плюсов

auto start = now();
sleep(a);
sleep(b);
return now() - start;

Правда, я использую аж два плюса, потому что C++

Идеальная избирательная система

>простыми гражданами, радеющих за принципы сменяемости власти и соблюдения своих избирательных прав.

Всё же простые граждане радеют за то, чтобы им было хорошо. А обеспечивается это сменяемостью власти или её несменяемостью — это для них уже вторично.

Пользователи обнаружили, что антимайнинговая функция RTX 3060 не работает с драйвером 470.05

Только для одной, да. Если карт больше одной, то с полным хешрейтом работает только основная. twitter.com/aschilling/statuses/1371536419857047568

Разработчик 7-Zip выпустил официальный билд для Linux спустя 22 года после выхода Windows-версии

Да, неправильно выразился. На Windows нет официального или общепринятого способа — только различной степени пригодности проекты. И как правило там какой-нибудь драйвер. Для себя использовать что-то можно, а вот встраивать в приложение я бы поостерёгся.

Сами Microsoft пилят ProjFS, но там свои особенности.

Разработчик 7-Zip выпустил официальный билд для Linux спустя 22 года после выхода Windows-версии

Надо полагать, хочется как в winrar, чтобы можно было исправить испорченные блоки.

Разработчик 7-Zip выпустил официальный билд для Linux спустя 22 года после выхода Windows-версии

В Windows такое сделать практически никак. А на linux есть FUSE + loop mount.

Смотрим любое кино мгновенно

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

Что такое научное мышление?

А вы не разу не задумывались о том, что это ИДИОТИЗМ, что на практике вы этого не получите? На практике: чем тоньше у вас будет труба, тем дольше вы будите набирать ведро воды (к примеру), а по данному уравнению вы будите набирать ведро воды за одно и то же время при любом уменьшении диаметра трубы.

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

TikTok согласился сотрудничать с российскими властями

Может быть, Сбер выкупит активы TikTok в России )))

Опасные мифы о клещах

Ну так материал был написан весной 2020 года, а зима 2020 довольно тёплая была.


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

Самый беззащитный — уже не Сапсан. Всё оказалось куда хуже…

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

Китай продолжает разработку процессоров: представлен 8-ядерный ARM-чип D2000 для мощных систем

Возможно, обмен данными между ядрами?

Яндекс отключил расширения с аудиторией в 8 млн пользователей. Объясняем, почему мы пошли на такой шаг

Если бы VDH перекодировал всё в h264, я бы ещё понял, потому что его достаточно быстро кодирует и его поддерживают практически все устройства. Но я вот сейчас скачал видео в av1 и VDH попытался его перекодировать в av1 же.

Американцы не хотят сотрудничать с белорусской компанией Synesis, которая помогает МВД распознавать лица протестующих

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


Но в ЕС ввели санкции против конкретно Synesis, в связи с этим у GSDVS запросили комментарий, и отвечать иначе было бы глупо.

Яндекс отключил расширения с аудиторией в 8 млн пользователей. Объясняем, почему мы пошли на такой шаг

Если бы он ещё не добавлял свой qr-код на сконвертированное видео. Мало того, что это не слишком приятно, так ещё и для этого требуется перекодировать видео вместо того, чтобы просто слить видео и аудиопотоки.

Информация

В рейтинге
3,320-й
Зарегистрирован
Активность