Алгоритмы *

Есть вот такая, вроде бы, простая задача на литкоде: Дано три числа total - сколько у вас есть денег, cost1, cost2 - цены двух товаров. Надо подсчитать, сколько всего существует различных способов купить сколько-то этих двух товаров, не выходя из бюджета (значение имеет только общее количество покупок). Иными словами, сколько существет целых неотрицательных пар (x, y), таких что x*cost1+y*cost2 <= total . Например, имея товары ценами {5, 10} и 20 денег на руках, есть 9 способов потратить деньги: 0, 5, 5+5, 5+5+5, 5+5+5+5, 10, 10+5, 10+5+5, 10+10.

Она там даже помечена как medium и вообще в одну строчку решается, но это если допускать безумно медленное решение за O(total / max(cost1, cost2)) , т.е линейное от входных чисел. А сможете ли вы решить ее сильно быстрее - за O(log(max(cost1, cost2))) ? В этом случае задачка становится вполне себе hard и требует много математики и аккуратности. Если интересно решение - добро пожаловать под кат. Буду рад любым альтернативным решениям. Может кто-то сможет додуматься до похожего решения проще.

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

Имея массив целых положительных чисел, нужно заменить каждый элемент так, чтобы разница между соседними элементами массива была меньше или равна заданному целевому значению (target). Нам необходимо минимизировать стоимость корректировки, то есть суммарную разницу между новыми и старыми значениями. По сути, нам нужно минимизировать ∑|A[i] — Anew[i]|, где 0 ≤ i ≤ n-1, n — размер A[], а Anew[] — массив с разницей между соседними элементами меньше или равной заданной. Предположим, что все элементы массива меньше константы M = 100.

Несмотря на то, что исследования в области постквантовой криптографии с каждым днём набирают обороты, практическое приложение полученных результатов очень лениво внедряется в реальные продукты. Во многом это связано с небезосновательными опасениями по поводу своевременности и практичности этого. Многие специалисты считают этот процесс преждевременным. Однако учёные настойчиво разрабатывают различные постквантовые приложения. Как знатный параноик и перестраховщик, я, скорее, нахожусь на стороне вторых, поскольку отчётливо представляю себе тот день, когда произойдёт технологический прорыв и в то же мгновение большинство криптографических схем прикажут долго жить, накрывшись респектабельным медным тазиком реализаций алгоритма Шора. Массовой истерии не избежать, например, как сейчас с генеративным ИИ. В отличие от тех же проблем с внезапно слишком умным ИИ, практическое приложение которого ещё не до конца осознано и варится в котле общественных мнений с явными попытками ограничения неконтролируемого развития, со скачком в квантовых вычислениях подобный номер вряд ли пройдёт. Всё, что может быть взломано, будет взломано, и мир погрузится в хаос...

Возможно, всё не так страшно, но бережёного бог бережёт, поэтому чем раньше начнут внедряться постквантовые системы, тем вероятнее шанс избежать неприятных последствий этого технологического рывка. Сегодня существует несколько подходов к реализации такой защиты. Хотя, пожалуй, самый реалистичный в ближайшем будущем подход будет основываться на криптографии на основе хэшей. Примером такой системы является схема с открытым ключом в виде хэш-дерева Меркла, разработанная ещё в 1979 году и основанная на идеях Лэмпорта и Диффи.

В первом приближении надо загрузить wav или mp3 файл с музыкой в Excel, провести над загруженными данными Digital Signal Processing (DSP) или Цифровую Обработку Сигнала (ЦОС) по определенному алгоритму на Visual Basic for Application (VBA) ), сохранить результат в wav файл и прослушать его. Сравнительный пример звуков после обработки и до обработки https://disk.yandex.ru/d/y18kiOIMN7CLCA

Автор статьи: Артем Михайлов

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

Вы когда‑нибудь задумывались, почему результаты поиска файлов появляются так быстро? В этой статье мы рассмотрим удивительную структуру данных, известную как двоичное дерево (бинарное дерево), и узнаем, как именно она позволяет достичь такой быстрой обработки и поиска.

Автор статьи: Рустем Галиев

Сегодня мы рассмотрим преобразование Хафа — популярный метод обнаружения фигур среди граней и границ. Поговорим про использование преобразования Хафа для обнаружения линий и кругов.

DragonflyDB - молодая in-memory база данных, написанная на C++ и совместимая с Redis (не форк). Под капотом используется многопоточная архитектура (в отличии от однопоточного Redis) для лучшей утилизации современных процессоров и более простого вертикального масштабирования.

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

Автор статьи: Артем Михайлов

Мой друг и коллега по цеху, блоггер Сэм, недавно опубликовал своё третье иллюстрированное руководство, темой которого стало хеширование. Нет острой необходимости читать его руководство перед прочтением моей статьи, но я очень рекомендую вам это сделать. Хотя бы ради того, чтобы посмотреть на восхитительные анимации, от которых невозможно оторваться. Честно — они просто потрясающие. Тут, к сожалению, анимаций вы не найдёте, поэтому насмотритесь на них в той статье, а потом возвращайтесь сюда. Здесь вы сможете немного позабавиться поиском коллизий алгоритма хеширования MurmurHash3.

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

Идея этого поста возникла после того, как меня попросили помочь с поиском коллизий. Тогда меня охватило непреодолимое желание узнать о том, сколько хешей в секунду я смогу выжать из доступного мне железа. Собственно, тут я расскажу о поиске хеш-коллизий MurmurHash3 на скорости 200 гигахешей в секунду.

Иногда хочется решить задачу просто потому что решение легко проверить, прям сразу для множество вариантов. Взяли список из 25 элементов, отсортировали его, и применили искомую функцию 25 раз, профит. Плюс задачка напоминает обложку тетрадки по арифметике за пятый класс, там где табличка произведений, ну та где находим пятый столбец и седьмой ряд и на пересечений их будет произведение. Там же в табличке видно что 6x6 - это квадрат, а 9x4 это совсем не квадрат (скорее ближе к прямоугольнику) хотя площадь у них равная. Так вот, "литкод" хочет чтобы мы нашли n-ый элемент в данной табличке по возрастанию.

Алгоритм Луна (Luhn algorithm) - это процесс вычисления контрольной цифры для числа в соответствии со стандартом ISO/IEC 7812. Процесс предназначен, в первую очередь, для выявления ошибок, вызванных с непреднамеренным искажением данных. Например, при ручном вводе номера карты или любого другого числа.

Разберём как он работает и рассмотрим инструмент для формирования номеров по алгоритму.

Волновой алгоритм — алгоритм поиска пути, алгоритм поиска кратчайшего пути. Принадлежит к алгоритмам, основанным на методах поиска в ширину.

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

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

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

Александр Пряхин, руководитель разработки юнита в Авито Работа, рассказал, так ли мрачно выглядит будущее для разработчиков «из плоти и крови» на фоне активного развития No Code, Low Code и нейросетей.

Каждый из нас из школы помнит определение Евклидова расстояния между двумя точками на плоскости. С помощью расстояния Евклида можно вычислить расстояние между двумя точками на карте, например, между вашим местоположением и станцией метро. Но для пешехода в Нью-Йорке расстояние между двумя точками в городе будет отличаться от расстояния Евклида между двумя точками из-за невозможности передвигаться иначе, как по проезжим улицам, пересекающимся под прямыми углами. Такое расстояние так и называется: "расстояние городских кварталов" или манхэттенское расстояние. При любом способе расстояние характеризует меру близости точек. В сегодняшней статье мы расскажем о способах вычисления расстояния между двумя словами.