Набор в ШАД продолжается, а тем временем мы с Егором Хайруллиным Mikari разобрали ещё несколько задач из письменного экзамена 2019 года (первая часть — здесь). Сначала пробуйте свои силы и постарайтесь решить задачи самостоятельно — например, номер 8 вообще не содержит формул, к решению можно прийти простыми рассуждениями и рисованием на листочке.
Найдите предел:
Видеоразбор
Для квадратичной вещественной матрицы A размера n x n и вектора v ∈ ℝⁿ положим:
Пусть матрица A такова, что dim W(A, v) = n для любого v ≠ 0. Какова максимально возможная размерность U(A)?
Видеоразбор
Вещественнозначная функция f определена на отрезке [a; b] (b – a ≥ 4) и дифференцируема на нём. Докажите, что найдётся точка x₀ ∈ (a; b), для которой
Видеоразбор
Дан граф с 40 вершинами без петель и кратных рёбер. Известно, что среди любых 5 вершин найдётся одна, соединённая с четырьмя остальными. Каково минимально возможное число рёбер в этом графе?
Видеоразбор
В массиве A длины n для каждого i-го элемента найдите такой ближайший к нему j-й элемент, что j > i и aj ≥ 2aᵢ.
Видеоразбор
Задача 5. Предел и вероятности
Найдите предел:
Видеоразбор
Текстовый разбор
Прежде всего необходимо понять физический смысл этого выражения. Когда мы видим одну пятую в каких-то степенях, к тому же перемножающуюся друг с другом и умножающуюся на биномиальный коэффициент, то сразу начинаем думать об испытаниях Бернулли. В частности, об испытаниях Бернулли с вероятностью успеха одна пятая.
Выражения в скобках с такими степенями похожи на вероятность того, что в первые n раз нам повезло, а в следующие k-n раз нам не везло. Умножение на биномиальный коэффициент намекает, что n раз были успешными. Однако у нас используется не С из k по n, а C из k-1 по n-1:
Запишем выражение по-другому, чтобы и в степенях использовались не k и n, а k-1 и n-1:
Часть выражения до умножения на одну пятую в конце — это вероятность того, что среди k-1 испытаний ровно n-1 успешны. Биномиальный коэффициент отвечает за выбор тех n-1 позиций, которые среди k-1 испытаний оказались успешны. C учётом этого стоящая в конце одна пятая означает, что на k-м испытании будет успех. Получается, выражение целиком означает, что на k-м испытании достигается n-й по счёту успех.
Вспомним, что в искомом пределе только что записанное нами выражение стоит под знаком суммы:
Вместе с суммой выражение равняется вероятности того, что n-й успех случился где-то между n-м и 5n-м испытанием. Так как раньше n-го испытания успех произойти не мог, то сумму
можно охарактеризовать как вероятность того, что n-й успех случился не позже 5n-го испытания.
Ищем пределы вероятности
Итак, мы поняли физический вероятностный смысл того, что стоит под знаком предела. Постараемся понять, как считать предел.
Введём независимые одинаково распределённые случайные величины:
каждая из которых распределена как номер первого успеха в серии испытаний Бернулли с вероятностью p = ⅕. Тогда номер n-го успеха равняется сумме этих величин.
А поскольку ранее мы охарактеризовали сумму
как вероятность, что n-й успех случился не позже 5n-го испытания, то
Мы свели исходное выражение к более понятным вероятностным сущностям.
Вспоминаем предельные теоремы
Итак, в наших рассуждениях появилась вероятность неравенства с суммой, причём нам надо найти её предел при n → ∞. Это повод вспомнить одну из предельных теорем. Можно вспомнить закон больших чисел, но он никак не характеризует вероятности.
Вспомним центральную предельную теорему (ЦПТ). Она говорит о том, как распределено некоторое выражение, в котором участвует сумма. Если точнее, ЦПТ говорит, что:
где имеется в виду сходимость по распределению. В числителе стоит разность суммы и математического ожидания любой из наших случайных величин, умноженного на n. В знаменателе — корень из дисперсии, умноженной на n; cправа — нормальное распределение с параметрами 0 и 1.
Взглянем одновременно на выражение из левой части ЦПТ и на неравенство, предел вероятности которого нам нужно найти:
Приведём неравенство справа к виду, похожему на выражение слева.
Мы имеем право добавить знаменатель в неравенство, если он положителен:
Равняется ли матожидание пяти? Мы можем вспомнить или догадаться, что да, матожидание номера первого успеха в серии испытаний Бернулли с вероятностью успеха ⅕ — это 5. Действительно, в среднем при вероятности ⅕ нам будет везти на каждой 5-й попытке.
То есть можно выразить искомый предел как
Выражение, стоящее слева в неравенстве, согласно ЦПТ стремится к нормальному распределению с параметрами 0 и 1. Следовательно:
Ответ: ½
Выражения в скобках с такими степенями похожи на вероятность того, что в первые n раз нам повезло, а в следующие k-n раз нам не везло. Умножение на биномиальный коэффициент намекает, что n раз были успешными. Однако у нас используется не С из k по n, а C из k-1 по n-1:
Запишем выражение по-другому, чтобы и в степенях использовались не k и n, а k-1 и n-1:
Часть выражения до умножения на одну пятую в конце — это вероятность того, что среди k-1 испытаний ровно n-1 успешны. Биномиальный коэффициент отвечает за выбор тех n-1 позиций, которые среди k-1 испытаний оказались успешны. C учётом этого стоящая в конце одна пятая означает, что на k-м испытании будет успех. Получается, выражение целиком означает, что на k-м испытании достигается n-й по счёту успех.
Вспомним, что в искомом пределе только что записанное нами выражение стоит под знаком суммы:
Вместе с суммой выражение равняется вероятности того, что n-й успех случился где-то между n-м и 5n-м испытанием. Так как раньше n-го испытания успех произойти не мог, то сумму
можно охарактеризовать как вероятность того, что n-й успех случился не позже 5n-го испытания.
Ищем пределы вероятности
Итак, мы поняли физический вероятностный смысл того, что стоит под знаком предела. Постараемся понять, как считать предел.
Введём независимые одинаково распределённые случайные величины:
каждая из которых распределена как номер первого успеха в серии испытаний Бернулли с вероятностью p = ⅕. Тогда номер n-го успеха равняется сумме этих величин.
А поскольку ранее мы охарактеризовали сумму
как вероятность, что n-й успех случился не позже 5n-го испытания, то
Мы свели исходное выражение к более понятным вероятностным сущностям.
Вспоминаем предельные теоремы
Итак, в наших рассуждениях появилась вероятность неравенства с суммой, причём нам надо найти её предел при n → ∞. Это повод вспомнить одну из предельных теорем. Можно вспомнить закон больших чисел, но он никак не характеризует вероятности.
Вспомним центральную предельную теорему (ЦПТ). Она говорит о том, как распределено некоторое выражение, в котором участвует сумма. Если точнее, ЦПТ говорит, что:
где имеется в виду сходимость по распределению. В числителе стоит разность суммы и математического ожидания любой из наших случайных величин, умноженного на n. В знаменателе — корень из дисперсии, умноженной на n; cправа — нормальное распределение с параметрами 0 и 1.
Взглянем одновременно на выражение из левой части ЦПТ и на неравенство, предел вероятности которого нам нужно найти:
Приведём неравенство справа к виду, похожему на выражение слева.
Мы имеем право добавить знаменатель в неравенство, если он положителен:
Равняется ли матожидание пяти? Мы можем вспомнить или догадаться, что да, матожидание номера первого успеха в серии испытаний Бернулли с вероятностью успеха ⅕ — это 5. Действительно, в среднем при вероятности ⅕ нам будет везти на каждой 5-й попытке.
То есть можно выразить искомый предел как
Выражение, стоящее слева в неравенстве, согласно ЦПТ стремится к нормальному распределению с параметрами 0 и 1. Следовательно:
Ответ: ½
Задача 6. Размерности
Для квадратичной вещественной матрицы A размера n x n и вектора v ∈ ℝⁿ положим:
Пусть матрица A такова, что dim W(A, v) = n для любого v ≠ 0. Какова максимально возможная размерность U(A)?
Видеоразбор
Текстовый разбор
Перед нами страшноватая на вид задача по линейной алгебре. Постараемся лучше понять её условие.
Свойства W
Обратим внимание на W. Это довольно интересное подпространство. Оно инвариантно относительно A: если линейную комбинацию векторов v, Av, A²v и так далее умножить на A, то останется линейная комбинация таких векторов. А раз любое инвариантное содержащее v подпространство содержит и все Аᵏv, то получается, что W — это минимальное содержащее v подпространство.
И мы знаем из условия, что это минимальное инвариантное подпространство, содержащее любой ненулевой вектор из нашего пространства, имеет размерность n. Следовательно, любое ненулевое инвариантное подпространство тоже имеет размерность n — другими словами, совпадает с ℝⁿ.
Проще говоря, у линейного оператора А есть лишь два инвариантных подпространства — нулевое и ℝⁿ.
Что нам известно об инвариантных подпространствах над ℝ?
То есть наше подпространство W — это либо ℝ, либо ℝ².
В условии спрашивается, какой может быть максимально возможная размерность U(A).
В случае W = ℝ матрица имеет размерность 1x1, то есть состоит из одного числа, а линейный оператор является умножением на это число. Условие, что все матрицы в U должны коммутировать с A (XA = AX), всегда выполняется, поскольку все числа коммутируют друг с другом. Следовательно, U(A) — подпространство размерности 1.
Случай ℝ²
Но что если W совпадает с ℝ², в котором нет инвариантных подпространств размерности 1?
Вспомним, что такое инвариантное подпространство размерности 1. Это прямая, которая под действием линейного оператора переходит в саму себя — то есть её направляющий вектор умножается на число. Другими словами, это линейная оболочка некоторого собственного вектора: <w>.
И наоборот, если есть собственный вектор, то порождённая им прямая — это инвариантное подпространство размерности 1.
В нашем ℝ² нет инвариантных подпространств размерности 1, то есть нет собственных векторов. Другими словами, характеристический многочлен матрицы не имеет корней над полем действительных чисел, а имеет два сопряжённых комплексных корня — z и z̅:
Над полем комплексных чисел ℂ матрица A диагонализуется c числами z и z̅ на диагонали. Обозначим полученную матрицу как B:
Обозначим через Uℂ(B) пространство всех комплексных матриц 2x2, которые коммутируют с B. Нетрудно проверить, что каждая из матриц в Uℂ(B) будет диагональной:
Значит, размерность Uℂ(B) над пространством комплексных чисел будет равна двум:
Как от B перейти к A, а от ℂ — к ℝ?
Переход от B к A
Предположим, матрица Y коммутирует с B:
Вспомним, что B получается из A заменой базиса, то есть:
Умножим и правую, и левую часть равенства слева на C, а справа — на С⁻¹:
То есть если матрица Y коммутирует с B, то матрица CYC⁻¹ коммутирует с A. Другими словами, линейное преобразование, переводящее Y в CYC⁻¹, осуществляет изоморфизм:
В частности, они имеют одинаковую размерность 2:
То есть если бы мы рассматривали A как комплексную матрицу, то пространство коммутирующих с ней комплексных матриц имело бы размерность 2.
Переход от ℂ к ℝ
Уравнение XA=AX можно считать однородной системой линейных уравнений на элементы матрицы X. Вспомним, что размерность пространства решений однородной системы уравнений, коэффициенты A которой заданы над ℝ, — одинаковое над ℂ и ℝ. Эта размерность зависит только от ранга матрицы системы, а при переходе от ℂ к ℝ ранг не меняется.
Таким образом:
Мы выяснили, что для случая W = ℝ размерность U равняется единице, для случая W = ℝ² — двойке. В условии спрашивалось, какой может быть максимально возможная размерность. Значит, ответ — 2.
Ответ: 2
Свойства W
Обратим внимание на W. Это довольно интересное подпространство. Оно инвариантно относительно A: если линейную комбинацию векторов v, Av, A²v и так далее умножить на A, то останется линейная комбинация таких векторов. А раз любое инвариантное содержащее v подпространство содержит и все Аᵏv, то получается, что W — это минимальное содержащее v подпространство.
И мы знаем из условия, что это минимальное инвариантное подпространство, содержащее любой ненулевой вектор из нашего пространства, имеет размерность n. Следовательно, любое ненулевое инвариантное подпространство тоже имеет размерность n — другими словами, совпадает с ℝⁿ.
Проще говоря, у линейного оператора А есть лишь два инвариантных подпространства — нулевое и ℝⁿ.
Что нам известно об инвариантных подпространствах над ℝ?
Теорема.
Над ℝ всякий линейный оператор имеет инвариантное подпространство размерности 1 или 2.
То есть наше подпространство W — это либо ℝ, либо ℝ².
В условии спрашивается, какой может быть максимально возможная размерность U(A).
В случае W = ℝ матрица имеет размерность 1x1, то есть состоит из одного числа, а линейный оператор является умножением на это число. Условие, что все матрицы в U должны коммутировать с A (XA = AX), всегда выполняется, поскольку все числа коммутируют друг с другом. Следовательно, U(A) — подпространство размерности 1.
Случай ℝ²
Но что если W совпадает с ℝ², в котором нет инвариантных подпространств размерности 1?
Вспомним, что такое инвариантное подпространство размерности 1. Это прямая, которая под действием линейного оператора переходит в саму себя — то есть её направляющий вектор умножается на число. Другими словами, это линейная оболочка некоторого собственного вектора: <w>.
И наоборот, если есть собственный вектор, то порождённая им прямая — это инвариантное подпространство размерности 1.
В нашем ℝ² нет инвариантных подпространств размерности 1, то есть нет собственных векторов. Другими словами, характеристический многочлен матрицы не имеет корней над полем действительных чисел, а имеет два сопряжённых комплексных корня — z и z̅:
Над полем комплексных чисел ℂ матрица A диагонализуется c числами z и z̅ на диагонали. Обозначим полученную матрицу как B:
Обозначим через Uℂ(B) пространство всех комплексных матриц 2x2, которые коммутируют с B. Нетрудно проверить, что каждая из матриц в Uℂ(B) будет диагональной:
Значит, размерность Uℂ(B) над пространством комплексных чисел будет равна двум:
Как от B перейти к A, а от ℂ — к ℝ?
Переход от B к A
Предположим, матрица Y коммутирует с B:
Вспомним, что B получается из A заменой базиса, то есть:
Умножим и правую, и левую часть равенства слева на C, а справа — на С⁻¹:
То есть если матрица Y коммутирует с B, то матрица CYC⁻¹ коммутирует с A. Другими словами, линейное преобразование, переводящее Y в CYC⁻¹, осуществляет изоморфизм:
В частности, они имеют одинаковую размерность 2:
То есть если бы мы рассматривали A как комплексную матрицу, то пространство коммутирующих с ней комплексных матриц имело бы размерность 2.
Переход от ℂ к ℝ
Уравнение XA=AX можно считать однородной системой линейных уравнений на элементы матрицы X. Вспомним, что размерность пространства решений однородной системы уравнений, коэффициенты A которой заданы над ℝ, — одинаковое над ℂ и ℝ. Эта размерность зависит только от ранга матрицы системы, а при переходе от ℂ к ℝ ранг не меняется.
Таким образом:
Мы выяснили, что для случая W = ℝ размерность U равняется единице, для случая W = ℝ² — двойке. В условии спрашивалось, какой может быть максимально возможная размерность. Значит, ответ — 2.
Ответ: 2
Задача 7. Неравенство для производной
Вещественнозначная функция f определена на отрезке [a; b] (b – a ≥ 4) и дифференцируема на нём. Докажите, что найдётся точка x₀ ∈ (a; b), для которой
Видеоразбор
Текстовый разбор
Когда речь идёт о доказательстве существования x₀ на интервале и упоминается дифференцируемость, то вспоминается теорема Лагранжа о промежуточном значении и теорема о промежуточном значении непрерывной функции.
Вспомним также, что:
Если рассмотреть сложную функцию arctg f(x), то её производная в точке x₀ будет равна
Приведём неравенство из условия задачи к похожему виду, разделив его на 1 + f²(x₀). Это выражение не меньше единицы, поэтому в ноль не обращается.
Это можно переписать в таком виде:
И мы должны доказать, что существует точка x₀, в которой это неравенство выполняется — то есть арктангенс в этой точке не может круто идти вверх. Звучит правдоподобно, ведь арктангенс — в целом довольно пологая функция. Но давайте придумаем строгое доказательство.
Итак, раз мы имеем дело с производной, самое время применить теорему Лагранжа о промежуточном значении. Запишем ее в удобном нам виде:
Поскольку арктангенс лежит на интервале (-π/2, π/2), то левая часть равенства не может быть большой:
Следовательно:
Из условия мы знаем, что b – a ≥ 4. Значит,
Выбирая для них x₀ из теоремы Лагранжа, получаем:
что и требовалось доказать.
Вспомним также, что:
Если рассмотреть сложную функцию arctg f(x), то её производная в точке x₀ будет равна
Приведём неравенство из условия задачи к похожему виду, разделив его на 1 + f²(x₀). Это выражение не меньше единицы, поэтому в ноль не обращается.
Это можно переписать в таком виде:
И мы должны доказать, что существует точка x₀, в которой это неравенство выполняется — то есть арктангенс в этой точке не может круто идти вверх. Звучит правдоподобно, ведь арктангенс — в целом довольно пологая функция. Но давайте придумаем строгое доказательство.
Итак, раз мы имеем дело с производной, самое время применить теорему Лагранжа о промежуточном значении. Запишем ее в удобном нам виде:
Поскольку арктангенс лежит на интервале (-π/2, π/2), то левая часть равенства не может быть большой:
Следовательно:
Из условия мы знаем, что b – a ≥ 4. Значит,
Выбирая для них x₀ из теоремы Лагранжа, получаем:
что и требовалось доказать.
Задача 8. Рёбра в графе
Дан граф с 40 вершинами без петель и кратных рёбер. Известно, что среди любых 5 вершин найдётся одна, соединённая с четырьмя остальными. Каково минимально возможное число рёбер в этом графе?
Видеоразбор
Текстовый разбор
Поскольку в графе много вершин и рёбер, представить его визуально будет непросто, нас это запутает.
Поэтому мы применим трюк — инвертируем задачу: заменим каждое ребро на отсутствие ребра, а каждое отсутствие ребра — на ребро. Каким будет новое условие задачи?
Минимальное число «отсутствий» рёбер тривиально выражается через максимальное число рёбер. При таком условии рёбер в графе будет немного.
Разберём два случая.
Случай 1. В графе есть связная компонента хотя бы из трёх вершин — то есть между ними есть хотя бы два ребра
Ответим на два вопроса:
Оба варианта исключены. Потому что среди этих пяти вершин нет ни одной, не соединённой с четырьмя другими — что противоречит условию задачи.
А какие варианты не исключены? Может существовать ещё только одна вершина, соединённая с одной или несколькими из первоначальных трёх:
То есть самый «насыщенный» рёбрами граф, который может получиться, — это граф K₄. Он состоит из четырёх вершин, каждая из которых соединена с тремя другими (всего шесть рёбер):
Итак, если в графе есть связная компонента хотя бы из трёх вершин, то рёбер в таком графе может быть не больше шести.
Случай 2. В графе нет связных компонент хотя бы из трёх вершин
Даже если в графе в принципе есть рёбра, они не могут иметь общих вершин:
Сколько тогда может быть рёбер? Не больше 20, потому что из условия известно, что в графе 40 вершин, а из них можно выбрать не больше 20 пар вершин, соединённых рёбрами.
Итак, в первом случае рёбер не больше шести, во втором — не больше 20. В инвертированной задаче требовалось найти максимальное число рёбер, поэтому ответ: 20.
Возврат к исходной задаче
Чтобы вернуться к исходной задаче, снова поменяем местами понятия «ребро» и «отсутствие ребра». Получается, что в таком графе не может быть более 20 отсутствующих рёбер.
Сколько вообще может быть рёбер в графе на n вершинах? n(n-1)/2, для нашего графа это 40 ⋅ 39/2 = 780.
Мы выяснили, что отсутствующих рёбер не более 20. В условии требуется найти минимальное число рёбер. Получается, что оно равняется 780 – 20 = 760.
Ответ: 760
Поэтому мы применим трюк — инвертируем задачу: заменим каждое ребро на отсутствие ребра, а каждое отсутствие ребра — на ребро. Каким будет новое условие задачи?
Дан граф с 40 вершинами без петель и кратных рёбер. Известно, что среди любых 5 вершин найдётся одна, не соединённая с четырьмя остальными. Каково минимально возможное число «отсутствий» рёбер в этом графе?
Минимальное число «отсутствий» рёбер тривиально выражается через максимальное число рёбер. При таком условии рёбер в графе будет немного.
Разберём два случая.
Случай 1. В графе есть связная компонента хотя бы из трёх вершин — то есть между ними есть хотя бы два ребра
Ответим на два вопроса:
- Может ли ещё где-то в графе быть хотя бы одно ребро?
- Могут ли в графе быть ещё две вершины, соединённые с одной или с несколькими из первоначальных трёх?
Оба варианта исключены. Потому что среди этих пяти вершин нет ни одной, не соединённой с четырьмя другими — что противоречит условию задачи.
А какие варианты не исключены? Может существовать ещё только одна вершина, соединённая с одной или несколькими из первоначальных трёх:
То есть самый «насыщенный» рёбрами граф, который может получиться, — это граф K₄. Он состоит из четырёх вершин, каждая из которых соединена с тремя другими (всего шесть рёбер):
Итак, если в графе есть связная компонента хотя бы из трёх вершин, то рёбер в таком графе может быть не больше шести.
Случай 2. В графе нет связных компонент хотя бы из трёх вершин
Даже если в графе в принципе есть рёбра, они не могут иметь общих вершин:
Сколько тогда может быть рёбер? Не больше 20, потому что из условия известно, что в графе 40 вершин, а из них можно выбрать не больше 20 пар вершин, соединённых рёбрами.
Итак, в первом случае рёбер не больше шести, во втором — не больше 20. В инвертированной задаче требовалось найти максимальное число рёбер, поэтому ответ: 20.
Возврат к исходной задаче
Чтобы вернуться к исходной задаче, снова поменяем местами понятия «ребро» и «отсутствие ребра». Получается, что в таком графе не может быть более 20 отсутствующих рёбер.
Сколько вообще может быть рёбер в графе на n вершинах? n(n-1)/2, для нашего графа это 40 ⋅ 39/2 = 780.
Мы выяснили, что отсутствующих рёбер не более 20. В условии требуется найти минимальное число рёбер. Получается, что оно равняется 780 – 20 = 760.
Ответ: 760
Задача 9. Индекс ближайшего превосходящего элемента
В массиве A длины n для каждого i-го элемента найдите такой ближайший к нему j-й элемент, что j > i и aj ≥ 2aᵢ.
Видеоразбор
Текстовый разбор
Для начала придумаем решение в лоб — брутфорс, перебор или ещё какой-нибудь вариант: достаточно простой, но хоть как-нибудь решающий задачу.
Например, для элемента i переберём все элементы справа и найдём искомый результат. Какова будет временнáя сложность такого брутфорса? Для каждого из n элементов (в худшем случае) нужно будет совершить n действий, так что сложность такого решения составит О(n²). Это недостаточно хорошо.
Свойства структуры
Одно из требований к искомому элементу — он должен быть больше или равен заданному. Это повод вспомнить алгоритм бинарного поиска, который решает похожую задачу: находит в сортированном массиве первый элемент, больше или равный заданному. Сложность алгоритма — логарифмическая: O(log n).
Однако пока непонятно, как воспользоваться алгоритмом бинарного поиска. И если это сделать, возникнет другая проблема: для i мы найдём результат быстро, а для последующих шагов (в каждом случае i – 1) нам потребуется перестраивать заново структуру, поверх которой будет работать бинарный поиск. Такой процесс может оказаться медленным — мы каждый раз будем тратить линейное время от числа элементов. Важно, чтобы структуру не требовалось перестраивать.
Заметим, что структуры для i и i – 1 будут построены на похожем наборе элементов. Для i это все элементы, начиная с i + 1 до j включительно, а для i – 1 — те же самые элементы плюс элемент i. Тем самым структуру не нужно каждый раз перестраивать с нуля — достаточно научиться её перестраивать инкрементально. Запомним это.
Визуальное представление
Изобразим наш массив визуально, чтобы высота столбца соответствовала значению элемента. Некоторые элемента справа от i-го будут больше него, некоторые — меньше:
Будем двигаться вправо, поочерёдно рассматривая элементы. Числа < aᵢ нас заведомо не интересуют.
Предположим, один из элементов оказался ≥ aᵢ. Тогда он может оказаться ответом для выбранного i.
Посмотрим на следующие элементы. Если очередной элемент меньше того, который мы отметили, то он нам тоже не интересен (даже если при этом он ≥ aᵢ).
Если мы встретим элемент, больше или равный отмеченному ранее, то отметим и его тоже — теперь уже он будет для нас кандидатом на ответ. И так далее.
Возрастающая последовательность элементов, отмеченных синим цветом, — это сортированный массив, найти в котором нужный элемент можно уже упомянутым бинарным поиском.
Вернёмся к вопросу, как перестраивать такой массив при переходе от i к i – 1. Как мы уже выяснили, нужно уметь делать это инкрементально. Рассмотрим два случая.
1) aᵢ ≤ aᵢ₋₁
Если мы начинаем движение по массиву от i – 1, то первым же кандидатом на ответ будет i-й элемент — а все остальные кандидаты останутся прежними. Мы почти не потратим лишнего времени на перестроение — только добавим aᵢ.
2) aᵢ > aᵢ₋₁
В зависимости от значения aᵢ₋₁ первые несколько кандидатов могут перестать быть кандидатами:
В обоих случаях, получив массив кандидатов, мы выполним по нему бинарный поиск. Это и будет нашим решением. Оценим его сложность.
Оценка сложности и выбор способа хранения
Во-первых, узнаем, сколько памяти нам потребуется. Мы должны будем хранить элементы, отмеченные синим. Таких элементов не может быть больше, чем всего элементов в массиве — n. Значит, сложность по памяти — O(n).
Во-вторых, какова сложность по времени? Нам потребуется запускать два вида операций:
Итак, сложность всех операций первого вида (бинарных поисков) составит O(n log n), а всех операций второго вида (перестроений массива) — O(n). Значит, сложность решения целиком — O(n log n). Это нас вполне устраивает.
Решение
Для каждого i = n..1:
Например, для элемента i переберём все элементы справа и найдём искомый результат. Какова будет временнáя сложность такого брутфорса? Для каждого из n элементов (в худшем случае) нужно будет совершить n действий, так что сложность такого решения составит О(n²). Это недостаточно хорошо.
Свойства структуры
Одно из требований к искомому элементу — он должен быть больше или равен заданному. Это повод вспомнить алгоритм бинарного поиска, который решает похожую задачу: находит в сортированном массиве первый элемент, больше или равный заданному. Сложность алгоритма — логарифмическая: O(log n).
Однако пока непонятно, как воспользоваться алгоритмом бинарного поиска. И если это сделать, возникнет другая проблема: для i мы найдём результат быстро, а для последующих шагов (в каждом случае i – 1) нам потребуется перестраивать заново структуру, поверх которой будет работать бинарный поиск. Такой процесс может оказаться медленным — мы каждый раз будем тратить линейное время от числа элементов. Важно, чтобы структуру не требовалось перестраивать.
Заметим, что структуры для i и i – 1 будут построены на похожем наборе элементов. Для i это все элементы, начиная с i + 1 до j включительно, а для i – 1 — те же самые элементы плюс элемент i. Тем самым структуру не нужно каждый раз перестраивать с нуля — достаточно научиться её перестраивать инкрементально. Запомним это.
Визуальное представление
Изобразим наш массив визуально, чтобы высота столбца соответствовала значению элемента. Некоторые элемента справа от i-го будут больше него, некоторые — меньше:
Будем двигаться вправо, поочерёдно рассматривая элементы. Числа < aᵢ нас заведомо не интересуют.
Предположим, один из элементов оказался ≥ aᵢ. Тогда он может оказаться ответом для выбранного i.
Посмотрим на следующие элементы. Если очередной элемент меньше того, который мы отметили, то он нам тоже не интересен (даже если при этом он ≥ aᵢ).
Если мы встретим элемент, больше или равный отмеченному ранее, то отметим и его тоже — теперь уже он будет для нас кандидатом на ответ. И так далее.
Возрастающая последовательность элементов, отмеченных синим цветом, — это сортированный массив, найти в котором нужный элемент можно уже упомянутым бинарным поиском.
Вернёмся к вопросу, как перестраивать такой массив при переходе от i к i – 1. Как мы уже выяснили, нужно уметь делать это инкрементально. Рассмотрим два случая.
1) aᵢ ≤ aᵢ₋₁
Если мы начинаем движение по массиву от i – 1, то первым же кандидатом на ответ будет i-й элемент — а все остальные кандидаты останутся прежними. Мы почти не потратим лишнего времени на перестроение — только добавим aᵢ.
2) aᵢ > aᵢ₋₁
В зависимости от значения aᵢ₋₁ первые несколько кандидатов могут перестать быть кандидатами:
В обоих случаях, получив массив кандидатов, мы выполним по нему бинарный поиск. Это и будет нашим решением. Оценим его сложность.
Оценка сложности и выбор способа хранения
Во-первых, узнаем, сколько памяти нам потребуется. Мы должны будем хранить элементы, отмеченные синим. Таких элементов не может быть больше, чем всего элементов в массиве — n. Значит, сложность по памяти — O(n).
Во-вторых, какова сложность по времени? Нам потребуется запускать два вида операций:
- Бинарный поиск для каждого i. Эту операцию мы осуществим не более чем n раз — для каждого элемента в массиве длины n. Сложность каждого бинарного поиска — O(log n), значит всего мы потратим O(n log n).
- Перестроение массива при переходе от i к i – 1. Здесь, как мы выяснили выше, потребуется либо добавить в массив один элемент, либо удалить из него некоторое число элементов. Возможно, их будет много — всё зависит от значения aᵢ₋₁. На то, чтобы их удалить, может потребоваться много времени.
Поэтому мы будем хранить «синие» элементы в обратном порядке — начиная с того, у которого в исходном массиве был самый большой индекс. Очевидно, этот же элемент будет самым большим и по своему значению. Тогда все добавления и удаления мы будем осуществлять в конце массива.
Каждая такая операция (добавление или удаление) выполняется за константу, а не за линейное время, как при работе с произвольным фрагментом массива. Общее число операций не превысит n, поэтому суммарная сложность перестроений массива будет равна О(n).
Итак, сложность всех операций первого вида (бинарных поисков) составит O(n log n), а всех операций второго вида (перестроений массива) — O(n). Значит, сложность решения целиком — O(n log n). Это нас вполне устраивает.
Решение
Для каждого i = n..1:
- Выполним бинарный поиск по массиву, который назовём массивом кандидатов. Будем искать элемент, больше либо равный 2aᵢ.
- Если aᵢ₋₁ ≤ aᵢ, то запишем aᵢ в конец массива кандидатов.
- Если aᵢ₋₁ > aᵢ и в массиве кандидатов есть элементы меньше, чем aᵢ₋₁, то удалим их из массива кандидатов.