Задачник Базовый курс EN

На чём держится

стек

Статьи

SRT Алгоритм Timsort Находит готовые упорядоченные куски и сливает их: стек серий, галоп, powersort. O(n log n), на готовых данных O(n) 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи GRA Алгоритм Поиск в глубину Идёт вглубь, отмечает вход и выход каждой вершины и по ним находит циклы за O(V + E). O(V + E) 2 задачи GRA Алгоритм Компоненты сильной связности Группы вершин, где из любой можно дойти до любой: Тарьян за один обход, Косараю за два, O(V + E). O(V + E) 2 задачи GRA Алгоритм Мосты и точки сочленения Улицы и перекрёстки, без которых граф распадается: один поиск в глубину с числами tin и low, O(V + E). O(V + E) 2 задачи GRA Алгоритм Эйлеров путь Пройти каждое ребро ровно раз: правило нечётных вершин и алгоритм Хирхольцера за O(E). O(V + E) 3 задачи GEO Алгоритм Выпуклая оболочка Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n). O(n log n) 2 задачи GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи TEC Приём Амортизационный анализ Оценка всей последовательности операций, а не каждой: суммой, монетами и потенциалом — и где она не спасает. оценка на последовательность 2 задачи

Задачи

Скобки в рукописи Когда потеплеет Цикл импортов Два перепутанных ключа Какие серии слить Кольцо из кусков Место для подписи Порядок выполнения модулей Самое сильное за месяц Цена поиска Сложность по Лемпелю — Зиву

Часто рядом

классика 10 собеседования 6 олимпиады 5 обход 4 граф 4 карты и навигация 4 амортизация 3 очередь 3 массив 3 связность 3 сортировка 2 в проде 2