Вот и разбор первого этапа ШАД 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.

Задача Яндекса.
Обязательно реши эту задачу если идешь в Яндекс.

Не могу не поделится задачей, которую крутят уже пятый раз подряд.
Задача называется Permutation in String.
В задаче говорится, что дается две строки s1 и s2 и нужно вернуть true если в s2 существует подстрока, которая является перестановкой строки s1.

Единственное собеседующий скажет что в строках могут быть абсолютно любые символы (то есть не только латинские буквы)

Решение:
Первое решение, которое попросят улучшить:
Давайте в словаре d1 посчитаем то сколько раз встречается каждая буква в s1.
Теперь наша задача, найти такой i, что Count(s2[i, i + len(s1) - 1]) = d1.
Для этого мы могли бы хранить второй словарь d2 где будем хранить вхождения букв на подотрезке длины len(s1) и обновлять значения ключей (делаем +1 и -1 к буквам s[i] и s2[i - len(s1)] соответственно)

Сложность такого алгоритма O(n * min(len(s1), m) где m - количество различных букв в строках.
Вы могли подумать откуда тут произведение ?
Произведение возникает из за того что мы на каждом шагу сравниваем две хеш-тиблицы.

Второе решение:
Обойдемся только одной хеш таблицей, чтобы не сравнивать на каждом шаге две хеш таблицы как мы это делали выше.
Посчитаем словарь d1 также как и выше для строки s1.
Теперь проходится по строке s2 окошкой длины len(s1) и мы когда делаем -1 и +1 для букв s2[i] и s2[i - len(s1)] соответственно, таким образом храня в словаре разницу!
Когда значения какого-то ключа обнулилось мы должны удалить этот ключ.
Когда словарь становится пустым (то есть len(d1) == 0) мы нашли нужный подотрезок.
Сложность алгоритма O(n)

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

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

Дается N пар чисел a_i, b_i.
Вы строите N отрезков, где концы i-того отрезка находятся в (a_i, 0) и (1, b_i).
Найти количество отрезков этого множества, которые не пересекаются с другими отрезками.

Например
a = [1, 2, 3, 4, 5]
b = [4, 5, 1, 5, 6]
Ответ 1
Только последний отрезок не пересекается.

Решение:
Давайте отсортируем отрезке по координате a_i.
Теперь подумаем, когда отрезок (a_i, 0), (1, b_i) пересекается с другим отрезком j.
У нас два варианта пересечения
1) a_j <= a_i and b_j >= b_i
2) a_j >= a_i and b_j <= b_i

Пусть мы в i-той позиции, так как мы отсортировали все по a нас интересует максимальный b_j. Максимальный b_j можно хранить в отдельной переменной во время обхода обновляя. Таким образом мы должны просто проверить правда ли max_b >= b_i.

Аналогично давайте пройдемся справа налево, но уже будем хранить минимальный b справа. Для каждой позиции i проверяем min_b <= b_i.

Асимптотика O(N logN).

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

Академия Бэкенда Тинькофф

Бесплатная образовательная программу по бэкенд-разработке. Длительность курса -1.5 года.
Обучение будет проходить по 4 направлением.
Java, Golang, Python, Scala.

С программой Академии бэкенда можно ознакомиться здесь. Конкурировать с такой программой может только ШАД по направлению инфраструктура больших данных.
Чего только стоит "Компьютерные сети", "Асинхронный обмен сообщениями", "Балансировка нагрузки", SRE курс. Не каждый опытный разработчик знает такие технологии.

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

Также нужно понимать, что это Тинькофф и программа бесплатная, значит велик шанс столкнуться с некоторым количеством кринжа. Например, ручная проверка всех ДЗ: понятно, что кураторам никто особо не платит, у них своих дел куча, поэтому ревьюить особо не будут. Или например препод отказывается делать записи занятий, мол их должны посещать. Или не любит, когда к нему пишут в тг аккаунты без реальных имен и фамилий) Про порой мало качественный материал, наверное, и говорить не стоит: опять же у преподавателей особо мотивации нет, вдобавок на последние занятия никто обычно не ходит.

Кому подходит Академия ?
-Отлично подходит для тех кто уже работает бэкенд разработчиком и хочет быстро апгрейдить свои знания, и сильно повысить зарплату. Занятость спокойно позволяет совмещать учебу и работу.

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

-Для тех кто решил поменять стэк/направление.


Поступление.
-Заполнить анкету до 22 июля. Как заполнить смотрим здесь.
-Написать 4-5 часовой контест по алгоритмам. Кстати подготовиться к нему поможет наш курс по алгоритмам.
-Языковая секция: вам предложат практическое задание, которое нужно выполнить на языке программирования, выбранном для курса.

Пример 2023 года по алгоритмическому контесту. Задачи чуть легче чем отбор на стажировку.
Пример 2023 года языковой секции на GO.

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

Но пробовать однозначно стоит!

Таблица задач с алго собесов Яндекса со всей актуальной информацией: ссылка на leetcode, частота, процентов принятия.
Именно эти задачи будут подробно разобраны на нашем предстоящем курсе по алгоритмам (код + видео) как бонус!

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

Задача Яндекса.
Дается строка, найти наибольший палиндромную подстроку.

Давно такая задача не встречалась на собесах, но недавно дали на собесе в яндекс.
Решение:

Наверное самое тупое решение - это зафиксировать длину подотрезка, пусть это число len. Теперь надо перебрать начало отрезка длины len, то есть зафиксировать [i, i + len - 1]. После нужно проверить правда ли этот подотрезок палиндром. Такое решение займет O(n^3) времени.

Скорее всего после такого решения вас не позовут дальше.....
Теперь обсудим решение, которое примут.
Переберем длину подотрезка len, после переберем начало подотрезка.
То есть зафиксировав len и i, мы получим отрезок [i, i + len - 1]. Остается вопрос, а как узнать правда ли подотрезок палиндром.
Во первых необходимо, что буквы s[i] и s[i + len - 1] были равны (иначе подотрезок точно не палиндром)
Во вторых нам важно чтобы подотрезок [i + 1, i + len - 2] был палиндром.
Если мы рассматриваем подотрезки по возрастанию длин (то есть по len), то по факту информацию о том, что подотрезок [i + 1, i + len - 2] является палиндромом, мы уже давно посчитали.
Пусть dp[l][r] = 1 если отрезок [l, r] палиндром.
В таком случае мы говорим, что dp[i][i + len - 1] = 1, если s[i] == s[i + len - 1] и dp[i + 1][i + len - 2] = 1.

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

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

Эту задачу видел в Yandex Leetcode. Так что, если вы готовитесь к собеседованию, то имеет смысл прорешать Yandex Leetcode.

Также мы запускаем два курса по алгоритмам.
Если задачи на БП, два указателя, одномерные дпшки для тебя простые, то на продвинутом курсе по алгоритмам мы прорешаем ~200 задач на БОР, ДП по поддеревьям, игры и стратегии, bit manipulation.....

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

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

Задания в БОТАЛКЕ. Там же можно обсуждать. Ждем 500 шэров и делаем разбор!

Продолжаем обновлять и расширять раздел алгоритмов на нашем сайте: добавили задачи с алго собесов VK group, Авито, обновили задачи Яндекса и добавили контесты с решениями!

Все для вас, товарищи, сохраняйте, пользуйтесь на здоровье и обязательно делитесь с друзьями такой годнотой!

А если вы хотите добавить задачи на сайт или поделиться тестовыми заданиями (на любую позцию), то пишите @vice22821, сочтемся!

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

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

Задача бэкенд Тинькофф (Hard).

Представьте, что у вас есть матрица из 0 и 1 размера n * m, где n * m <= 1e6. В матрице на каждом столбце есть ровно один непрерывный отрезок из единичек.
Например:
0 1 1
0 0 1
1 0 0

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

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

Ваша задача за минимальное количество действий получить хорошую расстановку.

Решение:
Пусть, dp[i][j] - минимальное количество операций необходимое, чтобы получить хорошую расстановку для столбцов 1, 2, 3, ..., i, но так, чтобы отрезок из единиц на i-том столбце покрывал позицию (i, j).

Давайте научимся обновлять дпшку. Пусть на i том столбце единички изначально находятся в позициях [s, e] (У нас же единички - это непрерывный отрезок по каждому столбцу).
Как обновляется dp[i][j], если s <= j <= e ?
Конечно же через min(dp[i - 1][s], dp[i - 1][s + 1], ..., dp[i - 1][e])
Отлично, а как быть с остальными j, которые лежат вне отрезка [s, e] ?

Давайте начнем наш отрезок двигать вверх, то есть наш отрезок [s, e] переместиться в [s - 1, e - 1], потом в [s-2, e-2] и так далее. По факту мы ходим скользящим окном и нам надо быстро узнавать минимум на отрезке для dp[i - 1], например, когда отрезок переместился на [s-1, e-1] мы обновляем нашу дпшку через 1 + min(dp[i-1][s-1], dp[i-1][s], ..., dp[i-1][e-1]).

Задача сводится к тому, чтобы быстро находить минимум на в скользящем окне.
ДО - не рекомендуется писать, так как будет TL.

Монотонный стек или Sparce Table самое то!
Если хочешь научиться решать такие задачи то приходи на курсы Алгоритмы Хард, которые начнутся 28 июля.

Асимптотика алгоритма O(n*m)
Код в комментариях

от и возможность для школьников познакомиться с работой в IT! Открыт набор в онлайн-лагерь «IT-дайвинг» — бесплатную программу от VK Education для учеников 7-11 классов. Здесь можно будет узнать о востребованных цифровых направлениях — от ML и разработки до креатива и управления проектами. А еще участников ждет работа над кейсами в выбранном направлении, обратная связь и мастер-классы от экспертов VK. Чтобы попасть в программу, нужно зарегистрироваться в чат-боте до 11 августа.

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

Задания в БОТАЛКЕ. Там же можно обсуждать. Ждем 500 шэров и делаем разбор!