11:17 Лектор загадывает число от 1 до 100, а слушатели задают вопросы вида «оно больше такого-то?». Оптимально спрашивать про середину текущей области: тогда на каждом шаге останется ровно половина кандидатов. 12:07 Если брать область меньше половины (например, треть), то в «плохой» исход попадёт в два раза больше кандидатов — в худшем случае придётся спрашивать дольше. Важно именно гарантированное число вопросов, поэтому делим пополам.
13:02 Сколько вопросов нужно? После $k$ делений остаётся не больше $100/2^k$ кандидатов. Так как $2^6=64<100$, шести вопросов не хватает (гарантии нет), а $2^7=128\ge 100$ — хватает семи. Значит, число вопросов равно $\lceil\log_2 100\rceil=7$ (двоичный логарифм, округлённый вверх).
13:53 То, что мы делаем, — это и есть бинарный поиск (бинпоиск), а его асимптотика — $O(\log n)$ без указания основания. 14:41 В асимптотике константные множители не пишут: она показывает, как меняется время работы при росте параметра, а константа на рост не влияет. Если $n$ вырос с 100 до 1000 в $10$ раз, то и время у алгоритма $2n$ выросло в $10$ раз — двойка при делении сокращается. 15:35 С логарифмами то же самое: $\log_2 n/\log_3 n$ — константа, не зависящая от $n$ (формула замены основания). Поэтому «логарифм по какому основанию» в асимптотике неважно: основание лишь умножает время на константу.
16:24 Лектор просит слушателей сформулировать общий принцип. 17:36 Ответ: нужна монотонность — свойство, при котором сначала идут «нет», потом «да» (или наоборот). Лектору больше всего нравится такое определение: сначала идут нули для какого-то чекера (проверки), а потом единицы.
18:28 Пример: в отсортированном массиве ищем число $3$. Для каждой позиции проверяем «уже встретилась ли тройка?» (то есть $a_i\ge3$): получаем $0,0,0,1,1,1,\dots$. Любой поиск превращается в поиск первой единицы в массиве из нулей и единиц.
18:28 Общий вид: пока границы не сошлись, берём середину $m$, проверяем условие в $m$ и сдвигаем одну из границ. 19:17 Для неубывающей функции: пусть искомое лежит где-то справа от середины. Мы смотрим на $m$: если значение в ней уже больше искомого — искомое левее, и мы сдвигаем правую границу $r$ на $m$; если меньше — правее, и сдвигаем левую границу $l$ на $m$. 21:07 Середина считается целочисленным делением.
21:53 Лектор договаривается об инварианте: $r$ указывает на «неподходящий» элемент, следующий после подходящих, а $l$ — на подходящий. Дальше: при $a[m]>x$ сдвигаем $r$, при $a[m]\le x$ сдвигаем $l$ (в записи это называется «$l$ — lower bound, $r$ — upper bound»).
lower_bound/upper_bound — это названия результатов двух вариантов поиска, а не самих границ. Надёжный способ не запутаться — сформулировать инвариант: проверка в $l$ «ложна» (или $l=-1$), проверка в $r$ «истинна» (или $r=n$). Цикл идёт, пока $r-l>1$, и на каждом шаге сохраняет это свойство. Когда $r-l=1$, граница между нулями и единицами найдена: она стоит прямо перед $r$.22:43 Задача: проверить, есть ли в отсортированном массиве число (например, тройка). Для этого ищем первую позицию, где $a[i]\ge x$, и смотрим, равно ли там значение $x$. 25:53 Начальные значения: можно взять $l=0$, $r=n$ (лектор привыкла писать так: $r$ указывает за конец массива, то есть на заведомо «неподходящий»); можно $l=-1$, $r=n$ — условия цикла будут чуть другими, но работают оба варианта. Предполагаемый ответ после цикла лежит в одной из границ, и в конце нужно проверить, действительно ли там $x$.
// Условие «a[i] >= x» нулей и единиц: сначала false, потом true.
// Инвариант: a[l] < x (или l = -1), a[r] >= x (или r = n).
int lowerBound(const vector<int>& a, int x) { // первый индекс i с a[i] >= x
int l = -1, r = a.size();
while (r - l > 1) {
int m = (l + r) / 2;
if (a[m] < x) l = m; // m «нулевой» — ответ правее
else r = m; // m «единичный» — ответ в m или левее
}
return r;
}
int upperBound(const vector<int>& a, int x) { // первый индекс i с a[i] > x
int l = -1, r = a.size();
while (r - l > 1) {
int m = (l + r) / 2;
if (a[m] <= x) l = m;
else r = m;
}
return r;
}
int countEqual(const vector<int>& a, int x) { // сколько раз x встречается в отсортированном a
return upperBound(a, x) - lowerBound(a, x);
}Здесь $l=-1$ и $r=n$ — «воображаемые» граничные элементы: слева от массива все проверки «ложны», справа — «истинны». Так цикл не требует разбирать особые случаи: даже если $x$ меньше всех элементов, ответ получится $r=0$, а если больше всех — $r=n$.
lowerBound, upperBound и countEqual сверены со стандартными lower_bound/upper_bound/count на 5000 случайных отсортированных массивах с повторами (в том числе пустых).26:53 Бинпоиск можно делать не только по массиву, но и по функции: вместо $a[m]$ вызываем $f(m)$. Всё работает на монотонных функциях — возрастающих, неубывающих, убывающих, невозрастающих.
27:50 Условие. Даны координаты стойл на прямой и число коров. Нужно расставить коров по стойлам (по одной в стойло) так, чтобы минимальное расстояние между соседними коровами было максимально возможным. 28:51 Например, коровы стоят в трёх стойлах так, что расстояния между ними равны $2,2,5$ — минимальное расстояние $2$; нужно сделать его как можно больше.
29:42 Идея. Мы бинпоиском идём не по стойлам и не по их номерам, а по самому ответу — по значению минимального расстояния $d$. Для фиксированного $d$ вопрос такой: можно ли поставить $k$ коров так, чтобы любые две соседние были не ближе $d$? 30:33 Проверка (чекер) — жадность: ставим первую корову в первое стойло, затем идём по стойлам слева направо и ставим корову в очередное, как только расстояние до последней поставленной стало не меньше $d$. Если удалось поставить хотя бы $k$ коров — расстояние $d$ подходит.
31:19 Пример с записи: при $d=3$ коров можно поставить по трём стойлам; при $d=4$ тоже подходит (расстояние между подобранными стойлами не меньше $4$); при $d=5$ ещё подходит (32:20), а при $d=6$ — уже нет. Так мы «ощупываем» ответ.
34:48 Границы. Левая граница — расстояние $0$ (всегда подходит), правая — на единицу больше максимальной разности координат (заведомо не подходит, если коров не меньше двух). 36:40 Количество шагов бинпоиска — логарифм максимальной разности координат $C=x_{\max}-x_{\min}$, на каждом шаге проверка за один проход по стойлам. Итого $O(m\log C)$, где $m$ — число стойл (в записи сначала спутаны обозначения числа коров и стойл; лектор сама поправляет асимптотику).
37:30 Почему функция монотонна. Если коров можно разместить так, что минимальное расстояние не меньше $d$, то и при любом меньшем $d'<d$ их можно разместить той же расстановкой. Если же при каком-то $d$ нельзя, то нельзя и при всех бо́льших. Значит, проверка даёт «да, да, да, …, нет, нет, нет» — как раз нули и единицы.
// Расставить k коров по стойлам x[0..n-1] (по возрастанию) так, чтобы минимальное расстояние было максимальным.
bool canPlace(const vector<int>& x, int k, int d) { // можно ли расставить k коров с расстояниями >= d
int cnt = 1, last = x[0]; // первую корову — в первое стойло
for (size_t i = 1; i < x.size(); i++)
if (x[i] - last >= d) { cnt++; last = x[i]; } // ставим жадно, как только расстояние достаточно
return cnt >= k;
}
int maxMinDist(const vector<int>& x, int k) { // нужно 2 <= k <= n
int l = 0, r = x.back() - x.front() + 1; // canPlace(l) истинно (d = 0), canPlace(r) ложно
while (r - l > 1) {
int m = (l + r) / 2;
if (canPlace(x, k, m)) l = m;
else r = m;
}
return l;
}maxMinDist сверена с полным перебором всех способов выбрать $k$ стойл из $n$ на 3000 случайных тестах ($2\le k\le n\le 9$): ответы совпали.37:30 До этого все числа были целыми, но границы бинпоиска не обязаны быть целыми — они могут быть вещественными. 38:37 Пример: найти $x$, при котором $x^3=13$ (то есть корень кубический из $13$). 39:26 Вопрос слушателям — как научить компьютер извлекать корень; ответ — бинпоиском. Функция $x^3$ монотонно возрастает.
40:31 Берём заведомо подходящие границы (в записи — от $-1000$ до $1000$; на деле границы зависят от задачи и берутся так, чтобы ответ гарантированно в них лежал). Смотрим на середину: если $m^3$ больше искомого $13$, ответ левее — двигаем правую границу, иначе двигаем левую. 41:22 Если идти только по целым, ответ не найти — он нецелый: нужно делить пополам нецелые границы ($2{,}5$ и так далее), они сами будут дробными.
42:12 Как понять, что поиск пора заканчивать? Условие «$l+1<r$» годилось для целых. Здесь два варианта:
for), например $60$ (лектору кажется нормальным, можно и больше). Лектор советует именно этот вариант: он не зависит от неудачно выбранной точности. 47:48 Число повторений можно ставить хоть $200$ — лишь бы укладываться по времени.// Корень кубический из a (a > 0) и корень квадратный: бинпоиск по вещественным, фиксированное число итераций.
double cbrtBS(double a) {
double l = 0, r = max(1.0, a); // f(x)=x^3 возрастает; на [0, max(1,a)] есть искомая точка
for (int it = 0; it < 100; it++) {
double m = (l + r) / 2;
if (m * m * m < a) l = m;
else r = m;
}
return (l + r) / 2;
}double; дальше середина просто перестаёт отличаться от границы, и цикл безвреден. С фиксированным числом итераций нет риска зацикливания при слишком малом $\varepsilon$.cbrtBS даёт значения, совпадающие с cbrt с точностью $10^{-9}$ для $a=13,\ 0{,}5,\ 2,\ 1000$.47:48 Тернарный поиск знают немногие. 48:35 Нужен он, чтобы искать максимум (или минимум) функции, которая сначала возрастает, потом убывает: т. е. один экстремум, без «полок». Отрезок делят не на две, а на три равные части точками $m_1<m_2$.
49:23 Пусть мы ищем максимум. Сравниваем значения $f(m_1)$ и $f(m_2)$. 50:15 Если $f(m_1)>f(m_2)$, можно положить $r:=m_2$; если $f(m_1)\le f(m_2)$ — положить $l:=m_1$.
51:06 Почему так можно. Нам неизвестно, где точка максимума. Мы знаем лишь, что $m_1$ левее $m_2$ и значение в $m_1$ больше. Возможны два случая: $m_1$ и $m_2$ расположены по разные стороны от точки максимума, либо по одну (обе левее). Но если они обе левее, функция растёт, и значение в $m_1$ не могло бы быть больше. Значит, при $f(m_1)>f(m_2)$ максимум не правее $m_2$. 51:53 А вот левее $m_1$ он может быть, поэтому слева границу двигать нельзя — отбрасываем только то, что правее $m_2$. Симметрично при $f(m_1)\le f(m_2)$ сдвигаем $l$ в $m_1$.
52:47 Точки считаются так: $m_1=l+(r-l)/3$, $m_2=r-(r-l)/3$ (в записи: «прибавить треть» и «отнять треть»). Каждый шаг отрезок сжимается в $3/2$ раза, значит, асимптотика — $O(\log n)$ (основание не важно).
// Точка максимума строго унимодальной (сначала строго растёт, потом строго убывает) функции на [l, r].
template <class F>
double ternaryMax(F f, double l, double r) {
for (int it = 0; it < 100; it++) {
double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (f(m1) > f(m2)) r = m2; // справа от m2 максимума нет
else l = m1; // слева от m1 максимума нет
}
return (l + r) / 2;
}54:01 Тернарный поиск не работает на функциях с «полками» (плато). 55:19 Если оказалось $f(m_1)=f(m_2)$, мы не понимаем, где точка — слева, справа или между. Сдвинув любую границу, можно потерять максимум. 57:04 Итог: тернарный поиск работает только на строго унимодальных функциях — таких, которые строго возрастают до максимума и строго убывают после.
57:58 Метод двух указателей даёт линейную асимптотику там, где наивный перебор отрезков квадратичен. 59:00 Задача. Дан массив неотрицательных чисел; нужно найти подотрезок (подряд идущие элементы) с суммой, равной заданной $S$ (на записи — $12$).
59:57 Идём двумя указателями $l$ и $r$ — концами текущего отрезка. Если сумма меньше $S$ — двигаем правый указатель вправо (отрезок нужно удлинить); если больше — двигаем левый вправо (отрезок нужно укоротить). 1:00:54 Лектор отдельно проговаривает границы: правая граница не включается, левая включается, чтобы пустой отрезок и «последний элемент» не требовали особых случаев. 1:03:39 Сформулируем алгоритм целиком:
// Есть ли в массиве НЕОТРИЦАТЕЛЬНЫХ чисел непустой подотрезок с суммой S? Возвращает [l, r) или {-1,-1}.
pair<int,int> segmentWithSum(const vector<long long>& a, long long S) {
int n = a.size(), l = 0, r = 0; // отрезок [l, r), сумма cur
long long cur = 0;
while (true) {
if (cur == S && r > l) return {l, r};
if (cur < S || r == l) { // не хватает — расширяем вправо (пустой отрезок тоже расширяем)
if (r == n) break;
cur += a[r++];
} else { // cur > S — убираем левый элемент
cur -= a[l++];
}
}
return {-1, -1};
}1:06:53 Нужно понять, что мы не можем «проскочить» ответ. Идея лектора — инвариант: искомые границы всегда не левее текущих: левая граница искомого отрезка находится правее или совпадает с текущей левой, а правая — правее или совпадает с текущей правой. 1:07:57 Доказательство от противного. Допустим, инвариант нарушился.
1:23:57 Асимптотика. Каждый из указателей двигается только вправо и проходит не больше $n$ позиций, поэтому суммарно действий не больше $2n$, то есть $O(n)$.
1:26:26 Указатели не обязаны двигаться в одну сторону. Бывают задачи, где левый указатель стоит в начале массива, правый — в конце, и они идут навстречу друг другу в зависимости от условий. Главное, чтобы сохранялся какой-то инвариант. 1:27:21 Доказательство выше опирается на монотонность суммы по включению: расширили отрезок — сумма не уменьшилась. В записи это называют требованием к операции; если оно нарушено, границы не обязаны двигаться только в одну сторону.
segmentWithSum сверена с перебором всех отрезков на 5000 случайных массивах неотрицательных чисел (в том числе с нулями) и случайных $S$ от $0$ до $12$: результат о существовании совпал, найденный отрезок действительно имеет сумму $S$.3:08:40 Условие. Дан массив и несколько чисел; для каждого нужно сказать, сколько раз оно входит в массив. Идея. Отсортировать массив и использовать пару lower_bound и upper_bound — оба и есть бинпоиск. Ответ: $\text{upper}-\text{lower}$. 3:09:37 Лектор акцентирует: надо понимать, что означает условие в теле цикла. Равные элементы образуют «плато». Нам нужны первая и последняя позиции плато, и разные условия внутри цикла дают разные границы.
3:10:41 Если внутри бинпоиска проверять $a[m]\ge x$, то граница остановится на первом элементе, равном $x$ (или первом большем); если проверять $a[m]>x$ — на первом элементе, который строго больше $x$. 3:11:44 Именно поэтому можно написать два разных поиска — «нестрогий» и «строгий» — и получить разные результаты. Количество вхождений — разность этих двух позиций.
lower(x) = первый индекс i с a[i] ≥ x
upper(x) = первый индекс i с a[i] > x
ответ = upper(x) − lower(x)3:12:44 Условие. Есть единичный квадрат; нужно пройти из левого нижнего угла $(0,0)$ в правый верхний $(1,1)$. Скорость зависит от координаты $x$: пока $x<r$ (параметр $r$ задан), скорость равна $v_1$, дальше — $v_2$. Найти минимальное время. 3:13:34 Идеи слушателей: выгодно идти по прямым; выбрать точку на границе между зонами и идти из начала в неё и из неё в конец; искать её бинарным поиском.
3:15:20 Разбор. Если бы скорость была одинаковой, оптимальный путь — диагональ. Отклонение зависит от отношения скоростей: например, при $v_1\gg v_2$ выгодно пройти больший путь по быстрой зоне, чтобы меньший путь пройти по медленной. 3:16:20 Путь состоит из двух прямолинейных отрезков: от $(0,0)$ до точки $(r,y)$ на границе и от неё до $(1,1)$. Время:
$$T(y)=\frac{\sqrt{r^2+y^2}}{v_1}+\frac{\sqrt{(1-r)^2+(1-y)^2}}{v_2},\qquad y\in[0,1].$$3:18:22 Каждое слагаемое — выпуклая функция от $y$, а сумма выпуклых функций выпукла. 3:19:22 Выпуклая функция — такая, что хорда между любыми двумя точками лежит не ниже графика. Выпуклая функция унимодальна, значит ищем точку минимума тернарным поиском по $y$ на $[0,1]$. 3:20:10 Ответ — время в найденной точке.
3:23:01 Условие. Найти приближённое значение корня из заданного числа. Нужна монотонная функция, по которой идти бинпоиском: 3:23:58 заменяем «найти $x=\sqrt a$» на «найти первое $x$, для которого $x^2\ge a$». Это и есть бинарный поиск по возрастающей функции $F(x)=x^2$ с условием $F(x)\ge a$; точность задаётся условием задачи.
3:24:54 Условие. Вдоль прямой стоят дома; нужно освещать их заданным количеством $k$ фонарей, каждый освещает расстояние $R$ вправо и влево. Найти минимальный радиус $R$, при котором существует расстановка $k$ фонарей, покрывающая все дома.
3:25:46 Идея. Если радиус $R$ подходит, то подходит и любой больший: расстановка та же, зоны только расширились. 3:26:44 Значит, бинарный поиск по ответу $R$ (границы — от $0$ до максимального расстояния между домами). Осталась проверка конкретного $R$.
3:27:53 Проверка. Самый левый неосвещённый дом должен быть освещён каким-то фонарём. 3:28:55 Фонарь, освещающий его, выгодно сдвинуть вправо до тех пор, пока этот дом всё ещё в его зоне: левее домов нет, так что ничего не потеряем. 3:29:45 Поэтому ставим фонарь в точку «координата дома $+R$»; он освещает дома до «координата дома $+2R$». Затем берём следующий неосвещённый дом и повторяем. Если потребовалось не больше $k$ фонарей, радиус подходит.
3:30:42 Лектор разбирает пример: при радиусе $3$ расстановка получается, а при радиусе $2$ (3:31:42) понадобится как минимум три фонаря, то есть радиус $2$ не подходит.
3:32:45 Формально: нужно найти минимальное $R$, для которого существуют $k$ координат, такие, что каждый дом находится хотя бы от одной из них на расстоянии не больше $R$.
covered(R):
used = 0; i = 0
пока i < n:
used += 1
reach = h[i] + 2R // фонарь в h[i]+R
пока i < n и h[i] ≤ reach: i += 1
вернуть used ≤ k
бинпоиск по R: l = 0 (не подходит или предельно), r = h[n−1]−h[0] (подходит);
m = (l+r)/2; если covered(m): r = m, иначе l = m // 100 итераций3:34:46 Условие. Дан массив из $n$ чисел; известно, что по краям стоят $-\infty$ (то есть «за» первым и последним элементом считаем $-\infty$), а соседние элементы различны. Нужно найти локальный максимум: такой индекс $i$, что $a_{i-1}<a_i>a_{i+1}$. 3:36:43 Ответ существует всегда (из-за $-\infty$ по краям), и нужен бинпоиск за $O(\log n)$ — а не линейный проход.
3:38:43 Идея. Берём середину $m$ текущего отрезка и смотрим на соседа справа. 3:40:34 Если сосед справа меньше $a_m$, то пик существует в левой части (включая $m$): слева от $m$ рано или поздно нужно вернуться вниз (на краю $-\infty$), а мы уже стоим выше правого соседа. 3:41:24 Рассуждение через непрерывное движение: мы не можем бесконечно подниматься — мы или упрёмся в пик, или в конце концов опустимся. 3:42:15 Инвариант: на текущем отрезке есть тройка точек «выше слева — выше в середине — ниже справа» (в смысле границ), отрезок сужается, и в конце остаётся три подряд идущих элемента, по которым видно пик. Если сосед справа больше, пик в правой части.
3:43:17 На вопрос о том, нужен ли именно максимум: нет — достаточно любого локального максимума, ответов может быть несколько (3:44:08).
l = 0, r = n − 1 // инвариант: пик в [l, r]
пока l < r:
m = (l + r) / 2
если a[m] < a[m+1]: l = m + 1 // справа выше — пик правее
иначе: r = m // справа ниже — пик в [l, m]
вернуть l3:44:59 Условие. Дан массив чисел (отсортированный). Рассмотрим все попарные абсолютные разности $|a_i-a_j|$, $i<j$. Нужно найти $k$-ю по величине в отсортированном списке этих разностей. 3:45:45 Наивно выписать все разности и отсортировать нельзя — их порядка $n^2$.
3:46:38 Идея. Бинарный поиск по ответу $M$. 3:47:37 Для фиксированного $M$ считаем $W(M)$ — количество пар с $|a_i-a_j|\le M$. Если $M$ — искомая разность, то среди всех разностей ровно $W(M)$ не больше $M$.
3:49:27 Как считать $W(M)$ за $O(n\log n)$. Для каждой точки $x_i$ бинпоиском находим последнюю точку, у которой координата $\le x_i+M$ (первое «слишком далёкое»), и аналогично первую, где координата $\ge x_i-M$. 3:51:19 Все точки между ними — подходящие, их количество прибавляем. 3:52:08 Суммарно $O(n\log n)$ за подсчёт, и ещё внешний бинпоиск по $M$ даёт $O(n\log n\log C)$.
3:53:04 Пример: точки на $1,2,3,4$; попарные разности: $1,1,1,2,2,3$. Единица является ответом для $k=1,2,3$ — одно и то же значение занимает несколько номеров в списке.
3:56:45 Монотонность и условие. $W(M)$ не убывает с ростом $M$. 3:57:34 Нужно найти наименьшее $M$, при котором $W(M)\ge k$: именно такое $M$ — $k$-я разность. Лектор подробно разбирает неверные варианты. Если искать «$W(M)\le k$» — для четвёртой статистики пробное значение $3$ даст ответ $1$ (неверно). Если искать «$W(M)=k$» — для $k=2$ при ответе $1$ получится $W=3$, а условие равенства не выполнено. 3:59:09 Правильный вариант: первое $M$, при котором $W(M)\ge k$.
W(M): для каждого i найти справа бинпоиском последнюю j с a[j] − a[i] ≤ M
сумма (j − i) по всем i // пар (i, j') с i < j' ≤ j
ответ: минимальное M, для которого W(M) ≥ kУлучшение подсчёта — в конце занятия (раздел «Возвращаемся к задаче 7»).
4:01:13 Условие. На прямой лежат $n$ точек. Нужно найти точку $x$, для которой сумма расстояний до всех точек $f(x)=\sum_i |x-x_i|$ минимальна. 4:02:04 Лектор объясняет, какая функция: на левом конце убывает, потом возрастает; значит, подходят и бинпоиск по знаку разности, и тернарный поиск (4:03:56: если функция унимодальна, поиск по «убывает/возрастает» даёт тот же результат, что тернарный).
4:04:55 Но задача проще: ответ — медиана (4:05:54). Если точки отсортированы $x_1\le\dots\le x_n$, то это элемент $x_{(n+1)/2}$ при нечётном $n$; при чётном $n$ подойдёт любая точка между двумя средними. 4:06:52 Ответ — точка, принадлежащая множеству данных (можно искать и тернарным поиском).
4:07:44 Почему медиана. Пусть мы стоим в точке $x$, слева (не правее) от нас $L$ точек, справа $R$. Сдвинем $x$ на $\delta>0$ вправо, не пересекая никакой точки. 4:09:34 Для каждой точки слева слагаемое $|x-x_i|=x-x_i$ становится $x+\delta-x_i$, то есть увеличивается на $\delta$; 4:12:14 для каждой точки справа слагаемое уменьшается на $\delta$. Итого сумма меняется на $\delta(L-R)$. 4:15:06 Если $R>L$ (справа точек больше) — шаг вправо улучшает ответ; 4:16:39 если $L>R$ — выгодно идти влево. Когда мы проходим точку, она «перекладывается» из правых в левые: $R$ уменьшается на $1$, $L$ увеличивается на $1$. 4:18:18 Идти нужно, пока правых больше, значит, остановка — когда $L\ge R$ и $R\ge L$ в смысле $\pm1$: в медиане. 4:19:12 При пяти точках остановимся на третьей (слева и справа по две); при шести можно «гулять» между третьей и четвёртой — сумма постоянна.
4:20:00 Итак, функция сначала убывает, потом плато, потом возрастает, и после этого можно искать минимум тернарным поиском. 4:20:53 На плоскости с манхэттенским расстоянием $|x-x_i|+|y-y_i|$ слагаемые независимы: 4:21:45 $x$-координата и $y$-координата оптимизируются отдельно — берём медиану по каждой оси.
отсортировать x_1 ≤ … ≤ x_n
ответ = x_{⌈n/2⌉} // медиана (для чётного n — любая точка между двумя средними)4:21:45 Условие. Нужно выполнить заказ из $n$ изделий. Нанять одного работника стоит $K$; работник делает одно изделие за время $t$. Если заказ выполнен за время $T$, предприятие платит штраф $T^2$. Какое минимальное количество денег придётся потратить? 4:22:38 Заранее нужно решить, сколько работников $w$ нанять — от этого зависит штраф.
4:23:30 Идея лектора: если нанять слишком много работников — потратим много на найм, слишком мало — заказ будет делаться долго и штраф будет большим; значит, функция «сначала убывает, потом возрастает», и можно искать тернарным поиском по числу работников $w$. 4:24:30 Сколько времени потребуется: $w$ работников делают по $w$ изделий за каждые $t$ единиц времени; если $n$ не кратно $w$, остаток делается ещё за один шаг — поэтому округляем вверх. Время $T=\lceil n/w\rceil\cdot t$, стоимость $\text{cost}(w)=K\cdot w+\left(\lceil n/w\rceil\,t\right)^2$ (4:26:17).
Правильный способ — заметить, что $\lceil n/w\rceil$ принимает только $O(\sqrt n)$ различных значений. Внутри блока, где оно постоянно, время не меняется, а $K\cdot w$ растёт — значит, в блоке выгодно брать наименьшее $w$. Достаточно перебрать только такие $w$.
best = ∞; w = 1
пока w ≤ n:
c = ⌈n / w⌉
best = min(best, K·w + (c·t)²)
w = ⌈n / (c − 1)⌉ если c > 1 иначе n + 1 // первое w, при котором c уменьшится4:27:13 Определение. $\operatorname{mex}$ множества — минимальное целое неотрицательное число, которого в множестве нет. Задача: отвечать на запросы $\operatorname{mex}$ на отрезках массива, причём известно, что суммарное смещение границ запросов невелико (сумма модулей разностей соседних границ запросов мала). 4:28:04 Для одного запроса можно ответить за $O(\text{длина})$ перебором; интересна более быстрая схема.
4:28:53 Идея. Храним не само множество чисел окна, а множество отсутствующих чисел $0,1,\dots,n$ — например, в std::set — и счётчик вхождений каждого числа. 4:29:42 Изначально в множестве отсутствующих лежат все числа $0..n$, счётчики нулевые. 4:30:42 При добавлении числа: если его счётчик был $0$ — удаляем число из множества отсутствующих, затем увеличиваем счётчик. 4:31:30 Тогда $\operatorname{mex}$ — это просто наименьший элемент begin() множества отсутствующих.
4:32:31 Переход к следующему запросу. Окно нового запроса получается из предыдущего сдвигом границ; мы добавляем нужные элементы справа и слева 4:33:33 и удаляем лишние: 4:34:24 при удалении уменьшаем счётчик, и если он стал $0$ — возвращаем число в множество отсутствующих (если двойка осталась в окне, счётчик $>0$ и в множество она не вернётся). 4:35:11 Ответ на запрос — begin() множества. Каждое добавление и удаление стоит $O(\log n)$, всего $O((\text{суммарный сдвиг}+q)\log n)$.
все числа 0..n лежат в set «отсутствуют»; cnt[v] = 0
add(v): если cnt[v] = 0: удалить v из set; cnt[v] += 1
del(v): cnt[v] −= 1; если cnt[v] = 0: вставить v в set
сдвиг окна к [l, r): сначала добавить недостающие справа/слева, потом удалить лишние
mex = первый (наименьший) элемент set4:36:45 Подсчёт $W(M)$ можно ускорить. 4:37:31 Идём по правому концу $j$ слева направо, левый указатель $i$ держим на первой подходящей позиции ($a_j-a_i\le M$): пока $a_j-a_i>M$, увеличиваем $i$. 4:39:20 Когда правая точка сдвигается вправо, граница слева может только увеличиться — это то же монотонное движение двух указателей. Для каждого $j$ прибавляем $j-i$.
4:39:20 Было: внутренний бинпоиск на каждый $i$ — $O(n\log n)$ на подсчёт и $O(n\log n\log C)$ суммарно. Стало: $O(n)$ на подсчёт и $O(n\log C)$ суммарно — теперь внутри бинпоиска нет второго бинпоиска, а только проход по массиву.
W(M): cnt = 0; i = 0
для j от 0 до n−1:
пока a[j] − a[i] > M: i += 1
cnt += j − i
вернуть cnt
бинпоиск по M: наименьшее M с W(M) ≥ kkthDiff) сверена с явным списком всех попарных разностей на 3000 случайных тестах ($n\le9$, значения до $25$): $k$-я разность совпала для всех $k$.4:40:13 В конце лектор предлагает дорешать оставшиеся задачи дома и задавать вопросы по контесту.