Задача ШБР.

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

Решение:
Вся задача сводится к тому, чтобы для 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).

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

Задача ШАДа.

Эта задача была на собеседовании в ШАД в 2023 году. Я считаю задача одна из коварных по сравнению с остальными, подумайте над этой задачей и думаю вы поймете о чем я.

Задача:
Дается массив из целых чисел, вернуть True, если можно за один swap двух чисел сделать массив отсортированным (по возрастанию или по убыванию). В массиве могут быть повторы.

Решение: (Настоятельно рекомендую перед этим подумать)

Будем предполагать, что в массиве нет повторов. (вы можете убрать подряд идущие элементы из массива за O(n) двумя указателями)


Пойдем с конца, возьмем отсортированный массив по возрастанию и сделаем swap двух чисел, как будет выглядит массив (например если рисовать график) ?

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

Назовем позиции i особенными если, a[i - 1] > a[i].

-Если особенных позиций больше 2 ответ False.

-Если такой позиции ровно 1, то вы должны сделать swap чисел a[i] и a[i - 1] и проверяете что массив отсортирован по возрастнанию.

-Если таких позицй ровно 2 (пусть это i1 и i2) то вы должны сделать swap чисел a[i1 - 1], a[i2] после проверить, что массив стал отсортированный.


Мы упустили случай, когда массив изначально был отсортирован по убыванию. Но у нас есть решение (функция) выше, нам надо вызывать ровно это же решение, умножив все элементы массива на -1.

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

Для тех кто готовится к собесу в ШАД оставлю полезные задачи, которые встречались в прошлом году.

https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/29
https://news.1rj.ru/str/algoses/33
https://news.1rj.ru/str/algoses/37
https://news.1rj.ru/str/algoses/90
https://news.1rj.ru/str/algoses/95

Алгоритмы в Ai-Masters

AI Masters — это двухгодичный курс, который можно сравнить с ШАД. Обучение на курсах AI Masters действительно качественное, и это прекрасная возможность получить дополнительные полезные знания за два года.

Подробный пост о этапах поступление написано здесь.

В Ai-Masters алгоритмы встретите в основном на экзамене, и там будет всего одна задача. Эта задача значительно отличается от тех, с которыми можно столкнуться на собеседованиях или в ШАД (за исключением олимпиады ШАД, которую запустили в 2024 году). Также алгоритмы будут на собесе, но по опыту прошлых лет там простетские вопросы в духе: какие знаете сортировки, посчитайте сложность алгоритма.

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

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

С примером и разбором одной из задач можно ознакомиться здесь.

И так как все таки подготовиться.
Как уже сказал вам необходима прочная база. Подготовка к алгоритмическому собеседованию или в ШАД отлично подходит. Подробнее про подготовку можно почитать здесь и здесь

Теперь готовимся к AI-Masters (кстати эта подготовка вам поможет к собесу и в какую-то хорошую HFT компанию).

Так как задачи по алгоритмам попадаются разные, то нужно перестраховаться и прокачать алгоритмы по следующим темам.
* Многомерное ДП и дп по подмножествам
* Дп по поддеревьям
* Теория игр
* Эйлерев путь
* Планарные графы, независимое множества (графы)
* Структуры данных (ДО, Фенвик, Sparce Table)
* Хеши

Также рекомендую решать региональные олимпиады школьников - первых двух задач будет достаточно.

Все темы выше проходят в стандартном курсе по алгоритмам, например в МФТИ, лекции которые можно найти в ютубе.
Задачи на эти темы спокойно можно найти в informatics.