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

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

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

Кстати тесты совсем простые, достаточно чата 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

Я в шоке! Академия Авито объявила набор... Мне стыдно, товарищи, что советовал поступать в этот содом, простите... Подобно Эдипу мне предстоит выколоть глаза и отправиться в изгнание. Прощайте! Оставляю вас Михаилу Абрамовичу. О том, что случилось в новом ролике..

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

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

Дается массив a из целых положительных чисел, а также число k. Найти максимальный по длине подотрезок в котором разница между максимальным и минимальным элементом будет не больше k.

Решение:
Наум, конечно, приходит два указателя. Это, кстати, хорошая идея.

И так, думаем в сторону двух указателей. Всё по шаблону, перебираем правый край отрезка 0 <= r < n, для каждого такого r будем искать оптимальный l, в котором разница максимального и минимального элемента не больше k.
Можно легко понять, что для каждого следующего r его оптимальный l будет не левее чем l для r - 1.

Осталось только быстро находить минимум и максимум на отрезке... Да, конечно, можно попытаться написать дерево отрезков, что позволит вам находить мин/макс за логарифм, но, к сожалению, задачу так не засчитают, нужно научиться за константу находить.

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

И так для решения - этой задачи нужно было хранить два стека. (ГПТ кстати хорошо решает такую задачу :))

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

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

Задача AI-Masters.

Постройте алгоритм, который получает на вход дерево и за линейное время определяет, есть ли в нем совершенное паросочетание, то есть множество ребер, такое, что каждая вершина графа встречается ровно в одном ребре множества.

Решение:

Определение совершенного паросочетания дано в условии задачи.

Давайте подвесим дерево за вершину 1 и запустим dfs от этой вершины.
Стандартный dfs принимает два аргумента v, p - вершина в котором находимся и вершина от которой пришли в вершину v.
Но давайте еще передавать булеву переменную bool_took, которая равна true если вершина взята в паросочетание и false иначе.
Таким образом дфс выглядит следующим образом dfs(int v, int p, int bool_took), наша функция вернет true если поддерво вершины v при условии bool_took, можно сделать совершенным паросочетанием.

Вот мы вошли в функцию dfs, что мы должны сделать если bool_took = false и что мы должны сделать если bool_took = true ?

- Если bool_took = true нужно запустить dfs от всех детей вершины v с параметром bool_took = false и если все вызовы dfs вернули true то мы в свою очередь тоже можем вернуть true.

- Если bool_took = false нужно выбрать какого-то ребенка вершины v и взять их в паросочетание, пусть эта вершина u, тогда если dfs(u, v, true) вернул true и dfs(to, v, false) вернул true для всех детей to не равным u мы можем спокойно возвращать true.

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

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