Тема: Линейные алгоритмы Параллель B'

YOUTUBE · 19.11.2025 05:51

Ключевые темы и таймкоды

Введение в линейные алгоритмы

0:09
  • Обсуждение темы линейных алгоритмов.
  • Упоминание о времени работы алгоритмов.

Постановка задачи

0:43
  • Описание массива из n элементов и k запросов.
  • Задача: найти сумму чисел в отрезке.

Префиксные суммы

1:28
  • Введение массива префиксных сумм pref.
  • Объяснение структуры массива: pref[0] = 0, pref[1] = a[1], pref[2] = a[1] + a[2] и так далее.

Вычисление суммы отрезка

2:29
  • Формула для вычисления суммы отрезка: pref[l] - pref[l - 1].
  • Проверка правильности формулы через математические вычисления.

Построение массива pref

4:12
  • Начальное значение pref[0] = 0.
  • Итеративный процесс построения массива: для i = 1..n, pref[i] = pref[i - 1] + a[i - 1].

Время работы алгоритма

6:13
  • Общее время работы алгоритма: O(n + k), где n — размер массива, k — количество запросов.

Заключение

6:43
  • Вопрос к аудитории о наличии вопросов по префиксным суммам.

Задача с массивом и префиксными суммами

7:10
  • Дано массив целых чисел A.
  • Необходимо найти такой отрезок [i, j], что сумма элементов массива максимальна.
  • Используется метод префиксных сумм для решения задачи.

Принцип работы метода

8:18
  • Фиксируется значение j.
  • Максимизируется разность префиксных сумм: префжитое - префi.
  • Минимизируется префi для каждого i.

Реализация метода

9:02
  • Строятся префиксные суммы.
  • Перебираются значения i от 1 до j.
  • Для каждого i вычисляется минимальное значение префиксной суммы.

Обновление ответа

10:11
  • Определяется максимальная разность префиксных сумм.
  • Если разность больше текущего максимума, обновляется ответ.

Объяснение минимизации

11:35
  • Объясняется, почему нужно минимизировать префi.
  • Подчёркивается, что максимизация разности префиксных сумм эквивалентна минимизации вычитаемого.

Новая задача с запросами

13:02
  • Дано множество запросов вида [i, j, x], где x — число.
  • Запросы делятся на два типа: добавление числа на отрезок и вычисление суммы на отрезке.

Обработка запросов добавления

15:14
  • Для каждого запроса добавляется x к элементу i и вычитается x из элемента i + 1.
  • После обработки всех запросов строятся префиксные суммы.

Пример обработки запросов

17:25
  • Рассматриваются примеры запросов: добавление единицы на отрезок [1, 3], добавление двойки на отрезок [2, 5], добавление единицы на отрезок [5, 5].
  • Показывается, как изменяются элементы массива после каждого запроса.

Построение префиксных сумм

20:19
  • Строятся префиксные суммы после обработки всех запросов.
  • Проверяется соответствие результатов требованиям задачи.

Заключение

22:43
  • Подчёркивается, что после построения префиксных сумм массив соответствует результату всех операций.
  • Подтверждается корректность выполнения задачи.

Введение в задачу

22:59
  • Обсуждение изменения элементов массива: добавление +5 вместо -2.
  • Создание «фейкового» префиксного массива «преф штрих».
  • Построение настоящей префиксной суммы на основе «преф штрих».

Новая задача

24:46
  • Описание новой задачи: массив из нулей и запросы на добавление арифметической прогрессии.
  • Формула для добавления прогрессии: a_i + = x + i * y.
  • Запросы на вывод суммы: sum_i = a_i - a_1.

Идея решения

26:38
  • Предложение использовать префиксную сумму для заполнения массива.
  • Обсуждение двух возможных решений: три раза построить префиксную сумму или два раза.

Реализация решения

27:48
  • Создание массива «б» для хранения левой части прогрессии.
  • Использование массива «ц» для хранения текущей прибавки.
  • Объяснение работы переменных «эдада» и «кур» для управления прибавкой.

Детали алгоритма

32:06
  • Описание процесса добавления прогрессии: прибавка увеличивается на y с каждым шагом.
  • Роль переменных «эдада» и «кур» в алгоритме.
  • Пример работы алгоритма с массивами «б» и «ц».

Проблемы и решения

37:13
  • Обсуждение проблемы с обнулением переменной «кур».
  • Предложение решения: уменьшение «эдада» до нуля после добавления прогрессии.
  • Уточнение, что «кур» должен быть равен нулю после завершения добавления прогрессии.

Завершение обсуждения

40:42
  • Подчёркивание необходимости дальнейшего анализа алгоритма.
  • Упоминание о возможных проблемах на следующем шаге.

Обнуление курса

40:52
  • На следующем шаге курс станет меньше нуля.
  • Для обнуления курса можно использовать формулу: `с р + 2 + равно минус цель умножить на игрек`.
  • При `с = 0` курс станет равным нулю.

Второй способ обнуления

42:03
  • Второй способ: в момент `р + 1` из курса вычесть число `р минус умножить на игрек`.
  • Формула: `д, р + первое минус равно первый минус целью умножить на игрек`.
  • После вычитания нужно вернуть число, чтобы курс снова стал равным нулю.

Сравнение методов

43:10
  • Первый метод: использование минусов для обнуления курса.
  • Второй метод: вычесть число из курса без дополнительной математики.
  • Необходимо использовать только один из методов в зависимости от ситуации.

Преимущества метода

45:05
  • Метод не требует сортировки больших чисел.
  • Выполняет те же операции, что и метод «скалайн», но без дополнительной сортировки.

Вопросы и ответы

46:06
  • Обсуждение использования `if` для обнуления курса и возможных проблем при пересечении прогрессий.
  • Упоминание о прогрессии с шагом ноль и её особенностях.

Пример с массивом

47:29
  • Пример с массивом `а` и построением суммы по массиву.
  • Построение массива после всех операций прибавления.
  • Получение итогового массива через сумму массива после всех операций.

Обратимые операции и их применение

48:29
  • Для создания при-сумм нужна любая обратимая операция.
  • Обратимая операция — это операция, которую можно нивелировать, например, для плюса это минус.
  • Для ксора это сам ксор, так как ксор числа с самим собой даёт ноль.

Проблемы с умножением и возведением в степень

49:18
  • Умножение на ноль может привести к неожиданным результатам.
  • Возведение в степень также вызывает вопросы при создании при-сумм.

Пример с ксором

50:23
  • Если ксорить число само с собой, получится ноль.
  • При-сумма с ксором работает хорошо, так как результат можно получить, повторяя операцию.

Задача с массивами

52:02
  • Даны два отсортированных массива A и B размеров n и m соответственно.
  • Необходимо найти индексы i и j такие, что модуль разности между ai и bj минимален.

Решение с указателями

53:01
  • Используются два указателя: один указывает на массив A, другой — на массив B.
  • Указатель массива B движется так, чтобы элемент был больше текущего элемента массива A.

Оптимизация алгоритма

56:09
  • Указатель массива B сдвигается вправо до тех пор, пока есть элемент, который меньше или равен текущему элементу массива A.
  • Это позволяет найти минимальный модуль разности между элементами.

Проверка правильности алгоритма

1:00:48
  • Проводится тест с массивами 2, 1 и 100.
  • Выясняется, что текущий алгоритм выводит 98 вместо 1.
  • Добавляется условие для учёта минимального и максимального элементов.

Завершение обсуждения

1:05:48
  • Подчёркивается, что массивы снова отсортированы.
  • Обсуждение переходит к следующей задаче.

Введение в задачу

1:06:11
  • Необходимо найти такие элементы массивов, чтобы сумма их значений равнялась заданному числу с.
  • Массивы упорядочены по возрастанию.

Объединение массивов

1:06:37
  • Предлагается объединить массивы в один и использовать тип для проверки соответствия чисел.
  • Важно не забыть, какой элемент где изначально лежал.

Использование указателей

1:07:07
  • Применяются два указателя: один идёт с начала массива, другой — с конца.
  • Проверяется условие: если элемент меньше или равен нулю, а сумма больше с, то элемент увеличивается.

Оптимизация поиска

1:08:01
  • Уменьшение элемента на один позволяет приблизиться к нужному значению.
  • Если сумма равна с, элемент считается найденным.

Эффективность алгоритма

1:08:43
  • Указатели проходят суммарно n элементов один от начала, другой — от конца.
  • Суммарное количество пройденных элементов равно n + m.
  • Упорядоченные массивы значительно облегчают поиск.

Обсуждение ограничений

1:09:37
  • Часто m равно n, что упрощает задачу.
  • При n < m алгоритм может работать быстрее из-за особенностей процессора.

Влияние констант

1:10:44
  • В худшем случае n и m могут быть одинаковыми.
  • Константы влияют на производительность алгоритма.

Завершение обсуждения

1:11:09
  • Обсуждение завершается, предлагается перейти к следующей задаче.

Введение в задачу

1:11:56
  • Обсуждение темы линейных алгоритмов.
  • Представление задачи о стране, представленной массивом городов с прожиточным минимумом.
  • Условие задачи: слух о том, что правее жить лучше, вызывает переселение жителей.

Пример решения задачи

1:13:39
  • Объяснение, как каждый житель ищет ближайший город справа с лучшим прожиточным минимумом.
  • Пример решения: первый житель останавливается в индексе 2, второй — в индексе 3 и т. д.

Использование стека для решения задачи

1:15:52
  • Введение стека для хранения возможных ответов.
  • Процесс удаления элементов из стека, если они не являются ответами для текущего элемента.
  • Пример: для элемента 5 ответ — минус один, для 3 — 7, для 4 — 4 и т. д.

Доказательство корректности алгоритма

1:19:43
  • Объяснение, почему стек хранит возможные ответы.
  • Доказательство по индукции: если стек пуст, ответ для текущего элемента — минус один.
  • Подтверждение, что стек сохраняет упорядоченность элементов по убыванию.

Реализация алгоритма в коде

1:23:51
  • Описание алгоритма: итерация по элементам массива справа налево.
  • Удаление элементов из стека, если они меньше текущего элемента.
  • Проверка стека на пустоту для определения ответа.

Модификация алгоритма

1:27:31
  • Обсуждение модификации алгоритма для случая, когда слух говорит о лучшем городе слева.
  • Предложение изменить порядок итерации массива.

Переход к новой задаче

1:28:20
  • Введение в задачу о гистограмме Instagram.
  • Цель задачи: вписать максимальный по площади прямоугольник в гистограмму.

Условия для прямоугольника

1:29:23
  • Прямоугольник должен лежать на нулевой координате, иначе он не максимальный.
  • Высота прямоугольника должна быть меньше минимального столбика, иначе он не впишется.

Перебор столбиков

1:30:26
  • Перебираем все столбики и для каждого пытаемся вписать максимальный прямоугольник.
  • Находим минимальный столбик слева и справа от текущего.

Вычисление высоты прямоугольника

1:31:32
  • Вычисляем высоту прямоугольника, умножая минимальный столбик на коэффициент.
  • Выбираем максимум среди всех возможных высот.

Поиск ближайшего минимума

1:32:10
  • Используем функцию для нахождения ближайшего минимума слева и справа.
  • Сохраняем элементы, которые меньше текущего, в отсортированном списке.

Новая задача

1:32:58
  • Дано прямоугольное поле, каждая клетка которого либо 0, либо 1.
  • Необходимо найти максимальный прямоугольник, состоящий из единиц.

Решение задачи на прямой

1:34:19
  • Рассматриваем только прямоугольники, лежащие на прямой.
  • Перебираем прямую и решаем задачу с помощью гистограммы.

Построение гистограммы

1:35:16
  • Строим гистограмму для каждой ячейки, используя информацию о единицах и нулях.
  • Продолжаем столбики, если внизу единица, и удаляем их, если внизу ноль.

Итоговая сложность

1:36:45
  • Задача решается за O(n^2) шагов.
  • На каждом шаге строим новую гистограмму, увеличивая столбик на один предыдущий.

Решение гистограммы

1:37:58
  • Обсуждение алгоритма решения гистограммы за O(n).
  • Объяснение, почему решение выполняется за O(n): каждый элемент один раз помещается в стек и один раз извлекается.
  • Упоминание о возможности использования DP для оптимизации.

Стек с минимумом

1:40:03
  • Описание структуры данных со стеком, операциями добавления и удаления элементов.
  • Идея хранения минимума на префиксе стека вместе с элементом.
  • Пример: при удалении элемента минимум остаётся правильным.

Реализация операций

1:42:11
  • Описание операций pop и push для стека с минимумом.
  • Важность проверки, что стек не пустой, при добавлении элемента.
  • Пример работы операций: добавление элементов, удаление и проверка минимума.

Задача с очередью

1:45:09
  • Постановка задачи: удаление, добавление элементов и определение минимума на очереди.
  • Проблема: при удалении элемента минимум может измениться.
  • Решение: моделирование очереди с помощью двух стеков.

Реализация очереди с двумя стеками

1:46:18
  • Описание работы стеков: добавление в конец и удаление из конца.
  • Перекладывание элементов для поддержания правильного порядка.
  • Реализация операций push и pop для очереди.

Определение минимума на очереди

1:52:24
  • Минимум на очереди определяется как минимум из головы и хвоста.
  • Быстрое пересчитывание минимума при добавлении и удалении элементов.
  • Итоговая сложность операций: амортизированная O(1) на запрос.

Второй способ реализации очереди

1:56:40
  • Введение в второй способ реализации очереди.
  • Использование реальной очереди и отсортированной очереди для меню.
  • Удаление элемента из отсортированной очереди при его удалении из реальной.

Введение в структуру данных

1:57:42
  • Описание структуры, которая хранит минимум и следующий за ним элемент.
  • Пример с элементами: 1, 2, 4, 5.
  • После удаления 1 следующим элементом становится 2.

Добавление и удаление элементов

1:59:05
  • Добавление нового элемента 1 приводит к тому, что он становится ответом на запрос.
  • Необходимость удаления из начала, добавления в конец и удаления из конца.
  • Использование структуры данных DEQ для реализации этих операций.

Реализация операций с DEQ

2:00:20
  • Удаление элемента из DEQ: если первый элемент совпадает с элементом очереди, удаляем из DEQ и очереди; иначе удаляем только из очереди.
  • Добавление элемента в DEQ: пытаемся добавить элемент до тех пор, пока он не станет ответом на некотором подотрезке массива.

Минимум на подотрезках

2:05:31
  • Поиск минимума на всех подотрезках длины k.
  • Реализация с помощью очереди для k элементов.
  • Применение структуры данных для вычисления функций на отрезках, например, произведения матриц.

Стек на минимум

2:08:27
  • Реализация стека на минимум с помощью двух стеков.
  • Добавление элементов в хвост стека и удаление из головы.
  • Пересчёт минимума при перекладывании элементов.

Задача с массивом и запросами

2:14:12
  • Задача: для каждого числа x найти максимальное количество элементов, равных x, среди всех элементов массива.
  • Решение: запоминаем позиции вхождения каждого числа и считаем ответ по формуле.
  • Пример расчёта ответа для числа x: если x входит в массив на позициях i1, i2, ..., ik, то ответ равен i1 * n - i1 - k - 1 + i2 * n - i2 - k - 2 + ... + ik * n - ik - k - 1.

Задача о коровах и стойлах

2:18:00
  • Задача: расположить коров так, чтобы минимальное расстояние между любыми двумя коровами было как можно больше.
  • Использование бинарного поиска для фиксации ответа.
  • Вопрос: можно ли сделать так, чтобы расстояние между коровами было хотя бы x?

Размещение коров

2:18:45
  • Первую корову ставим на число a1.
  • Находим наименьшее i такое, что ai ≥ a1 + x.
  • Если такого i нет, то проигрываем.
  • Если находим, то сдвигаем корову на i.
  • Решение работает за O(n log n) при жадном размещении коров.

Поиск корня функции

2:20:56
  • Нужно найти положительный корень функции x² - x - c = 0.
  • Функция имеет вид x² + √c.

Задача с партиями

2:21:45
  • Есть n партий, для каждой известно количество голосов и стоимость подкупа главаря.
  • Некоторые партии неподкупные.
  • Цель — выбрать партию с максимальным количеством голосов, потратив минимальное количество денег.

Сортировка партий и бин-поиск

2:22:40
  • Сортируем партии по возрастанию или убыванию количества голосов.
  • Используем бин-поиск для нахождения минимального количества денег, необходимого для победы.

Подкуп главаря и переманивание голосов

2:25:07
  • Подкупаем главаря партии, тратя b денег.
  • Остаётся x - b денег для переманивания голосов у других партий.
  • Находим партии с наибольшим количеством голосов и переманиваем их сторонников.

Проверка возможности победы

2:27:01
  • Проверяем, сможем ли мы забрать голоса у партий с максимальным количеством голосов.
  • Если требуемое количество голосов больше x - b, то проигрываем.
  • Если меньше, то можем выиграть, переманивая голоса у других партий.

Завершение алгоритма

2:34:05
  • Забираем лишние голоса у партий с наибольшим количеством голосов.
  • Переманиваем оставшихся сторонников у других партий, пока есть деньги.
  • Цель — сделать нашу партию лидирующей.

Стратегия в партии

2:36:58
  • Если в партии закончились люди, переходим к следующей партии.
  • Пример с партиями: хотим потратить шесть денег, чтобы выиграла партия номер три.
  • Партия два стоит дорого, поэтому её не рассматриваем.

Анализ голосов

2:38:14
  • Если партия выиграет, нужно заплатить восемь денег.
  • Можно потратить шесть денег и сделать партию выигравшей.
  • Цель — получить пять голосов.

Захват голосов

2:39:42
  • Забираем голоса у партии с наибольшим количеством людей.
  • Сначала забираем три голоса, затем четырёх.
  • Важно не допустить равенства количества голосов в партиях.

Алгоритм поиска

2:40:53
  • Используем бинарный поиск для нахождения партии с наибольшим количеством людей.
  • Проходим по всем партиям и находим нужную.
  • Можно использовать два указателя для оптимизации алгоритма.

Задача с массивами

2:41:52
  • Необходимо определить количество вхождений числа в массив.
  • Сортируем массив и используем апп и ловер баунд для ответа.

Минимизация функции

2:43:19
  • Даны два массива: возрастающий и убывающий.
  • Нужно минимизировать максимум из элементов массивов.
  • Функция будет у-немодальной, используем тернарный поиск.

Переполнение

2:49:21
  • Проблема переполнения при умножении.
  • Варианты решения: использовать int128 или аккуратные вычисления.
  • Важно внимательно проверять код на переполнение.

Задача с ультой

2:50:19
  • Оракул кастует ульту, которая забирает у противника а HP и добавляет б.
  • Перезарядка ульты — д секунд.
  • Задача: определить максимальное HP врага, при котором он умрёт через определённое время.

Анализ функции HP

2:52:29
  • Функция f(t) — это количество HP у врага через t секунд.
  • За одно использование ульты HP врага изменяется на -а + б.
  • Если а > б, то врага можно убить с любым количеством HP.

Введение в задачу

2:53:58
  • Рассматривается случай, когда «а» меньше «бц».
  • Цель — определить, сколько HP будет у врага после «т» секунд.

Анализ моментов времени

2:54:13
  • Интересные моменты времени — это моменты использования ульты, когда у врага убавляется HP.
  • В промежутках между ультами HP врага только увеличивается.
  • Интересующие моменты времени имеют вид «т» вида «д умножить на какое-то число ка».

Подсчёт завершённых ультов

2:55:00
  • Подсчитываются ульты, которые успели завершиться до момента «т минус ц».
  • Каждый завершённый ульт наносит урон «а минус бц».
  • Общее количество завершённых ультов: 1 + «т минус ц» / «д», округлённое вниз.

Подсчёт незавершённых ультов

2:57:31
  • Считаются ульты, которые начались, но ещё не завершились.
  • Общее количество незавершённых ультов: «т» / «д» + 1, округлённое вниз.

Определение количества завершённых ультов

2:58:31
  • Количество завершённых ультов обозначается как «икс».
  • Количество полностью завершённых ультов обозначается как «игрек».

Расчёт HP после ультов

2:59:30
  • HP после завершённых ультов: «икс» * «а минус бц» - «игрек» * «а минус бц».
  • HP после незавершённых ультов: сумма арифметической прогрессии.

Расчёт времени запуска ультов

3:02:20
  • Определяется время запуска последнего ульта, который полностью отработал.
  • Время запуска последнего ульта: «игрек» * «д» + 1.

Расчёт количества повторений ультов

3:04:23
  • Количество повторений ультов: максимальное «к», при котором «игрек» * «д» + 1 + «к» <= «т».
  • Формула для расчёта: «к» <= «т» - «игрек» * «д» - 1.

Применение тернарного поиска

3:07:31
  • Используется тернарный поиск для нахождения максимума функции.
  • Устанавливаются границы для «т».

Задача на максимизацию

3:09:13
  • Даны пары чисел u и v.
  • Необходимо найти индексы i, чтобы максимизировать значение суммы u * v / sum(u * v).
  • Обсуждается попытка решения задачи жадным алгоритмом.

Преобразование уравнения

3:10:39
  • Уравнение преобразуется: сумма u * v - x * sum(u * v) ≥ 0.
  • x рассматривается как константа.

Решение с помощью жадного алгоритма

3:11:48
  • Строится новый массив a_i = u_i - x * sum(u_i).
  • Массив сортируется по убыванию.
  • Если сумма первых k элементов больше или равна нулю, задача решена.

Интерактивная задача

3:13:25
  • Дан отсортированный массив, где каждое число встречается ровно по два раза, кроме одного.
  • Необходимо найти это число, сделав не более 42 запросов.
  • Предлагается использовать бинарный поиск с двумя запросами на каждой итерации.

Анализ массива

3:14:39
  • Числа в массиве расположены попарно, затем следует одиночное число.
  • После одиночного числа идут сначала нечётные, затем чётные числа.

Поиск одиночного числа

3:16:28
  • Сравниваются чётные числа: если они равны, одиночное число находится правее; если не равны, то левее.

Задача с нулями и единицами

3:18:21
  • Дан массив из нулей и единиц, где ноль слева, а единица справа.
  • Необходимо найти позицию, где ноль и единица рядом.

Применение бинарного поиска

3:20:26
  • Используется бинарный поиск для сохранения варианта, что слева ноль, а справа единица.
  • Если элемент мид равен единице, сдвигается влево; если равен нулю, сдвигается вправо.

Завершение

3:23:21
  • Подчёркивается, что задача решается с помощью бинарного поиска.
  • Обещание разобрать задачу «Аж» в следующий раз.
Похожие пересказы
Эстония-Молдова- параллель
YOUTUBE 01.12.2025
Поиски. Параллель B'. 03.10.2020.
YOUTUBE 30.11.2025
Д/с «Война миров». Операция «38 параллель». Как Вашингтон разделил Корею
RUTUBE 27.11.2025
Топ Моменты с Twitch | параллель
YOUTUBE 19.11.2025