Задать вопрос
wataru

Wataru

Разработчик на С++, экс-олимпиадник.
Ответы пользователя по тегу Алгоритмы

  • Как называется это свойство набора кодов (словаря)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Нету у этого свойства никакого имени. Вы его слишком обобщили. Свойство - определенные символы не могут идти в начале слова. Вот и все.
    Ответ написан
    Комментировать
    Комментировать

  • Как устроено окто дерево? Как происходит отсечение видимых грайней?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вернуть все данные в узле. это же самое что дальше продолжать обходить все внутренние рекурсией или стеком узлы, и составить список. В чем профит то тогда? Как можно вернуть все данные по щелчку.


    Да, именно так, надо обойти все узлы дальне.
    Но при этом уже не надо проверять на видимость и код там попроще.

    А профит тут в том, что вы вот так вот обходите не все дерево. а только маленькую его часть.

    Окто дерево используется, чтобы отсечь те объекты, которые сзади или сбоку от камеры и точно не видны. Оно не помогает отсекать объекты, закрытые стеной. Тут, действительно, используется z-buffer.
    Ответ написан
    4 комментария
    4 комментария

  • Как разбить треугольник в прямоугольной области на N треугольников?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    mayton2019 правильно вам сказал: сначала пересеките треугольник и ваш прямоугольник. А потом триангулируйте.

    При пересечении у вас 2 выпуклых многоугольника. Алгоритм Сазерленда-Коэна тут немного перебор, ибо там один из многоугольников может быть не выпуклым. В вашем фиксированном случае скорее всего нет даже смысла заморачиваться с O(n log n) алгоритмом. Просто научитесь пересекать любые 2 отрезка. После чего пересеките каждую сторону треугольника с каждой стороной квадрата. Не надо считать за пересечение, если 2 отрезка параллельны и накладываются. Получите макимум 12 точек. К ним добавьте 3+4=7 вершины ваших многоугольников. Потом каждую точку проверьте на принадлежность обоим фигурам, и оставьте только те, которые лежат внутри или на границе. Потом постройте выпуклую оболочку из них (погуглите, эта-то задача вообще везде расписана).

    Что касается триангуляции, то у вас там получится выпуклый многоугольник. Так что можно, например, провести все хорды из одной вершины. Если же вам нужна какая-то особо "хорошая" триангуляция, то гуглите "Триангуляция Делоне". Этот алгоритм не строит очень приплюснутых треугольников, где это возможно.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоритм приближенного решения Задачи Комивояжера выбрать для регулярных точек?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Раз человек легко прокладывает путь, то его можно просто захардкодить.

    Очевидно, что шаг от одной вершины к следующей будет не меньше 1, а значит кратчайший путь - тот, который ходит только горизонтально и вертикально. Если сетка не квадратная, то пусть ровно с 2m более длинных вертикаьных ребер будет мнимальным, потому что путь любую горизонтальнюу линию должен будет пересечь хотя бы в 2 точках.

    Ну и нарисуйте на бумаге 4 случая - когда высота и ширина четные или нечетные.
    Ответ написан
    Комментировать
    Комментировать

  • Когда целесообразно использовать именно такую реализацию DSU?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    DSU выполняет две операции: проверить, принадлежат ли 2 элемента одному множеству; объеденить множества двух данных элементов. Обе за O(log*n) ассимтотически. Это не логарифм, а суперлогарифм, или обратная функция Аккермана. Это - сколько нужно двоек сложить в степенную башню, чтобы набрать n. Она растет так медленно, что ее можно считать константой на практике (она достигнет 4 только при n=2^65536 - вы столько числел не сохраните во всех датацентрах мира).

    Я бы в качестве альтернативной, "тривиальной" реализации рассматривал массив пометок + списки в массиве:
    для каждого элемента храним номер его множества, а для каждого номера храним список всех его элементов в списках (так же, как и в DSU, в одном массиве ссылок на следующий элемент).

    Эта структура компактна по памяти и более быстра, чем ваши хеш таблицы. Тут можно за O(1) проверить, что два числа в одном множестве и за O(log n) объеденить два множества (амортизированно, если перекрашиваем меньшее множество).

    Итак, имеем O(Log*n) vs O(1) за проверку и O(log*n) vs O(log n) за объединения.

    Т.е. вроде бы имеет смысл использовать пометки+списки, если у вас заметно больше проверок, чем объединений.

    Но на практике там выигрыша нет, ибо редко когда у вас сильно больше проверок. Да и, если у вас много проверок, то оценка O(log*n) - завышена, ведь если вы одну и ту же проверку повторяете, то там пути сжимаются и проверки работают уже за O(1).

    Таким образом, DSU от Тарьяна - лучше всех других структур на практике.
    Ответ написан
    7 комментариев
    7 комментариев

  • Как найти количество помеченных связных графов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Формула включения-исключения. Берете все графы, где хотя бы одна вершина соединена со всеми (их n*2^(n-2)*(n-1)), вычитаете все графы, где хотя бы две вершины соеденины со всеми (2 раза, ведь они 2 раза подсчитались), прибавляете графы, где хотя бы 3 вершины соеденины со всеми (3 раза)... И т.д.

    Графов, где хотя бы k вершин имеют степень n-1 - C(n, k)*2^{(n-k-1)(n-k)/2}: тут можно выбрать k вершин и для каждого ребра из оставшихся n-k вершин есть 2 варианта - оно или есть, или нет.

    Это будет за O(n log n) решение, если пердподсчитать все факториалы и обратные к им по модулю в задаче. Ну, или O(n^2), если считать сочетания через треугольник паскаля.

    Ражеванное объяснение:

    Сложно подсчитать количество графов где ровно 1 вершина такая полная. Но легко подсчитать те, где k или более таких. Мы их такие зафиксируем и нарисуем от них все ребра. А все оставшиеся ребра в графе могут быть любыми. Во-первых, можно выбрать эти k вершин - поэтому у нас есть множитель C[n,k]. Оставшиеся, незафиксированные ребра идут между любыми двумя оставшимся n-k вершин. Их (n-k)(n-k-1)/2. И каждое может быть или проведено или нет.

    Поэтому всего таких графов, с не менее k вершин: F(k)=C[n,k]*2^{(n-k)(n-k-1)/2}.

    Теперь, как подсчитать графы ровно с 1 вершиной? Можно взять F(1). Но мы насчитали много лишнего, Графы с 2мя такими вершинами мы в F(1) подсчитали 2 раза. Поэтому вычтем 2F(2). Теперь графы ровно с 3 вершинами мы подсчитали 3 раза в F(1) и 3 раза в каждом F(2). Поэтому пока мы их насчитали 3-2*3 = -3 раза. Поэтому прибавим 3F(3). И далее, получится, что графы ровно с 4-мя вершинами мы подсчитали 4 раза (4-2*6+3*4). И т.д.
    Ответ написан
    6 комментариев
    6 комментариев

  • Какой правильный класс коллекции для хранения сортируемого списка?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Достаточно списка. При принудительном обновлении берите первый элемент из списка. При любом обновлении перемещайте объект(ы) в конец. Можно перед началом из списка элемент удалить, а после конца в конце вернуть.

    Тут вам еще понадобится какая-то структура, чтобы по объекту получить итератор на него в списке. Если у вас объекты каким-то id определяются, то это может быть 
    std::unordered_map<int, std::list<Object>::iterator>
    .

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

    А вообще, есть и Lock-free списки. Если у вас обновления сами по себе очень быстрые операции, то такая структура может быть в итоге работать быстрее.

    Edit: простите за C++-ый код. Не заметил, что вопрос с java тегом. В общем, тут нужны какой-то список и hashmap из id в итераторы в этом листе.
    Ответ написан
    1 комментарий
    1 комментарий

  • Можно ли сравнить большие массивы по частям?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно и по частям. Какой там алгоритм сравнения, если все сразу известно? Два указателя, по одному в каждом массиве. Выкидываем меньшее число из двух - оно уникальное в своем массиве. Если два числа равны - вы нашли совпадение и двигайте оба.

    Можно алгоритм поставить "на паузу". Вам надо будет хранить указатель в первом массиве между порциями второго.
    Когда у вас приходят данные от второго массива, двигайте указатель в первом, пока число там меньше текущего во втором массиве. Если они равны, двигайте оба. Если число в первом больше - дивгайте указатель во втором массиве. И так пока один из массивов не кончится.

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

  • Как найти решение для задачи?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Rsa97 правильно написал про геометрический смысл. Но есть более быстрое решение за O(n log n), использующее метод заметающей прямой.

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

    Если числа в задаче большие или нецелые, то сначала через бинпоиск или хешмап замените все координаты по X и по Y на их порядковый номер в отсортированном массиве (отдельно по каждой оси). Эта операция называется "сжатие координат". Теперь у вас все координаты целые числа от 0 до 2*n.

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

    Для этого каждый прямоугольник (X1, Y1, X2, Y2) создаст 2 события "открылся отрезок с Y1 до Y2 во время X1" и "закрылся отрезок с Y1 до Y2 во время X2". Эти все события вы сортируете по X и в таком порядке обрабатываете.

    Для отслеживания состояния прямой используйте дерево отрезков на минимум с отложенной суммой. Эта структура данных потребует массив на примерно 4n элементов для дерева с 2n листами. Каждая вершина будет хранить минимум на соответсвующем ей отрезке. При открытии прямоугольника вы должны добавить +1 на его отрезок. При закрытии - вычесть 1. Сначала открывайте прямоугольники, если время у событий одинаковое. Учитывайте это при сортировке. Так касающиеся по вертикали прямоугольники не создадут пустых мест.
    Если после обработки какого-либо события вы получили минимум в дереве отрезков 0 и следующее событие имеет большую координату по X - то какая-то часть оказалась не покрыта. Еще есть случай, если первое событие не X1=левая граница покрываемого прямоугольника, или последнее событие - не X2=правая граница всего прямоугольника. Тут тоже покрытия нет.

    Еще, аккуратно с целыми числами, чтобы если у вас 2 прямоугольника касаются горизонтальными сторонами - там пустое место не подсчиталось. Например, каждый лист дерева отвечает за единичный отрезок координат. Тогда изменяйте в дереве всегда отрезок от Y1 до Y2-1 для события с координатам Y1..Y2.
    Ответ написан
    7 комментариев
    7 комментариев

  • Каким алгоритмом воспользоваться для поиска вхождений диапазона чисел в другой диапазон?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Самое быстрое решение - с использованием двумерных структур данных, вроде двумерного дерева отрезков.

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

  • Можно ли так доказывать правильность алгоритмов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если их нельзя переворачивать и при равенстве высот все-равно можно вложить (а не только строго меньшее), ио алгоритм правильный. Но доказательство не полное. Надо доказать, что любая неубывающая последовательность в этом массиве даст веладывающиеся прямоугольники.
    Ответ написан
    7 комментариев
    7 комментариев

  • Что подразумевается под поиском двух линий при создании контейнера?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    У вас есть куча вертикальных столбиков с заданными высотами. Вам надо взять 2 столбика так, чтобы между ними было больше всего воды. Они образуют загогулину вроде |____| - это и есть контейнер, в котором может быть вода (если мир двумерный). Например если в примере взять самый левый (1) и самый правый (7) столбики, то высота воды будет 1 (иначе она слева выльется), а ширина будет 8 - итого получается 1*8=8 единиц воды.

    Формально, вам надо найти такие i<j, что min(h[i],h[j])*(j-i) максимально.
    Ответ написан
    2 комментария
    2 комментария

  • Преобразование шрифта?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Этот текст - это символы Unicode.

    Например, "б" в слове "большое" - это символ 0x0431

    Проблема в том, что там символы не из одного алфавита, а полная солянка. На этом сайте можно получить коды всех символов: https://www.rapidtables.com/convert/number/ascii-t...
    Получите: 
    1D04 1D00 28D 43E 1D07 20 431 43E 1D27 44C 26F 43E 1D07 20 28D 43E 1D29 1D07


    Как видите, они все разбросаны довольно сильно. 1D** - Phonetic Extensions . 04** - Cyrillic, 02** - IPA Extensions

    Символы из разных алфавитов подобраны по внешней похожести на нужные буквы (как Ш - это перевернутая m вообще). Наверно, какой-то онлайнг конвертер вроде этого где-то имеет набор из 33 кодов и подставляет их вместо русских букв. Не знаю, есть ли такой обратный.

    Можно написать обратный конвертер на том же питоне, только надо руками сопоставить каждому символу из текста нужный символ из обычного ascii. Например, заведите солварь (вам надо руками все встречающиеся символы в исходной строке туда добавить):
    convert = {'ᴀ': 'а', ... 'ʍ':'м', ...}

    Потом примените его ко всем символам в вашей строке каким-нибудь map().
    Ответ написан
    Комментировать
    Комментировать

  • Адрес сайта с нормальными гайдами по алгоритмам?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Есть русский сайт e-maxx.ru/algo
    Есть сборник кучи алгоритмов, но там мало объяснений: https://rosettacode.org/wiki/Rosetta_Code
    Ответ написан
    2 комментария
    2 комментария

  • Алгоритм поиска маршрута?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В питоне есть библиотека для работы с графами NetworkX. И там есть уже реализованные алгоритмы кратчайших путей.

    Это будет быстрее, чем самостаятельно реализовывать какой-нибудь алгоритм Дейкстры или обход в ширину, ибо питон - безбожно тормознутый язык. А в библиотеке вычисления обычно реализованы на более быстрых языках.
    Ответ написан
    1 комментарий
    1 комментарий

  • Какой самый быстрый способ найти позицию последовательности 0-bit заданной длины в int[]?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Зависит от длины n. Если n маленькое то можно прикладывать маску. Байт x содержит 3 ноля в последних битах, если ~x &0x7 == 0x7. Аналогично, сдвигая маску из трех единиц (0x7) можно приложить ко всем позициям.

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

    Потом, можно еще распараллелить поиск в несколько потоков. Каждый поток ищет последовательность, начинающаюся в отдельном куске массива.
    Ответ написан
    Комментировать
    Комментировать

  • В чем заключается суть бинарного поиска неотсортированного массива?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ну ведь тут массив же отсортирован. Хоть и с приколом: он сдвинут. Можно тем же бинарным поиском найти, где там "разрыв" происходит, а после у вас 2 отсортированных куска. Или сразу модифицировать бинпоиск.
    Представьте, что у вас массив, где сначала идут 1, а потом 0. Можете найти в нем, где 1 переходит в 0?

    Или смотрите так: ищите вы x. Взяли значение a[m]. Можете, посмотрев на a[l], a[m], a[r] и x понять, в какой половине лежит x?

    Edit: ах, тут числа могут быть одинаковыми. Тогда бинпоиск тут не работает. Ибо может быть тест {1,1,1,2,1,1} - и тут можно 2 в любую позицию поставить. И, если вам надо эту 2 найти, то вам придется просмотреть все числа, иначе вы ее не найдете. Бинпоиск возможен, если первое и последнее числа разные.
    Ответ написан
    3 комментария
    3 комментария

  • Как на udp сервере подсчитать one-way latency и верменной offset клиента?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Надо клиенту в пакете отправлять время получения и отправления в пакете.

    В итоге сервер получит 4 таймстампа: сервер отправил, клиент получил, клиент отправил, сервер получил. При этом два серверных и два клиентских - могут быть в разных часах. Поэтому надо взять t4-t1+t2-t3 - и вы получите rtt. Поделите на 2, получите оценку нужной задержки. И это надо сглаживать по многим пакетам.

    Проблема будет, если часы тикают с разной скоростью, а не просто отстают на фиксированное время. Это надо смотреть на динамику t2-t1. Если там линейная регрессия с отличным от 1 коэффициентом получается, то надо это учесть и делить на этот коэффициент t2-t3 в формуле. Но это редко делают. Если время обработки пакета клиентом мало по сравнению с сетевой задержкой, то лишь малая часть этого времени пойдет в ответ ошибкой.

    Однако, если вы часы синзронизируете, то вам надо постоянно пересчитывать отставание по последнему пакету и оценке rtt. И этот сдвиг часов будет изменятся со временем а соответствии с разной скоростью часов.
    Ответ написан
    Комментировать
    Комментировать

  • Какой структурой можно повесить lock на диапазон?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если у вас диапазоны такие маленькие, то можно прямо в классе буфера завести еще и массив mutex-ов. И каждый поток будет их лочить слева на-право по всему диапазону (важно, что каждый поток делает это в одном и том же порядке, а то дедлоки получите).

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

    Если же у вас ожидаются интервалы побольше 100, то тут возможно лучше будет вот такое решение:
    У вас будет одна глобальная структура-индекс, где вы будете хранить статус буфера (о ней позже). Потоки будут к ней обращатся и просить у нее выделить потоку кусок.
    Внутри этой структуры, похоже, придется сделать один глобальный мьютекс.
    В качестве самой структуры хорошо подойдет дерево отрезков с отложенным добавлением. Пусть оно будет считать сумму на отрезке. При запросе на выделение вы смотрите, равна ли сумма на запрошенном отрезке 0. Если да, то прибавляете на отрезке 1. Если нет, то возвращаете неудачу и поток должен будет опять обратиться к структуре. При освобождении интервала прибавляйте -1.

    Тут операция выделения сама по себе будет сильно быстрее. Но это фактически спинлок - каждый поток будет в цикле пытаться выделить себе интервал, пока не сможет. Если ожидается, что потокам придется долго ждать, то надо какие-то стратегии back-off добавлять (спать между вызовами). И вообще спинлоки - это плохо.

    Как сделать это без спинлоков с деревом отрезков - я не придумал.
    Ответ написан
    Комментировать
    Комментировать

  • Как показать зависимость скорости от O(nlogn)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно, только надо числа брать побольше. Скажем, 100000 и 1000000. Для полносты картины можно взять несколько точек. Еще возьмите, например, 5000000 и 10000000.

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