Ответы пользователя по тегу Алгоритмы
  • Как сделать дерево обьектов из массива?

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

    Заведите мап объектов, которые будете собирать. Ключи будудт айдишники, а значения - объекты. У объектов заполните uid, parentUID, пустой Map children и пустой список children_list. Так же запомните куда-то id, у которого null отец.

    Потом еще одним проходом по списку всех элементов заполните children_list у всех обхектов в Map из прошлого шага (кладите текущий id в список для parentUID).

    Потом еще одним проходом по всем элементам этого Map соберите дерево: обойдите список детей и в Map children кладите 'id' => объект из внешнего Map'а по данному ключу. После прохода можно children_list удалить.

    Если я правильно понимаю, как работает JS, то у вас будет не копироваться объект а его ссылка. В итоге в Map будут осодержаться вообще все поддеревья ссылыющееся друг на друга. Можно потом вырвать оттуда объект по ключу id корня и Map удалить.
    Ответ написан
    Комментировать
  • Есть ли алгоритм разложения матрицы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Посмортите на метод Гаусса. Там получается диагональная матрица путем прибавления одной строки к другим и перестановки строк. Так вот - прибавление одной строки к другой с коэффициентом - это и есть домножение матрицы на трансвекцию.

    Единственная проблема - надо переставлять строчки местами. Тут вам поможет класический пазл о помене двух чисел без использования вспомогательных переменных:
    a = a + b;
    b = a - b;
    a = a - b;


    Эти три операции поменяют местами a и b. При чем они уже выглядят как трансвекции - только вторая операция не совсем вида a += b*k.

    Но можно чуть чуть поменять:
    a = a + b;
    b = b - a;
    a = a + b;


    Тут три трансвекции и строки меняются местами, только одна из них домножается на -1. Но это домножение метод гауса нисколько не меняет.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Обход в ширину. Сначала поместите в очередь ваши начальные точки с расстоянием 0 и пометьте эти клетки в какой-то матрице как обработанные. Потом, пока очередь не пуста, доставайте из нее одну клетку, смотрите 4 соседние клетки и, если они пока не обработаны, кладите их в конец очереди с расстоянием +1 к текущей клетке. Также всегда помечайте клетки обработанными когда помещаете их в очередь.

    Работать это будет O(nm) - быстрее никак.
    Ответ написан
    Комментировать
  • Как найти сумму чисел на нечетных позициях после сортировки массива?

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

    Edit: Если стандартная сортировка не работает и L большое, то стоит посмотреть в сторону radix sort. Если бы L было относительно небольшим - то лучший вариант был бы сортировка подсчетом.
    Ответ написан
  • Как реализовать битовую матрицу оптимально по памяти?

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

    Для матрицы NxM бит (i,j) будет лежать в (i*N+j)/8 ячейке массива. Номер бита - надо взять остаток от деления на 8.

    Можно получить любой бит и можно что угодно делать с матрицей.
    Ответ написан
    Комментировать
  • Как сменить разряды двухбайтового числа (С++)?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам нужно сделать побитовое И с маской, где стоят 0 в нужных вам разрядах (и 1 в остальных). Маску можно задавать прямо бинарной или шестнадцатеричной константой.
    Ответ написан
    Комментировать
  • Как найти все комбинации многоуровневого ассоциативного массива?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Рекурсивно. Функция должна получать уже набранный элемент и оставшиеся параметры. Она берет первый параметр и перебирает все его варианты, плюс пустой вариант (пропустить этот параметр). Добавляет это к элементу и рекурсивно запускается от оставшихся параметров с измененным элементом. Если параметров больеш нет - функция добавляет текущий ответ к результату. Правда этот алгоритм переберет еще и совсем пустой варинт []. Вам надо будет отдельно это проверить и не добавлять этот элемент в результат.
    Ответ написан
    2 комментария
  • Как хэшировать вещественные числа?

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

    Копируете в uint64_t. Если надо меньше бит, то можно домножить на большое простое число и потом взять xor младших и старших бит.
    Ответ написан
    4 комментария
  • Задачка по раскрою максимального количества коробок на листе?

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

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

    Она NP-полная - тут нет быстрых и простых решений. В общем случае, возможно только решение полным перебором за N*3^N. Что-то вроде того, что предложил Alexandroppolus, только там вообще не рассматривается случай, что текущее число просто пропускается. Еще можно делать это же без рекурсии на основе битовых масок.

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

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

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

    Т.е. вам надо найти путь из одной клетки в другую, пройдя по как можно меньшему количеству клеток. Можно ходить в 8 направлений - если пересечь угол, то можно за одну точку на ломаной перейти по диагонали.

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

    Надо только аккуратно разобрать случаи, если начальная или конечная точка лежит на границе клетки.
    Ответ написан
    1 комментарий
  • Как посчитать количество циклов у перестановки?

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

    Поэтому, алгоритм простой - посчитать циклы по одному.
    Фактически, перестановка - это граф и вам надо подсчитать в нем количество компонент связности. Надо использовать DFS. Но граф очень простой, поэтому DFS выраждается в тупо цикл.

    Заведите массив флагов длинной с перестановку. Пройдитесь по всем позициям и, если текущая не помечена, запускайте от нее второй цикл, который пометит ее и перейдет в позицию по перестановке (row[i]) и пометит там и опять перейдет и так далее, пока не наткнется на уже помеченную позицию. Так вы побойдете один цикл и пометите все позиции в нем. Поэтому прибавьте 1 к счетчику, когда будете запускать внутренний цикл.

    В решении будет 2 вложенных цикла, внешний - удобнее всего делать for, внутренний можно тоже делать for или while, но в for будет вместо инкримента переход по перестановке. И эти 2 вложенных цикла суммарно обойдут все позиции по одному разу, поэтому время работы алгоритма - линейное.
    Ответ написан
    Комментировать
  • Как называется алгоритм, в котором заданный отрезок собирается из набора отрезков меньшей длины?

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

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

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

    Если же вы можете один раз что-то предподсчитать для всех магазинов, то потом можно выполнять "запросы" даже не проходясь по всем магазинам.

    Можно по каждому тегу составить список магазинов, имеющих его в названии, упорядоченный как-то (допустим, по id магазинов). Эту структуру можно построить за один проход по всем магазинам и сохранить.

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

    В хужшем случае, где используется очень частый тег, обработка запроса будет почти как полный просмотр всех магазинов (даже если в ответ попадет их малая часть), но в среднем этот метод будет работать неплохо.
    Ответ написан
    Комментировать
  • Определить победителя КНБ?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    (-1) % 3 = 2

    Это математическое определение вычетов по модулю. Все числа, которые отличаются на n, имеют одинаковый остаток по модулю n. Конфуз происходит из-за того, что операция взятия по модулю во многих языках программирования работает не так. Для отрицательных чисел она выдаст отрицательное значение, правда к которому можно прибавить n, что бы получить правильный модуль - число от 0 до n-1.

    Поэтому при реализации можно делать (a-b+3)%3 Или преобразовать, чтобы не было вычитания: b == (a+1)%3
    Ответ написан
    Комментировать
  • Односвязные списки. Удаление элемента?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Только если вам известен ПРЕДЫДУЩИЙ элемент. Иначе за честные О(1) вы из односвязного списка ничего не удалите.

    Можно амортизационно удалить за О(1) просто пометив этот элемент удаленным. Но тогда все функции, которые проходятся по списку, должны такие помеченные элементы действительно удалять во время прохода.

    Суммарное время работы алгоритма будет как если бы удаление было за О(1). Но некоторые отдельные операции могут быть сильно медленнее, чем при честной константе. Например, если вы кучу раз добавите элемент в начало списка и тут же удалите, то потом вывод списка будет медленным, несмотря на то, что список должен быть пустым.

    Но на практике этот метод, наверно, не применяется. Потому что вы же где-то берете указатель на удаляемый элемент. Обычно можно вместе с ним получать и указатель на предыдущий. Или тупо использовать двусвязные списки.
    Ответ написан
    1 комментарий
  • Сумма арифметической прогрессии?

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

    Первый член - 1 (при j=i+1), последний - n-i (при j=n). Всего их n-i. Ну а дальше - стандартная формула: среднее крайних членов, помноженное на их количество.

    Как из этого получается O(n^3). По уму, надо раскрыть скобки и разложить на сумму трёх рядов, в зависимости от степени i в слагаемом. Дальше сумма i даст также O(n^2). Сумма по i^2 даст O(n^3). Тут уже нельзя арифметическую прогрессию применять, но это известная формула - сумма n квадратов даст n(n+1)(2n+1)/6. Ее можно вывести, если взять ряд f(x)=1+x+x^2+...+x^n = (1-x^{n+1})/(1-x) и найти (x*f'(x))'. Потом туда можно подставить x=1. Или есть визуальные доказательства. Каждый квадрат - это квадрат из кубиков. Их все можно сложить в пирамиду. 6 таких пирамид можно сложить в параллелепипед.
    Ответ написан
    1 комментарий
  • Как ускорить код?

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

    Во-вторых, как вам уже сказали - амортизационно это все будет O(s). Потому что внутренний цикл делает "лишних" операций суммарно столько, сколько l-1 на конце всех размещений. Их 0 в l^(n-1)*(l-1) размещениях, 1 в l^(n-2)*(l-1), и т.д. если все это просуммировать, то результат будет меньше l^n - количества итераций внешнего цикла.
    Ответ написан
    Комментировать
  • Как из убывающей последовательности сделать возрастающую в c++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    1) Проходитесь по массиву, находя убывающие последовательности.

    2) Разворачиваете каждую их них.

    3) ???

    4) PROFIT!

    Вот вам подсказка, как можно выделять в массиве убывающие последовательности.
    start = 0;
    while (start < n) {
      end = start;
      ПОКА (start..end+1 - убывающая последовательность) {
        ++end;
      }
      // start..end - убывающая последовательность.
      start = end+1;
    }


    Развернуть кусок с i по j можно одним циклом while. Меняйте местами 2 крайних элемента и тогда останется развернуть кусок с i+1 по j-1.
    Ответ написан
    Комментировать