Ответы пользователя по тегу Алгоритмы
  • Как хэшировать вещественные числа?

    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.
    Ответ написан
    Комментировать
  • Как реализовать функцию копирования бит со смещениями в src и/или dst и не кратным 8 количестве бит?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Самое эффективное - использовать какой-нибудь SSE (гуглите shift bits sse. Лучше всего, мне кажется, подойдет _mm_slli_epi64). Но там очень много кода и случаев будет. Придется отдельно разбирать случаи сдвига влево и вправо, отдельно вычленять биты, которые SSE операция при сдвиге бы потеряла и записывать куда надо.

    Следующий по эффективности вариант - это читать в int64_t, и там сдвигать биты. Придется сначала из переменной доставать старшые/младшие 1-7 бит и писать их отдельно, потом сдвигать биты и записывать куда надо. Используйте memcopy для чтения/записи 64-ех бит. Еще можно ускорить, если отдельно обработать первые несколько байт до 64-битного выравнивания, и потом придется еще обрабоать отдельно лишние 0-7 байтов в конце, если их количество не делится на 8.
    Ответ написан
  • Какой алгоритм используется при возможности 2 неудачных попыток?

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

    Пусть C(n,k) - сколько надо в худшем случае бросков, если мы знаем, что предмет разбивается при бросании с 1..n и можно сделать k неудачных бросков.

    С(n,k) = min_i=1..n-1 ( max(C(i,k-1), C(n-i, k)) )) + 1


    База - C(1, k) = 0; C(n, 1) = n-1.
    Ответ написан
    2 комментария
  • Как разбить числа по группам так, чтобы в группах находились близкие по значению числа?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Надо ввести какую-то метрику - какая-то числовая оценка, которая говорила бы вам, почему [[1,2],[3,4],[5,6]] лучше чем [[1,2,3,4],[5],[6]]. Например, можно взять максимальную разность двух чисел в любой группе. Или сумму квадратов расстояний от всех чисел до среднего в их группе. Или минимальное расстояние между числами в разных группах (это надо максимизировать).

    Потом можно применять какой-то из известных методов кластеризации, в зависимости от выбранной метрики. В случае одного измерения, как у вас (просто числа) можно еще применить и динамическое программирование. Этот метод работает для практически любой вменяемой метрики. Считайте функцию F(n,k) - лучшая возможная метрика если первые n чисел разбить на k групп. Для пересчета надо перебрать, сколько чисел идет в последнюю группу (i), и пересчитать метрику на основе F(n-i, k-1). из всех вариантов выбрать лучший.
    Ответ написан
    Комментировать
  • Какой алгоритм вычисления кратности чисел более эффективен?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Судя по названию функции (sum) вам надо найти сумму чисел. Это делается в одно действие без циклов вообще.

    Если бы были нужны только числа делящееся на 3, то их сумма - f(n, 3)=3*floor(n/3)(floor(n/3)+1)/2. Эта формула получается вынесением 3 за скобки в сумме и дальше применением формулы армфметической прогрессии.

    Чтобы взять сумму делящихся на 3 или 5 надо взять сумму делящихся на 3, прибавить сумму делящихся на 5 и вычесть сумму делящихся на 15. Потому что делящиеся на 15 были подсчитанны 2 раза в первых слагаемых. Т.е. ответ - f(n,3)+f(n,5)-f(n,15)
    Ответ написан
    Комментировать
  • Влезет ли параллелепипед в четверть цилиндра?

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

    Как проверить прямоугольник на впихивание в сектор? Если коробка помещается, ее можно в секторе вертеть и двигать, пока она не будет касаться границы сектора тремя вершинами. Получаются случаи: угол коробки совспадает с уголом сектора (диагональ прямоугольника <= радиуса), одна точка на прямой стороне сектора и две на круглой, 2 угла на двух прямых сторонах и одна на круглой.

    Два последних случая надо порисовать, ввести какие-то переменные (например во втором случае можно ввести x и y - длины отрезков от угла сектора до углов прямоугольника) решить систему квадратных уравнений (длины сторон заданны, третья точка лежит на окружности) и проверить, что четвертая, свободная точка лежит внутри.

    Что бы не плодить еще и случаи с порядком вершин советую перебрать 3! перестановок всех длин параллелипипида. Третья всегда будет высотой, дву другие в заданном порядке задают расположение точек. Например в первом случае первая длина - будет шириной прямоугольника, а вторая - высотой. В случае касания двумя точками двух прямых сторон, первая длина - будет стороной отсекающей угол, и т.д.

    Вот так перебрав все случаи различных расположений коробки надо проверить, что хотя бы один из них помещается в ваш цилиндр.
    Ответ написан
  • Алгоритм перевода RGB-компонент в длину волны?

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

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

    Еще надо помнить про специфику работы мониторов - эти самые числа в RGB задают квадратные корни интенсивности свечения разных пикселей.

    Еще, возможно будет легче сначала преобразовать RGB в какой-нибудь YUV или HSL.
    Ответ написан
    1 комментарий
  • Как ускорить перебор элементов списка?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно в несколько раз с оптимизировать, переписав на C++ c векторизацией (SSE там всякие). Тогда сравнение двух строк будет 1-2 инструкции вместо 15. Еще можно распаралеллить вычисления. Но все эти оптимизации все равное не позволят вам быстро считать для 100000 строк. Что уж говорить, сама матрица будет занимать минимум 10 гигабайт, если аккуратно на C писать или типизированный numpy массивы использовать. А так она и все 20 и 40 гигабайт займет запросто.

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