Набор в ШАД продолжается, а тем временем мы с Егором Хайруллиным 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, а справа — на С??:
![](https://habrastorage.org/webt/gw/hz/bj/gwhzbjtpsnjkilhxsncggilwkly.jpeg)
То есть если матрица 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, а справа — на С??:
![](https://habrastorage.org/webt/gw/hz/bj/gwhzbjtpsnjkilhxsncggilwkly.jpeg)
То есть если матрица 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. В графе есть связная компонента хотя бы из трёх вершин — то есть между ними есть хотя бы два ребра
![](https://habrastorage.org/webt/m4/zn/yn/m4znynky8vcxtkpcx8idzxy-jb8.jpeg)
Ответим на два вопроса:
Оба варианта исключены. Потому что среди этих пяти вершин нет ни одной, не соединённой с четырьмя другими — что противоречит условию задачи.
А какие варианты не исключены? Может существовать ещё только одна вершина, соединённая с одной или несколькими из первоначальных трёх:
![](https://habrastorage.org/webt/if/er/li/iferlihnlfhc-klsaisvfaetlwe.jpeg)
То есть самый «насыщенный» рёбрами граф, который может получиться, — это граф K?. Он состоит из четырёх вершин, каждая из которых соединена с тремя другими (всего шесть рёбер):
![](https://habrastorage.org/webt/rn/hs/oi/rnhsoiru-m8ght4tel7maxpszjw.jpeg)
Итак, если в графе есть связная компонента хотя бы из трёх вершин, то рёбер в таком графе может быть не больше шести.
Случай 2. В графе нет связных компонент хотя бы из трёх вершин
Даже если в графе в принципе есть рёбра, они не могут иметь общих вершин:
![](https://habrastorage.org/webt/5j/dr/ic/5jdricpjmiarn1xrsynsaezea7w.jpeg)
Сколько тогда может быть рёбер? Не больше 20, потому что из условия известно, что в графе 40 вершин, а из них можно выбрать не больше 20 пар вершин, соединённых рёбрами.
Итак, в первом случае рёбер не больше шести, во втором — не больше 20. В инвертированной задаче требовалось найти максимальное число рёбер, поэтому ответ: 20.
Возврат к исходной задаче
Чтобы вернуться к исходной задаче, снова поменяем местами понятия «ребро» и «отсутствие ребра». Получается, что в таком графе не может быть более 20 отсутствующих рёбер.
Сколько вообще может быть рёбер в графе на n вершинах? n(n-1)/2, для нашего графа это 40 ? 39/2 = 780.
Мы выяснили, что отсутствующих рёбер не более 20. В условии требуется найти минимальное число рёбер. Получается, что оно равняется 780 – 20 = 760.
Ответ: 760
Поэтому мы применим трюк — инвертируем задачу: заменим каждое ребро на отсутствие ребра, а каждое отсутствие ребра — на ребро. Каким будет новое условие задачи?
Дан граф с 40 вершинами без петель и кратных рёбер. Известно, что среди любых 5 вершин найдётся одна, не соединённая с четырьмя остальными. Каково минимально возможное число «отсутствий» рёбер в этом графе?
Минимальное число «отсутствий» рёбер тривиально выражается через максимальное число рёбер. При таком условии рёбер в графе будет немного.
Разберём два случая.
Случай 1. В графе есть связная компонента хотя бы из трёх вершин — то есть между ними есть хотя бы два ребра
![](https://habrastorage.org/webt/m4/zn/yn/m4znynky8vcxtkpcx8idzxy-jb8.jpeg)
Ответим на два вопроса:
- Может ли ещё где-то в графе быть хотя бы одно ребро?
- Могут ли в графе быть ещё две вершины, соединённые с одной или с несколькими из первоначальных трёх?
Оба варианта исключены. Потому что среди этих пяти вершин нет ни одной, не соединённой с четырьмя другими — что противоречит условию задачи.
А какие варианты не исключены? Может существовать ещё только одна вершина, соединённая с одной или несколькими из первоначальных трёх:
![](https://habrastorage.org/webt/if/er/li/iferlihnlfhc-klsaisvfaetlwe.jpeg)
То есть самый «насыщенный» рёбрами граф, который может получиться, — это граф K?. Он состоит из четырёх вершин, каждая из которых соединена с тремя другими (всего шесть рёбер):
![](https://habrastorage.org/webt/rn/hs/oi/rnhsoiru-m8ght4tel7maxpszjw.jpeg)
Итак, если в графе есть связная компонента хотя бы из трёх вершин, то рёбер в таком графе может быть не больше шести.
Случай 2. В графе нет связных компонент хотя бы из трёх вершин
Даже если в графе в принципе есть рёбра, они не могут иметь общих вершин:
![](https://habrastorage.org/webt/5j/dr/ic/5jdricpjmiarn1xrsynsaezea7w.jpeg)
Сколько тогда может быть рёбер? Не больше 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 переберём все элементы справа и найдём искомый результат. Какова будет временнaя сложность такого брутфорса? Для каждого из n элементов (в худшем случае) нужно будет совершить n действий, так что сложность такого решения составит О(n?). Это недостаточно хорошо.
Свойства структуры
Одно из требований к искомому элементу — он должен быть больше или равен заданному. Это повод вспомнить алгоритм бинарного поиска, который решает похожую задачу: находит в сортированном массиве первый элемент, больше или равный заданному. Сложность алгоритма — логарифмическая: O(log n).
Однако пока непонятно, как воспользоваться алгоритмом бинарного поиска. И если это сделать, возникнет другая проблема: для i мы найдём результат быстро, а для последующих шагов (в каждом случае i – 1) нам потребуется перестраивать заново структуру, поверх которой будет работать бинарный поиск. Такой процесс может оказаться медленным — мы каждый раз будем тратить линейное время от числа элементов. Важно, чтобы структуру не требовалось перестраивать.
Заметим, что структуры для i и i – 1 будут построены на похожем наборе элементов. Для i это все элементы, начиная с i + 1 до j включительно, а для i – 1 — те же самые элементы плюс элемент i. Тем самым структуру не нужно каждый раз перестраивать с нуля — достаточно научиться её перестраивать инкрементально. Запомним это.
Визуальное представление
Изобразим наш массив визуально, чтобы высота столбца соответствовала значению элемента. Некоторые элемента справа от i-го будут больше него, некоторые — меньше:
![](https://habrastorage.org/webt/4c/on/sd/4consdqsno75qutlvps4sor8lxu.jpeg)
Будем двигаться вправо, поочерёдно рассматривая элементы. Числа < a? нас заведомо не интересуют.
![](https://habrastorage.org/webt/pv/wr/zm/pvwrzmyqkl5dstxuafpqpv9anag.jpeg)
Предположим, один из элементов оказался ? a?. Тогда он может оказаться ответом для выбранного i.
![](https://habrastorage.org/webt/vm/tn/uh/vmtnuhycgrgups1gd8aremeun90.jpeg)
Посмотрим на следующие элементы. Если очередной элемент меньше того, который мы отметили, то он нам тоже не интересен (даже если при этом он ? a?).
![](https://habrastorage.org/webt/8t/zc/mr/8tzcmretxtqc1mjfgvu93csl-oy.jpeg)
Если мы встретим элемент, больше или равный отмеченному ранее, то отметим и его тоже — теперь уже он будет для нас кандидатом на ответ. И так далее.
![](https://habrastorage.org/webt/e_/t4/dg/e_t4dgfjuisp-92iviiqxwmzgn8.jpeg)
Возрастающая последовательность элементов, отмеченных синим цветом, — это сортированный массив, найти в котором нужный элемент можно уже упомянутым бинарным поиском.
Вернёмся к вопросу, как перестраивать такой массив при переходе от i к i – 1. Как мы уже выяснили, нужно уметь делать это инкрементально. Рассмотрим два случая.
1) a? ? a???
Если мы начинаем движение по массиву от i – 1, то первым же кандидатом на ответ будет i-й элемент — а все остальные кандидаты останутся прежними. Мы почти не потратим лишнего времени на перестроение — только добавим a?.
![](https://habrastorage.org/webt/cy/dh/dr/cydhdrx-e4eg_3d9dljddk_id3g.jpeg)
2) a? > a???
В зависимости от значения a??? первые несколько кандидатов могут перестать быть кандидатами:
![](https://habrastorage.org/webt/zq/hb/ci/zqhbcilwt-eqkjoy4ta2z8xj8f0.jpeg)
В обоих случаях, получив массив кандидатов, мы выполним по нему бинарный поиск. Это и будет нашим решением. Оценим его сложность.
Оценка сложности и выбор способа хранения
Во-первых, узнаем, сколько памяти нам потребуется. Мы должны будем хранить элементы, отмеченные синим. Таких элементов не может быть больше, чем всего элементов в массиве — n. Значит, сложность по памяти — O(n).
Во-вторых, какова сложность по времени? Нам потребуется запускать два вида операций:
Итак, сложность всех операций первого вида (бинарных поисков) составит O(n log n), а всех операций второго вида (перестроений массива) — O(n). Значит, сложность решения целиком — O(n log n). Это нас вполне устраивает.
Решение
Для каждого i = n..1:
Например, для элемента i переберём все элементы справа и найдём искомый результат. Какова будет временнaя сложность такого брутфорса? Для каждого из n элементов (в худшем случае) нужно будет совершить n действий, так что сложность такого решения составит О(n?). Это недостаточно хорошо.
Свойства структуры
Одно из требований к искомому элементу — он должен быть больше или равен заданному. Это повод вспомнить алгоритм бинарного поиска, который решает похожую задачу: находит в сортированном массиве первый элемент, больше или равный заданному. Сложность алгоритма — логарифмическая: O(log n).
Однако пока непонятно, как воспользоваться алгоритмом бинарного поиска. И если это сделать, возникнет другая проблема: для i мы найдём результат быстро, а для последующих шагов (в каждом случае i – 1) нам потребуется перестраивать заново структуру, поверх которой будет работать бинарный поиск. Такой процесс может оказаться медленным — мы каждый раз будем тратить линейное время от числа элементов. Важно, чтобы структуру не требовалось перестраивать.
Заметим, что структуры для i и i – 1 будут построены на похожем наборе элементов. Для i это все элементы, начиная с i + 1 до j включительно, а для i – 1 — те же самые элементы плюс элемент i. Тем самым структуру не нужно каждый раз перестраивать с нуля — достаточно научиться её перестраивать инкрементально. Запомним это.
Визуальное представление
Изобразим наш массив визуально, чтобы высота столбца соответствовала значению элемента. Некоторые элемента справа от i-го будут больше него, некоторые — меньше:
![](https://habrastorage.org/webt/4c/on/sd/4consdqsno75qutlvps4sor8lxu.jpeg)
Будем двигаться вправо, поочерёдно рассматривая элементы. Числа < a? нас заведомо не интересуют.
![](https://habrastorage.org/webt/pv/wr/zm/pvwrzmyqkl5dstxuafpqpv9anag.jpeg)
Предположим, один из элементов оказался ? a?. Тогда он может оказаться ответом для выбранного i.
![](https://habrastorage.org/webt/vm/tn/uh/vmtnuhycgrgups1gd8aremeun90.jpeg)
Посмотрим на следующие элементы. Если очередной элемент меньше того, который мы отметили, то он нам тоже не интересен (даже если при этом он ? a?).
![](https://habrastorage.org/webt/8t/zc/mr/8tzcmretxtqc1mjfgvu93csl-oy.jpeg)
Если мы встретим элемент, больше или равный отмеченному ранее, то отметим и его тоже — теперь уже он будет для нас кандидатом на ответ. И так далее.
![](https://habrastorage.org/webt/e_/t4/dg/e_t4dgfjuisp-92iviiqxwmzgn8.jpeg)
Возрастающая последовательность элементов, отмеченных синим цветом, — это сортированный массив, найти в котором нужный элемент можно уже упомянутым бинарным поиском.
Вернёмся к вопросу, как перестраивать такой массив при переходе от i к i – 1. Как мы уже выяснили, нужно уметь делать это инкрементально. Рассмотрим два случая.
1) a? ? a???
Если мы начинаем движение по массиву от i – 1, то первым же кандидатом на ответ будет i-й элемент — а все остальные кандидаты останутся прежними. Мы почти не потратим лишнего времени на перестроение — только добавим a?.
![](https://habrastorage.org/webt/cy/dh/dr/cydhdrx-e4eg_3d9dljddk_id3g.jpeg)
2) a? > a???
В зависимости от значения a??? первые несколько кандидатов могут перестать быть кандидатами:
![](https://habrastorage.org/webt/zq/hb/ci/zqhbcilwt-eqkjoy4ta2z8xj8f0.jpeg)
В обоих случаях, получив массив кандидатов, мы выполним по нему бинарный поиск. Это и будет нашим решением. Оценим его сложность.
Оценка сложности и выбор способа хранения
Во-первых, узнаем, сколько памяти нам потребуется. Мы должны будем хранить элементы, отмеченные синим. Таких элементов не может быть больше, чем всего элементов в массиве — 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???, то удалим их из массива кандидатов.