source_emaxx

Статті e-maxx

Алгебра

прості алгоритми

• Функція Ейлера
• Бінарне піднесення в степінь за O(log N)
• Алгоритм Евкліда знаходження НСД (найбільшого спільного дільника)
• Решето Ератосфена
• Розширений алгоритм Евкліда
• Числа Фібоначі та їх швидке обчислення
• Обернений елемент в кільці за модулем
• Код Грея
• Довга арифметика
• Дискретне логарифмування за модулем M алгоритмом baby-step-giant-step Шенкса за O(sqrt(M) log M)
• Діофантові рівняння з двома невідомими: AX+BY=C
• Модульне лінійне рівняння першого порядку: AX=B
• Китайська теорема про остачі. Алгоритм Гарнера
• Знаходження степені дільника факторіала
• Трійкова збалансована система числення
• Обчислення факторіала N! за модулем P за O(P log N)
• Перебір всіх підмасок даної маски. Оцінка 3^N для загальної кількості підмасок всіх масок
• Первісний корінь. Алгоритм знаходження
• Дискретне обчислення кореня
• Решето Ератосфена з лінійним часом роботи

складні алгоритми

• Тест BPSW на простоту чисел за O(log N)
• Ефективні алгоритми факторизації: Поларда p-1, Поларда p, Бента, Поларда Монте-Карло, Ферма
• Швидке перетворення Фур'є за O(N log N). Застосування при множенні двох поліномів або довгих чисел

Графи

прості алгоритми

• Пошук в ширину
• Пошук в глибину
• Топологічне сортування
• Пошук компонент зв'язності

компоненти сильної зв'язності, мости і т.д.

• Пошук компонентів сильної зв'язності, побудова каркасу графа за O(N + M)
• Пошук мостів за O(N + M)
• Пошук точок зчеплення за O(N + M)
• Пошук мостів в режимі онлайн за O(1) в середньому

найкоротші шляхи з однієї вершини

• Алгоритм Дейкстри знаходження найкоротших шляхів від заданої вершини до всіх інших вершин за O(N² + M)
• Алгоритм Дейкстри для розрідженого графу знаходження найкоротших шляхів від заданої вершини до всіх інших вершин за O(M log N)
• Алгоритм Форда-Беллмана знаходження найкоротших шляхів від заданої вершини до всіх інших вершин за O(N M)
• Алгоритм Левіта знаходження найкоротших шляхів від заданої вершини до всіх інших вершин за O(N M)

найкоротші шляхи між усіма парами вершин

• Знаходження найкоротших шляхів між усіма парами вершин графа методом Флойда-Уоршелла за O(N³)
• Підрахунок кількості шляхів фіксованої довжини між усіма парами вершин, знаходження найкоротших шляхів фіксованої довжини за O(N³ log K)

мінімальний каркас

• Мінімальна каркасне дерево. Алгоритм Прима за O(N²) і за O(M log N)
• Мінімальна каркасне дерево. Алгоритм Крускала за O(M log N + N²)
• Мінімальна каркасне дерево. Алгоритм Крускала зі структурою даних 'система множин, що не перетинаються' за O(M log N)
• Матрична теорема Кірхгофа. Знаходження кількості каркасних дерев за O(N³)
• Код Прюфера. Формула Келі. Кількість способів зробити граф зв'язним

цикли

• Знаходження негативного циклу в графі за O(N M)
• Знаходження Ейлерового шляху або Ейлерового циклу за O(M)
• Перевірка графа на ациклічність та знаходження циклу за O(M)

найменший спільний предок (LCA.md)

• Найменший спільний предок. Знаходження за O(sqrt (N)) і O(log N) з препроцесингом O(N)
• Найменший спільний предок. Знаходження за O(log N) з препроцесингом O(N log N) (метод двійкового підйому)
• Найменший спільний предок. Знаходження за O(1) з препроцесингом O(N) (алгоритм Фарах-Колтона і Бендера)
• Задача RMQ (Range Minimum Query - мінімум на відрізку). Знаходження за O(1) з препроцесингом O(N)
• Найменший спільний предок. Знаходження за O(1) в режимі офлайн (алгоритм Тар'яна)

потоки і пов'язані з ними задачі

• Алгоритм Едмондса-Карпа знаходження максимального потоку за O(N M²)
• Метод проштовхування preflow для знаходження максимального потоку за O(N⁴)
• Модифікація методу проштовхування preflow за O(N³)
• Потік з обмеженнями
• Потік мінімальної вартості (min-cost-flow). Алгоритм шляхів, що збільшуються, за O(N³ M)
• Задача про призначення. Рішення з допомогою min-cost-flow за O(N⁵)
• Задача про призначення. Угорський алгоритм (алгоритм Куна) за O(N³)
• Знаходження мінімального розрізу алгоритмом Штор-Вагнера за O(N³)
• Потік мінімальної вартості, циркуляція мінімальної вартості. Алгоритм видалення циклів негативної ваги
• Алгоритм Дініца знаходження максимального потоку

паросполука і пов'язані з ними задачі

• Алгоритм Куна знаходження найбільшої паросполуки за O(N M)
• Перевірка графа на дводольність і розбиття на дві частки за O(M)
• Знаходження найбільшої по вазі вершинно-зваженої паросполуки за O(N³)
• Алгоритм Едмондса знаходження найбільшої паросполуки у довільних графах за O(N³)
• Покриття шляхами орієнтованого ациклічного графа
• Матриця Татта. Рандомізований алгоритм для пошуку максимальної паросполуки у довільному графі

зв'язність

• Реберна зв'язність. Властивості та знаходження
• Вершинна зв'язність. Властивості та знаходження
• Побудова графа із зазначеними величинами вершинної та реберної зв'язності і найменшою із степеней вершин

зворотні задачі

• Зворотня задача SSSP (inverse-SSSP - зворотня задача найкоротших шляхів з однієї вершини) за O(M)
• Зворотня задача MST (inverse-MST - зворотня задача мінімального каркасу) за O(N M²)

різне

• Розмальовка ребер дерева (структури даних) - рішення за O(log N)
• Задача 2-SAT (2-CNF). Рішення за O(N + M)
• Heavy-light декомпозиція

Геометрія

прості алгоритми

• Довжина об'єднання відрізків на прямій за O(N log N)
• Знакова площа трикутника і предикат 'За годинниковою стрілкою'
• Перевірка двох відрізків на перетин
• Знаходження рівняння прямої для відрізку
• Знаходження точки перетину двох прямих
• Знаходження точки перетину двох відрізків
• Знаходження площі простого багатокутника за O(N)
• Теорема Піка. Знаходження площі решіткового багатокутника за O(1)
• Задача про покриття відрізків точками
• Центри тяжіння багатокутників та багатогранників

більш складні алгоритми

• Перетин кола і прямої
• Перетин двох кіл
• Побудова опуклої оболонки алгоритмом Грехема-Ендрю за O(N log N)
• Знаходження площі об'єднання трикутників. Метод вертикальної декомпозиції
• Перевірка точки на належність опуклому багатокутнику за O(log N)
• Знаходження вписаного кола в опуклому багатокутнику за допомогою тернарного пошуку за O(N log² C)
• Знаходження вписаного кола в опуклому багатокутнику методом стиснення сторін за O(N log N)
• Діаграма Вороного у двовимірному випадку, її властивості, застосування. Найпростіший алгоритм побудови за O(N⁴)
• Знаходження всіх граней та зовнішню грань планарного графа за O(N log N)
• Знаходження пари найближчих точок алгоритмом "розділяй та володій" за O(N log N)
• Перетворення геометричної інверсії
• Пошук спільних дотичних для двох кіл
• Пошук пари відрізків, що перетинаються, алгоритмом "sweep line" за O(N log N)

Стрічки

• Z-функція стрічки та її обчислення за O(N)
• Префікс-функція, її обчислення та застосування. Алгоритм Кнута-Морріса-Пратта
• Алгоритми хешування у задачах на стрічки
• Алгоритм Рабіна-Карпа пошуку підстрічки в стрічці за O(N)
• Розбір виразів за O(N). Зворотня польська нотація
• Суфіксний масив. Побудова за O(N log N) та застосування
• Суфіксний автомат. Побудова за O(N) та застосування
• Знаходження всіх підпаліндромів за O(N)
• Декомпозиція Ліндона. Алгоритм Дюваля. Знаходження найменшого циклічного зсуву за O(N) часу та O(1) пам'яті
• Алгоритм Ахо-Корасик
• Суфіксне дерево. Алгоритм Уконена
• Пошук всіх тандемних повторів в стрічках алгоритмом Мейн-Лоренца ("розділяй та володій") за O(N log N)

Структури даних

• Sqrt-декомпозиція
• Дерево Фенвіка
• Система множин, що не перетинаються
• Дерево відрізків
• Декартове дерево (treap, дераміда)
• Модифікація стека і черги для знаходження мінімуму за O(1)
• Рандомізована куча

Алгоритми на послідовностях

• Задача RMQ (Range Minimum Query - мінімум на відрізку)
• Знаходження найдовшої зростаючої підпослідовності за O(N²) і O(N log N)
• K-а порядкова статистика за O(N)

Динаміка

• Динаміка по профілю. Задача "паркет"
• Знаходження найбільшої нульової підматриці за O(N M)

Лінійна алгебра

• Метод Гауса рішення системи лінійних рівнянь за O(N³)
• Знаходження рангу матриці за O(N³)
• Обчислення визначника матриці методом Гауса за O(N³)

Числові методи

• Інтегрування за формулою Сімпсона
• Пошук коренів методом Ньютона (дотичних)
• Тернарний пошук

Комбінаторика

• Біноміальні коефіцієнти
• Числа Каталана
• Намиста
• Розміщення слонів на шаховій дошці
• Правильні дужкові послідовності. Знаходження лексикографічно наступну, K-у, визначення номера
• Кількість помічених графів, зв'язаних помічених графів, помічених графів з K компонентами зв'язності
• Генерація сполучень з N елементів
• Лема Бернсайда. Теорема Пойа
• Принцип включень-виключень

Теорія ігор

• Ігри на довільних графах. Метод ретроспективного аналізу за O(M)
• Теорія Шпрага-Гранді. Нім

Розклад

• Задача Джонсона з одним верстатом
• Задача Джонсона з двома верстатами
• Оптимальний вибір завдань при відомих моментах завершення та тривалостях виконання

Різне

• Задача Йосипа
• Гра П'ятнашки: існування розв'язку
• Дерево Штерна-Броко. Ряд Фарея
• Пошук підмасиву з максимальною/мінімальною сумою за O(N)