изображения

Статьи

DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи GRA Алгоритм Минимальный разрез Самая дешёвая граница в графе: вырезает предмет на фотографии и находит слабое место сети. O(m n² |C|) 2 задачи GRA Алгоритм Паросочетания в двудольном графе Наибольшее число пар в двудольном графе: Кун, Хопкрофт — Карп, теоремы Кёнига и Холла. O(E √V) 2 задачи DP Алгоритм Seam carving Сужает фото, вырезая пиксельные швы наименьшей энергии; каждый шов — динамика по таблице. O(W·H) на шов, O(k·W·H) на k швов 2 задачи NUM~ Алгоритм Метод Монте-Карло Оценка числа случайным опытом: ошибка 1/√n в любой размерности, честный доверительный интервал. O(n) испытаний, ошибка ~ σ/√n 2 задачи ML Алгоритм k-средних Делит точки на k групп так, чтобы точки были поближе к центру своей группы. O(n · k · d) за шаг 2 задачи ML Алгоритм Перцептрон и обратное распространение Нарисуйте цифру: её узнают перцептрон 1958 года и сеть со скрытым слоем, обученные прямо на странице за секунду.

перцептрон — O(d) на пример; градиент сети — O(число весов) на пример

1 задача TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи TEC Приём Данные, удобные кэшу Тот же алгоритм, другой порядок обращений к памяти: обход блоками, запас в строках и раскладка по полям. O-большое то же 1 задача TEC Приём Векторизация Вынести цикл из интерпретатора в операции над целыми массивами: что ускоряется в сотни раз и что не векторизуется. та же O(n), что у цикла 2 задачи

Задачи

Ближайший цвет палитры «Жизнь» на большом поле Мозаика из доминошек Самый дешёвый шов Тёмные острова Фото в шестнадцати красках Квадродерево снимка Место для подписи Покрытие снимками Шов через пиксель

Часто рядом

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