Алгоритмические задачи
Общий поток: LeetCode + e-maxx. Данные хранятся в отдельных LiteDB.
E002. Бинарное возведение в степень
e-maxx · algorithm · оригинал: C/C++
E003. Алгоритм Евклида нахождения НОД (наибольшего общего делителя)
e-maxx · algorithm · оригинал: C/C++
E005. Расширенный алгоритм Евклида
e-maxx · algorithm · оригинал: C/C++
E007. Обратный элемент в кольце по модулю
e-maxx · algorithm · оригинал: C/C++
E008. Код Грея
e-maxx · algorithm · оригинал: C/C++
E009. Длинная арифметика
e-maxx · algorithm · оригинал: C/C++
E010. Дискретное логарифмирование
e-maxx · algorithm · оригинал: C/C++
E011. Линейные диофантовы уравнения с двумя переменными
e-maxx · algorithm · оригинал: C/C++
E012. Модульное линейное уравнение первого порядка
e-maxx · algorithm · оригинал: C/C++
E013. Китайская теорема об остатках
e-maxx · algorithm · оригинал: C/C++
E014. Нахождение степени делителя факториала
e-maxx · algorithm · оригинал: C/C++
E015. Троичная сбалансированная система счисления
e-maxx · algorithm · оригинал: C/C++
E016. Вычисление факториала по модулю
e-maxx · algorithm · оригинал: C/C++
E017. Перебор всех подмасок данной маски
e-maxx · algorithm · оригинал: C/C++
E018. Первообразные корни
e-maxx · algorithm · оригинал: C/C++
E019. Дискретное извлечение корня
e-maxx · algorithm · оригинал: C/C++
E020. Решето Эратосфена с линейным временем работы
e-maxx · algorithm · оригинал: C/C++
E021. тест BPSW на простоту чисел
e-maxx · algorithm · оригинал: C/C++
E022. Эффективные алгоритмы факторизации
e-maxx · algorithm · оригинал: C/C++
E023. Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел
e-maxx · algorithm · оригинал: C/C++
E024. Поиск в ширину
e-maxx · algorithm · оригинал: C/C++
E026. Топологическая сортировка
e-maxx · algorithm · оригинал: C/C++
E027. Алгоритм поиска компонент связности в графе
e-maxx · algorithm · оригинал: C/C++
E028. Поиск компонент сильной связности, построение конденсации графа
e-maxx · algorithm · оригинал: C/C++
E029. Поиск мостов
e-maxx · algorithm · оригинал: C/C++
E030. Поиск точек сочленения
e-maxx · algorithm · оригинал: C/C++
E031. Поиск мостов в режиме онлайн
e-maxx · algorithm · оригинал: C/C++
E032. Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры
e-maxx · algorithm · оригинал: C/C++
E033. Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры для разреженных графов
e-maxx · algorithm · оригинал: C/C++
E034. Алгоритм Форда-Беллмана
e-maxx · algorithm · оригинал: C/C++
E035. Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершин
e-maxx · algorithm · оригинал: C/C++
E036. Алгоритм Флойда-Уоршелла нахождения кратчайших путей между всеми парами вершин
e-maxx · algorithm · оригинал: C/C++
E037. Кратчайшие пути фиксированной длины, количества путей фиксированной длины
e-maxx · algorithm · оригинал: C/C++
E038. Минимальное остовное дерево. Алгоритм Прима
e-maxx · algorithm · оригинал: C/C++
E039. Минимальное остовное дерево. Алгоритм Крускала
e-maxx · algorithm · оригинал: C/C++
E040. Минимальное остовное дерево. Алгоритм Крускала с системой непересекающихся множеств
e-maxx · algorithm · оригинал: C/C++
E041. Матричная теорема Кирхгофа. Нахождение количества остовных деревьев
e-maxx · algorithm · оригинал: C/C++
E042. Код Прюфера. Формула Кэли. Количество способов сделать граф связным
e-maxx · algorithm · оригинал: C/C++
E043. Нахождение отрицательного цикла в графе
e-maxx · algorithm · оригинал: C/C++
E044. Нахождение Эйлерова пути за O (M)
e-maxx · algorithm · оригинал: C/C++
E045. Проверка графа на ацикличность и нахождение цикла
e-maxx · algorithm · оригинал: C/C++
E046. Наименьший общий предок. Нахождение за O (sqrt (N)) и O (log N) с препроцессингом O (N)
e-maxx · algorithm · оригинал: C/C++
E047. Наименьший общий предок. Нахождение за O (log N) (метод двоичного подъёма)
e-maxx · algorithm · оригинал: C/C++
E048. Наименьший общий предок. Нахождение за O (1) с препроцессингом O (N) (алгоритм Фарах-Колтона и Бендера)
e-maxx · algorithm · оригинал: C/C++
E049. Задача RMQ (Range Minimum Query - минимум на отрезке). Решение за O (1) с препроцессингом O (N)
e-maxx · algorithm · оригинал: C/C++
E050. Наименьший общий предок. Нахождение за в оффлайн (алгоритм Тарьяна)
e-maxx · algorithm · оригинал: C/C++
E051. Максимальный поток методом Эдмондса-Карпа за O (N M2)
e-maxx · algorithm · оригинал: C/C++
E052. Максимальный поток методом Проталкивания предпотока за O (N4)
e-maxx · algorithm · оригинал: C/C++
E053. Модификация метода Проталкивания предпотока для нахождения максимального потока за O (N3)
e-maxx · algorithm · оригинал: C/C++
E054. Нахождение потока в графе, в котором у каждого ребра указано минимальное и максимальное значение потока
e-maxx · algorithm · оригинал: C/C++
E055. Поток минимальной стоимости (min-cost- flow). Алгоритм увеличивающих путей
e-maxx · algorithm · оригинал: C/C++
E056. Задача о назначениях. Решение с помощью min-cost-flow
e-maxx · algorithm · оригинал: C/C++
E057. Венгерский алгоритм решения задачи о назначениях
e-maxx · algorithm · оригинал: C/C++
E058. Нахождение минимального разреза. Алгоритм Штор-Вагнера
e-maxx · algorithm · оригинал: C/C++
E059. Поток минимальной стоимости, циркуляция минимальной стоимости. Алгоритм удаления циклов отрицательного веса
e-maxx · algorithm · оригинал: C/C++
E061. Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе
e-maxx · algorithm · оригинал: C/C++
E062. Проверка графа на двудольность и разбиение на две доли
e-maxx · algorithm · оригинал: C/C++
E063. Нахождение наибольшего по весу вершинно-взвешенного паросочетания
e-maxx · algorithm · оригинал: C/C++
E064. Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах
e-maxx · algorithm · оригинал: C/C++
E065. Покрытие путями ориентированного ациклического графа
e-maxx · algorithm · оригинал: C/C++
E067. Рёберная связность. Свойства и нахождение
e-maxx · algorithm · оригинал: C/C++
E068. Рёберная связность. Свойства и нахождение
e-maxx · algorithm · оригинал: C/C++
E069. Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин
e-maxx · algorithm · оригинал: C/C++
E070. Обратная задача SSSP (inverse-SSSP - обратная задача кратчайших путей из одной вершины)
e-maxx · algorithm · оригинал: C/C++
E071. Обратная задача MST (inverse-MST - обратная задача минимального остова) за O (N M2)
e-maxx · algorithm · оригинал: C/C++
E075. Длина объединения отрезков на прямой за O (N log N)
e-maxx · algorithm · оригинал: C/C++
E076. Знаковая площадь треугольника и предикат "По часовой стрелке"
e-maxx · algorithm · оригинал: C/C++
E077. Проверка двух отрезков на пересечение
e-maxx · algorithm · оригинал: C/C++
E078. Нахождение уравнения прямой для отрезка
e-maxx · algorithm · оригинал: C/C++
E079. Точка пересечения прямых
e-maxx · algorithm · оригинал: C/C++
E080. Пересечение двух отрезков
e-maxx · algorithm · оригинал: C/C++
E081. Нахождение площади простого многоугольника
e-maxx · algorithm · оригинал: C/C++
E082. Теорема Пика. Нахождение площади решётчатого многоугольника
e-maxx · algorithm · оригинал: C/C++
E083. Задача о покрытии отрезков точками
e-maxx · algorithm · оригинал: C/C++
E084. Центры тяжести многоугольников и многогранников
e-maxx · algorithm · оригинал: C/C++
E085. Пересечение окружности и прямой
e-maxx · algorithm · оригинал: C/C++
E086. Пересечение двух окружностей
e-maxx · algorithm · оригинал: C/C++
E087. Построение выпуклой оболочки обходом Грэхэма
e-maxx · algorithm · оригинал: C/C++
E088. Нахождение площади объединения треугольников. Метод вертикальной декомпозиции
e-maxx · algorithm · оригинал: C/C++
E089. Проверка точки на принадлежность выпуклому многоугольнику
e-maxx · algorithm · оригинал: C/C++
E090. Нахождение вписанной окружности в выпуклом многоугольнике с помощью тернарного поиска
e-maxx · algorithm · оригинал: C/C++
E091. Нахождение вписанной окружности в выпуклом многоугольнике методом "сжатия сторон" ("shrinking sides") за
e-maxx · algorithm · оригинал: C/C++
E092. Диаграмма Вороного в 2D
e-maxx · algorithm · оригинал: C/C++
E093. Нахождение всех граней, внешней грани планарного графа
e-maxx · algorithm · оригинал: C/C++
E094. Нахождение пары ближайших точек
e-maxx · algorithm · оригинал: C/C++
E095. Преобразование геометрической инверсии
e-maxx · algorithm · оригинал: C/C++
E096. Поиск общих касательных к двум окружностям
e-maxx · algorithm · оригинал: C/C++
E097. Поиск пары пересекающихся отрезков алгоритмом заметающей прямой за O (N log N)
e-maxx · algorithm · оригинал: C/C++
E098. Z-функция строки и её вычисление
e-maxx · algorithm · оригинал: C/C++
E099. Префикс-функция. Алгоритм Кнута- Морриса-Пратта
e-maxx · algorithm · оригинал: C/C++
E100. Алгоритмы хэширования в задачах на строки
e-maxx · algorithm · оригинал: C/C++
E101. Алгоритм Рабина-Карпа поиска подстроки в строке за O (N)
e-maxx · algorithm · оригинал: C/C++
E102. Разбор выражений. Обратная польская нотация
e-maxx · algorithm · оригинал: C/C++
E103. Суффиксный массив
e-maxx · algorithm · оригинал: C/C++
E104. Суффиксный автомат
e-maxx · algorithm · оригинал: C/C++
E105. Нахождение всех подпалиндромов
e-maxx · algorithm · оригинал: C/C++
E106. Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига
e-maxx · algorithm · оригинал: C/C++
E107. Алгоритм Ахо-Корасик
e-maxx · algorithm · оригинал: C/C++
E108. Суффиксное дерево. Алгоритм Укконена
e-maxx · algorithm · оригинал: C/C++
E109. Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца
e-maxx · algorithm · оригинал: C/C++
E110. Поиск подстроки в строке с помощью Z- или Префикс-функции
e-maxx · algorithm · оригинал: C/C++
E111. Решение задачи "сжатие строки" за O (N)
e-maxx · algorithm · оригинал: C/C++
E112. Sqrt-декомпозиция
e-maxx · algorithm · оригинал: C/C++
E113. Дерево Фенвика
e-maxx · algorithm · оригинал: C/C++
E114. Система непересекающихся множеств
e-maxx · algorithm · оригинал: C/C++
E115. Дерево отрезков
e-maxx · algorithm · оригинал: C/C++
E116. Декартово дерево (treap, дерамида)
e-maxx · algorithm · оригинал: C/C++
E117. Модификация стека и очереди для извлечения минимума за O (1)
e-maxx · algorithm · оригинал: C/C++
E118. Рандомизированная куча
e-maxx · algorithm · оригинал: C/C++
E119. Задача RMQ (Range Minimum Query - минимум на отрезке)
e-maxx · algorithm · оригинал: C/C++
E120. Нахождение наидлиннейшей возрастающей подпоследовательности
e-maxx · algorithm · оригинал: C/C++
E121. K-ая порядковая статистика за O (N)
e-maxx · algorithm · оригинал: C/C++
E122. Нахождение наидлиннейшей возрастающей подпоследовательности
e-maxx · algorithm · оригинал: C/C++
E123. Динамика по профилю. Задача "паркет"
e-maxx · algorithm · оригинал: C/C++
E124. Нахождение наибольшей нулевой подматрицы
e-maxx · algorithm · оригинал: C/C++
E125. Метод Гаусса решения системы линейных уравнений
e-maxx · algorithm · оригинал: C/C++
E126. Нахождение ранга матрицы
e-maxx · algorithm · оригинал: C/C++
E127. Вычисление определителя методом Краута за O (N3)
e-maxx · algorithm · оригинал: C/C++
E128. Интегрирование по формуле Симпсона
e-maxx · algorithm · оригинал: C/C++
E129. Метод Ньютона (касательных) для поиска корней
e-maxx · algorithm · оригинал: C/C++
E130. Тернарный поиск
e-maxx · algorithm · оригинал: C/C++
E131. Биномиальные коэффициенты
e-maxx · algorithm · оригинал: C/C++
E134. Расстановка слонов на шахматной доске
e-maxx · algorithm · оригинал: C/C++
E135. Правильные скобочные последовательности
e-maxx · algorithm · оригинал: C/C++
E136. Генерация сочетаний из N элементов
e-maxx · algorithm · оригинал: C/C++
E137. Лемма Бернсайда. Теорема Пойа
e-maxx · algorithm · оригинал: C/C++
E138. Принцип включений-исключений
e-maxx · algorithm · оригинал: C/C++
E139. Игры на произвольных графах
e-maxx · algorithm · оригинал: C/C++
E140. Теория Шпрага-Гранди. Ним
e-maxx · algorithm · оригинал: C/C++
E141. Задача Джонсона с одним станком
e-maxx · algorithm · оригинал: C/C++
E142. Задача Джонсона с двумя станками
e-maxx · algorithm · оригинал: C/C++
E143. Оптимальный выбор заданий при известных временах завершения и длительностях выполнения
e-maxx · algorithm · оригинал: C/C++
E145. Игра Пятнашки: существование решения
e-maxx · algorithm · оригинал: C/C++
E146. Дерево Штерна-Броко. Ряд Фарея
e-maxx · algorithm · оригинал: C/C++
E147. Поиск подотрезка массива с максимальной/минимальной суммой
e-maxx · algorithm · оригинал: C/C++