Алгоритмы - Собеседования, Олимпиады, ШАД

Все задачи, которые встретились на собесе ШАДа 2024 года.

1) Дается массив/строка и число k. Найти максимальный по длине подотрезок в котором <=k различных элементов.
Решать нужно за O(n) а памятью O(min(k, количество различных букв)). Также могли спросить как работает словарь если использовали словарь.

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

3) Даются две строки s, p. Найти все позиции в строке s, что подстрока s[i: i + len(p)] является анаграммой для строки p.
Решать за линию использую словарь. Некоторых спрашивали как работает словарь.

4) Даются два массива a, b. Длина массива b равно k. Найти количество подпоследовательностей массива a, что они равны массиву b.
То есть найти количество различных множеств (i1, i2, ..., ik), что a[i1] = b[0], a[i2] = b[1], ..., a[ik] = b[k-1]
-Решение за квадрат удовлетворит собеседующих.

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

(Если вам попалась другая задача то поделитесь условием в комментариях)

Полный цикл отбора в Яндекс (Бэкенд 2024)

Продолжаем сопровождать наших выпускников и радовать вас инсайдами, товарищи.

Вступительный контест
Подавался на бэкенд С++, сначала скинули ссылку на контест. Задания нашел тут, просто прорешал заранее и сдал. Первую задачу мне решил ГПТ. Вторая задача была на хэш-таблицу + строки. Третья задача была сортировка + префикс сумма. Четвертая задача была одной из самых сложных, но решалась через префикс суммы. Пятая задача была на алгоритм БОР.

Кстати, товарищи, на курсе бэкенд разработка вы найдете подробный разбор (видео + код) этих задач.

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

Алгоритмическая секция 1
Задача 1: дается массив из 0 и 1. Нужно за один проход поставить все нули в начало массива. Задача баян, в группе выкладывали задачу.
Задача 2: дается массив 0 и 1. Найти длину максимального подотрезка, состоящего из 1, после удаления ровно одного нуля. Решил быстро, и в запасе оставалось еще 20 минут.
Собеседующий решил просто так не сидеть и дал 3 задачу.
Задача 3: дается строка, найти максимальную по длине подотрезок, состоящий не более чем из k различных букв. Тоже какая-то баянистая задача на два указателя...
Остается 5 минут, и собеседующий говорит: «Го, еще одну задачу, достаточно, чтобы ты рассказал идею».
Задача 4: дается массив чисел. Найти наибольший по длине подотрезок, что сумма чисел в этом подотрезке равно 0. Ну и я ему предлагаю решения с префикс-суммой и хеш-таблицей за O(1).

Алгоритмическая секция 2
Задача 1: Дается массив из 0 и 1. Найти такую позицию нуля, что расстояние до ближайшей единицы максимально возможное. Рассказываю решения за линию и пишу код.
Задача 2: Дается бинарное дерево поиска, проверить, что это дерево является сбалансированным.
Рассказываю линейное решение, пишу код, исправляю пару багов. Остается еще 15 минут, я 5 минут позадавал ему вопросов по компании, и на этом разошлись.

Алгоритмическая секция 3
Задача 1: Условие было длинное, единственное, что запомнил, что там были отрезки (как временные интервалы), которые были даны в отсортированном порядке, и нужно было написать бинпоиск)
Задача 2: Дается натуральное число n. Нужно представить число n в виде суммы квадратов. Написать программу, которая находит количество представлений числа n.
Если честно, был удивлен, что предложили такую задачу, так как она решается простой баянистой дпшкой за n*sqrt(n), к счастью, оказывается, это же решение от меня ожидали.

Приходит HR с обратной связью. Говорит, что теперь будут подбирать мне команды. Кидается 4 ссылки на команды, говорит, выбирай, что интересно, я сказал, что хочу во все попробовать. Мне начали по очереди ставить собесы в команды.

Собес 1
Пришел лид одной команды, сказал, что ему важно, чтобы хорошо знали ООП на С++.... Он начал спрашивать все по ООП, показывал примеры кодов и задавал, сколько раз какой-то объект скопируется и т. д.
В общем, собес состоял только из ООП.

Собес 2
Пришли собесить два парня, такие разговорчивые. Начали узнавать, чем занимался, есть ли у меня опыт по БД, Linux. Потом дали около алгоритмическую задачу, в которой нужно было использовать map и указатели.

Собес 3
Интервьюер Говорит, что в его команду нужен человек, который знает многопоточности. У меня от этого слова уже в глазах потемнело.... Потом он сказал, что понимает такие темы, скорее всего, стажеры не знают....
И начинает по поверхности многопоточности задавать вопросы, я, конечно же, ничего ему не отвечаю.
После он мне дает задачу и говорит: «Давайте попытаемся решить многопоточностью, есть у вас идеи?» Я говорю: «Нет», и собес на этом заканчивается.

Собес 4
Сходу мне дает задачу:
Поступают запросы вида:
+ x (Добавить число x в множество)
- x (Удалить число x из множества)
get min (вернуть минимальный элемент из множества)
get max (вернуть максимум из множества)
Такое решение нужно написать за линию. При этом в множестве могут быть повторы.

В итоге два приглашения и два отказа. Чисто хватило алгосов.

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

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

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

Задача бэкенд Тинькофф (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)
Код в комментариях

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

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

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

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

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

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

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

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

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

Наверное самое тупое решение - это зафиксировать длину подотрезка, пусть это число 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.....

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

Дается 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).

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

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

Не могу не поделится задачей, которую крутят уже пятый раз подряд.
Задача называется 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача ШАДа.

Эта задача была на собеседовании в ШАД в 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://t.me/algoses/6
https://t.me/algoses/12
https://t.me/algoses/29
https://t.me/algoses/33
https://t.me/algoses/37
https://t.me/algoses/90
https://t.me/algoses/95

Задача 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На плоскости расположены 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)
Код в комментариях.