Задача ШАДа
Мощностью элемента массива назовем сумму максимального элемента, стоящего справа от него и максимального элемента стоящего от него слева.
Мощность крайних элементов будем считать равной 0.
У вас имеется первоначально пустой массив к которому по очереди справа приписываются n целых чисел. На каждом шаге посчитайте и выведите наибольшее значение среди мощностей его элементов.

В первом строке дается число n (1 <= n <= 10^6). Во второй строке дается сам массив.
Вывести n чисел - наибольшие мощности на каждом из n шагов.

Пример-1
3
1 4 5
Ответ 0 0 6
(если кто не понял объясню пример, вам сначала дают число 1, так как в списке у вас одно число то ответ 0, после вам дает число 4, так как всего у вас два числа то ответ 0, после вам дают число 5, можность для числа на второй позиции (4) будет равна 6, так как 1 + 5 = 6)

Пример-2
2 3 3 2
Ответ 0 0 5 5

Пример-3
6
6 5 4 3 2 1
Ответ 0 0 10 10 10 10

Решение:

Решим задача за O(N).
Предположим что вы уже получили i чисел, то есть у вас есть числа a[1], ..., a[i], вы знаете ответ для них равен ans[i].
Теперь вам дает i + 1 ое число, то есть a[i + 1].
В каких случаях ans[i + 1] может стать больше чем ans[i] ?
Очевидно чтобы это произошло в ans[i + 1] должен участвовать число a[i + 1] и какое-то максимальное число слева от позиции i (мы не можем взять число a[i] в ans[i + 1]) пусть это число max_pref, которую легко поддерижвать (смотрите код для лучшего понимания).
Таким образом получаем формулу:
ans[i] = max(ans[i - 1], a[i] + max_pref)

Код в комментариях.

Задача из Яндекса

Дается массив из 0 и 1. Ваша задача выбрать такую позицию нуля, чтобы минимальное расстояние до единицы было максимальным.
Например 100110001
ответом будет позиция 6. 100110001. В задаче нельзя использовать дополнительную память, то есть можете использовать только О(1) дополнительной памяти.

Решение:
Очевидно, что если массив начинается с нуля то претендент на ответ это позиция 0.
Аналогично если массива заканчивается на 0 то претендент на ответ это позиция n - 1.
Теперь разберемся с остальными кейсами,пусть i1, i2, ,..., ik позиции где стоят единички, тогда очевидно претендентом на ответ будет нолик по середине между двумя соседними единицами, например в случае 1000001 ответом будет ноль по середине 1000001.

С идеей разобрались, теперь мы должны подумать как найти ответ без дополнительной памяти.
Конечно если бы знали ближайший слева и ближайший справа единичку для каждой позиции i то смогли бы очень просто решить задачу, но чтобы знать ближайший слева или ближайший справа единичку нам нужно создать дополнительный массив.....

Давайте хранить переменную last_one -которая будет хранить ближайший слева позицию единички от позиции i. (i - цикл по которому идем слева направо)
Если a[i] == 1 то есть встретили единичку, то мы понимаем что до этого единичка была в позиции last_one и нам выгоднее всего выбрать позицию (i + last_one) // 2 (конечно если там ноль)
Таким образом мы смогли решить задачу без дополнительной памяти.
Время работы алгоритма O(n)

Код в комментариях:

Задача из ШАДа.

Так как скоро вступительные в ШАД я решил разобрать вам задачу из 2023 года.
Еще больше полезного материала можно найти здесь

Решение:
В задаче якобы просят построить граф, но по факту вас интересуют только степени вершин. Давайте обойдемся без построения графа.
И так для каждой вершины k мы должны провести ребра к вершинам k-v[k], k - v[k] + 1, ...., k - 1. Проводить ребра явно плохая идея так как получим асимптотику O(n^2). Давайте мыслить в сторону степеней вершин. У каждой вершине на отрезке [k-v[k], k - 1] мы увеличиваем степень на один, а у вершины k степень увеличивается v[k].
Хочется применить дерево фенвика или дерево отрезков ?
- В целом можно но за это у вас снимут пару баллов, так как асимптотика такого решения O(n * logn).

Давайте придумаем решение за O(n).
Заведем массив ans размера n, давайте для каждой вершины k мы обновим массив ans следующим образом:
ans[k - v[k]] += 1
ans[k] -= 1
Этим трюком мы условно говорим " Давай прибавим +1 на отрезке [k-v[k], n - 1] (то есть на суффиксе, а также -1 на отерзке [k, n-1]"

После того как проделали для каждого k (0 <= k < n) мы посчитаем префикс сумму массива ans.
Осталось вывести массив ans[0] + v[0], ans[1] + v[1], ans[2] + v[2], ..., ans[n-1] + v[n-1].
Время работы алгоритма O(n)


Код в комментариях.

Вот и задания на стажировку в Тинькофф! Одну из самых масштабных стажировок сезона, задание на этот раз поприятней: формулировки хотя бы понятны. Поэтому дерзайте, товарищи, открыта куча позиций, не упускаем возможность отлично провести лето: прокачаться в своей карьере и образовании😎😎

Задания в БОТАЛКЕ. Там же можно обсуждать.

Тесты стажирвоки в Тинькофф также вложены в БОТАЛКЕ.
Там же обсуждаем задания с товарищами и любимым админом 🥰

Кстати тесты совсем простые, достаточно чата gpt.

Задача ШБР.

Если этот пост наберет много шаров, выложу фулл разбор.

Решение:
Вся задача сводится к тому, чтобы для i-того дня вы должны взять самую дешевую рыбу на отрезке [i-k+1, i], то есть нужно быстро определять минимум для чисел a[i-k+1], a[i-k+2], ..., a[i] для каждого i.
Конечно можно писать дерево отрезков, а еще легче использовать set/heap, в которых вы будете поддерживать пары {a[i], i} и после сдвига i -> i + 1 вы удалите число {a[i-k], i-k} из set и добавите {a[i], i}, да действительно такое решение будет проходить, но давайте решим задачу за O(N), ведь предыдущее решение работало за O(N*logN).

Оптимальное решение состоит в том, чтобы хранить возрастающий стек.
Подробнее можете почитать здесь.
Храним в нашем возрастающим стеке dq пары чисел {a[i], i}, но таким образом, чтобы первые аргументы пар возрастали, также поддерживаем в стеке инвариант о том, что по второму аргументу у нас находится в окошке длины k.

Код в комментариях.

Вот и разбор алгоритмов на стажировку в Тинькофф! Обязательно делимся с друзьями. Ждём 5 тыс просмотров на ютуб ролике и выкладываем математику.

Смотрим! Смотрим! https://youtu.be/aWqk8-i1bis

Вот и разбор математики на стажировку в Тинькофф! Обязательно делимся с друзьями. Ждём 6 тыс просмотров на ютуб ролике и выкладываем разбор ШБР Яндекса.

Смотрим! Смотрим! https://www.youtube.com/watch?v=98LWuYoXmn4&t=18s

Вот и решения SQL на стажировку в Тинькофф! Обязательно делимся с друзьями. Давайте наберем как можно скорее 500 шэров (поделиться с другом) и расскажу, чего ждать после отбора: когда и кого позовут на собес, чтобы уж точно правильно заполнить анкету и не проморгать!

Обсудить можно в нашей БОТАЛКЕ

Вот и разбор алгоритмов на летнюю школу Яндекса бэкенд-разработки! Обязательно делимся с друзьями. Ждём 20 тыс просмотров на ютуб ролике и выкладываем разбор Яндекс стажировки.

Смотрим! Смотрим! https://www.youtube.com/watch?v=mHZYsmALlMw&t=5s

Вот и долгожданный ролик по стажировкам в Касперовский. Вместе с Максимом разберемся во всех вопросах, связанных со стажировкой. Вышло много инсайдов и лайфхаков. Обязательно делимся с друзьями, ждем 10 тыс просмотров на ролике и выкладываем обзор VK.

Смотрим! Смотрим! https://www.youtube.com/watch?v=Cq2QiFj6y_g&t=1s

Самая сложная задача ШМР.

Решение:
Пусть dp[i] - максимальная сумма, которую можно заработать, если мы рассмотрели первые i букв в строке s.

Тогда как обновить dp[i] ?
- Для начало мы должны выделить подстроку конец, которой будет в i. Пусть эта подстрока [j, i] где j <= i.
Каким требованием должна удовлетворят переменная j ?
По условию задачи длина подотрезка должна быть между l и r отсюда выходит что нам подходят такие j, что l <= i - j + 1 <= r.
Ваша задача в подотрезке [j, j] быстро узнавать минимальную и максимальную букву. (вот не надо сейчас думать в сторону структур). Чтобы хранить min, max букву на подотрезке [j, i] нам достаточно завести две переменные и пока j сдвигается налево от i обновлять эти переменные. (подробнее смотрите на код).

Ну и наконец теперь мы можем обновлять dp[i].
dp[i] = max(dp[i], dp[j-1] + max-min)
Для тех кто не понял этот кусок, dp[j-1] + max-min:
-Здесь говорится, что вы берете оптимальный ответ на отрезке [0, j-1] и оптимальный ответ на отрезке [j, i] в котором ответ max-min.

Так как в задаче еще должны восстановить ответ, мы заводим массив from, где from[i] равен позиции j от которой обновилась dp[i].

Время работы алгоритма O(n^2).

Код в комментариях.

До отборочных в ШАД буквально 7 дней, товарищи, поэтому сегодня в ролике делюсь главным секретом, который подготовит вас к экзаменам за пару недель😎😎 Свои силы сможет попробовать каждый.

Смотрим! Смотрим! https://youtu.be/U7TgvUE3yqA

Вот и реально собеседование на стажера аналитика в Тинькофф. Во всю присылают приглосы, поэтому мониторим почту, товарищи, и смотрим в ролике, чего ждать от собеса.

Смотрим! Смотрим! https://www.youtube.com/watch?v=73cmSsEg2n8

Задача ШАР
Даются числа N и K, а затем массив a целых чисел длины N
Вам нужно найти такую позицию i в массиве а, что 90% всех чисел слева от позиции i меньше чем число a[i], но число i должно быть больше K.

Решение:
N было до 1e6 и решения использованием дерево отрезков или дерево фенвика не проходили по времени, так как код писать нужно на питоне.

Для решения этой задачи нам нужно научиться хранить для каждой позиции i девяноста процентов наименьших чисел слева от позиции i.
Представьте, что вы это сделали для позиции i, то есть у вас есть массив b с 90% наименьших чисел слева от позиции i.
Что происходит с массивом b, когда вы переходите с позиции i на позицию i + 1 ?
Вам нужно добавить число a[i] в массив и удалить несколько максимальных чисел из массива b, так чтобы длина массива b стала (i+1)*0.9.

А с этим нам поможет heap, единственное он не умеет удалять максимальные числа, а умеет удалять только минимальные, так что будем хранить числа со знаком минус!

Общий алгоритм:
Для начало добавим первые K чисел в heap со знаком минус.
После удалим need_delete = K / 10 максимальных чисел из heap, запомним, что мы удалили count_deleted = K/10 чисел.
Теперь начинаем рассматривать числа из массива a начиная с позиции K.
Если a[i] > -heap[0] это означает что число a[i] больше чем 90% чисел и мы нашли ответ.
Иначе мы добавляем в heap число -a[i] и удаляем максимальные числа из heap пока count_deleted не станет равным need_delete.
Время работы алгоритма O(nlogn).
Код в комментариях:

Вот и разбор первого этапа ШАД 2024 года! Обязательно делимся с друзьями, ждем 10 тыс просмотров и разбираем другой вариант. Пока другие варианты можно получить только на наших курсах.

Смотрим! Смотрим! https://www.youtube.com/watch?v=AS4c22KKlgY

Вот и разбор первого этапа ШАД 2024 года! Обязательно делимся с друзьями, ждем 6 тыс просмотров и разбираем следующий вариант. Пока другие варианты и разведку по остальным этапам можно получить только на наших курсах.

Смотрим! Смотрим! https://www.youtube.com/watch?v=bR2jza6gpyU

Вот и задание сегодняшней олимпиады.
Как прошло, товарищи?

Как всегда будет полезно прорешать все задания. Ничего необычного. Все на те темы, которые мы разбирали на наших курсах.

Задача с контеста Яндекс.

Решение:
Во первых заметим, что x[i] <= x[i + 1]. Задача сводится к тому, чтобы выбрать индексы i_1, i_2, ..., i_k, таким образом, что t[i_1] + t[i_2] + .... + t[i_k] + x[i_k] <= T, а также k-> max.

По факту, если бы мы знали до какой позиции Андрею нужно дойти (то есть i_k) то нам нужно было бы взять t[i_k] + x[i_k] и взять самые маленькие t слева от позиции i_k, таким образом чтобы сумма была <=T. Так как мы не знаем оптимальную позицию i_k то куда Андрею стоит идти, нам придется ее перебирать.

Давайте идти слева направо по позициям (то есть for i in range(n)) и предположим, что у вас есть оптимальный набор t-шок слева, я буду хранить их в multiset, (на питоне можно heap).
Пусть сумма оптимальных t-шок (чисел которые лежат в multiset) равна sum_T.
Тогда логично, когда вы в i-той позиции убирать из multiset максимальные числа до тех пор пока sum_T + x[i] > T (так как x[i] возрастают и нам незачем таскать за собой в следующие позиции ненужные t-щки).
Теперь мы оставили такой набор t-щик (замечу мы сделали не хуже для следующих позиций).
У нас 3 случая:
1) sum_T + t[i] + x[i] <= T
2) sum_T + t[i] <= T
3) максимальная t-щка в оптимальном набор больше чем t[i]
Рассмотрим все эти три случая по порядку и обновим ответ/оптимальный набор. (Подробнее смотрите код)

Время работы алгоритма O(NlogN).

Код и полное условие в комментариях.

Олимпиада ШАДа.

Вторая задача олимпиады. Полное условие с тестами оставлю в комментариях.

На плоскости расположены N различных окружностей, любые две либо не пересекаются, либо вложены.
Требуется найти количество подмножеств окружностей мощности K, таких, то их можно упорядочить в цепочку вложенных друг в друга окружностей.

Решение:
Давайте отсортируем окружности по возрастанию радиуса. То есть после сортировки получим r[i] <= r[j] для всех i < j.
В условии сказано, что окружности не пересекаются.

Давайте построим граф на этих окружностях.
Пусть окружности - это вершинки графа. Проведем ориентированное ребро от вершины i в вершину j если окружность j находится внутри i.

Ну такой граф неудобный, так как может содержаться циклы и излишний ребра, давайте лучше построим дерево.
И так построение дерева:
Как мы помним наши окружности отсортированы по возрастанию радиуса. Пусть мы в вершине i, тогда мы проводим ребро к вершине j, если j < i и окружность j находится внутри i, а также у вершины j нет предка.
Если вы будете проводить ребра именно таким образом, то получите дерево.

- А в чем преимущество дерева ?
- В том что если все поддерева вершины i находится строго внутри окружности i.

Теперь как посчитать ответ ?
Мы фиксируем вершинку дерева, пусть это вершина v. Давайте найдем все такие подмножества окружности содержащий v из которых можно построить вложенную цепочку.
Можно легко заметить, что мы должны просто взять подмножество предков вершины v размера k - 1.
Пусть количество предков вершины v равно, тогда в ответ добавляем C(count_parents, k - 1).

Время работы алгоритма O(N ^ 2)
Код в комментариях.

Вот и разбор экзамена ШАД 2024 года!

Смотрим! Смотрим! https://www.youtube.com/watch?v=SxjyPnXFxH0