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

Эпичная программа от института, о котором вы еще не слышали!

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

EPIC Institute of Technology - часть инновационного продуктового центра EPAM. Это уникальная образовательная организация под руководством Deltix team (EPAM Systems).
В EPIC представлены 4 направления:
1. Time Series Analysis
2. Real-Time Backend
3. Real-Time Frontend
4. Complex Logic

Плюсы:
1. После успешного завершения программы у вас появится возможность начать карьеру в выбранной области.
2. Программа абсолютно бесплатная.
3. Сообщество, где каждый помогает другому.
4. Преподаватели-эксперты (победители олимпиад, сотрудники Google и других крупных компаний).
5. Гибкая система обучения: преподаватели понимают ваше положение и готовы помочь в случае возникновения уважительных причин.

Вступителэьный экзамен включает в себя контест на codeforces по алгоритмам. Каждый год проводится всего 4 экзамена, вам нужно успешно сдать лишь один из них. Также есть возможность поступить с помощью резюме (если у вас хороший опыт и вы можете объяснить, почему решили не сдавать экзамен), но приоритет отдается тем, кто успешно сдал вступительный экзамен.
На сайте указано, что необходимо зарегистрироваться на экзамен и следить за обновлениями. Однако, у моей ученицы был опыт, что несмотря на регистрацию, новости на сайте не обновлялись, поэтому рекомендую вам следить за анонсами экзаменов в их телеграм канале.
Единственное строгое ограничение - возраст: вам должно быть не менее 18 лет.

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

Чтобы успешно пройти экзамен, вам нужно будет изучить следующие темы:
1. Хеш таблицы, префикс суммы
2. Базовое понятие графов
3. Базовое понятие ДП
4. Жадные алгоритмы
5. Знания структуры данных дерево отрезков или фенвика поможет решить более сложные задачи

Обычно первых четырех пунктов хватает с головой

Не упустите шанс стать частью EPIC Institute of Technology уже этим летом! Присоединяйтесь к нашим курсам и освойте мир алгоритмов! Курс стартует 10 марта.
Программа и подробности.

Твой план подготовки к собесу и ШАД.

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

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

Задача ШАДа.

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

Требуется высадить аллею из n деревьев. Лунки под деревьями пронумерованы последовательно. Расстояние между деревьями определяется как разность номеров лунок, где они растут. На Марсе могут выжить только k сортов деревьев. Красота одного дерева i-го сорта c_i. 
Требуется озеленить Марс с максимальной суммарной красотой. Однако, деревья одного сорта конфликтуют, поэтому их следует садить как минимум на расстоянии k.

В первой строке находится два целых числа 
k (1 <= k <= 5) и n (1 <= n <= 10^5)

В следующей строке следуют k целых чисел c_i (1 <= c_i <= 10^5)

Решение:
Разобьем n деревьев на n/k блоков длины k, и последний блок длины n%k.
Визуально можно представить так: |........|........|........|........|........|....

Заметим что в одном блоке не могут быть двух деревьев одного сорта. Хммм
Ну чтобы у нас не было пустых ячеек мы должны каждую ячейку блока заполнить, следовательно в каждом блоке перестановка ci - тых.
Тогда почему бы не использовать в каждом блоке следующий порядок : с1, c2, ..., ck ?

Потому что последний блок может быть длины < k, а туда нам выгодно расставить максимальные ci-тые.
Тут вы уже должны понять в каком порядке нам сажать....
Давайте отсортруем наш массив по убыванию c, и будем расставлять в каждом блоке c1, c2, .., ck, так мы получим, что в последнем блоке (который может быть длины < k) будет максимальные числа.
Если хотите лучше подготовиться то записывайтесь на наш интенсив.
Благодарю интенсиву в прошлом году много наших студентов успешно поступили в ШАД.
Код в комментариях.

How to забоать алгосы к ШАД за оставшееся время

Товарищи, вступительные ШАД совсем скоро, самое время начать готовиться!
Для начало сравним задачи вступительных 2023 и 2018 года.

Вот несколько задач которые встречались в 2023 году.
https://t.me/algoses/6
https://t.me/algoses/12
https://t.me/algoses/19

2018 год
https://t.me/algoses/69
https://t.me/algoses/9

Задачи сильно отличаются......
2018 год был аномальным по алгоритмам и сейчас такого уже не делают, так что расслабляемся и не тревожимся.
Лучше всего сфокусироваться на свежих задачах, это касается не только алгосов, но и всего другого. Тот же матанализ, если вы видели задания 2022 года и 2023, то согласитесь во многом общие темы.

И так какие же темы по алгоритмам попадались в прошлом году и какие скорее всего попадутся в этом ?
—Бинарный поиск, два указателя, префиксные суммы, жадные алгоритмы, бинарные деревья, графы.

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

Объясню логику почему на последним этапе именно такие задачи.
-Во первых это Яндекс и зачастую на собесах дают задачи со сложностью O(N).
-Во вторых собес длится 30 минут, давать задачи на сложные алгоритмы или сложную идею нет смысла, скорее всего будет задача где можно легко уйти не туда, не учесть подводные камни и наделать багов. Как раз таки темы на два указателя/жадные алгоритмы такие.


На вступительных экзаменах могут встречаться два типа задач: идеи‌ные и простые на реализацию.

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


—Теперь про подготовку:
Чтобы избежать ситуации, когда не удастся решить простую задачу на графах из-за недостаточного знания этой темы, я предлагаю вам ознакомиться с алгоритмами, перечисленными выше. Для этого можно решать простые задачи на соответствующие темы на платформе leetcode. Желательно до-конца марта это одолеть.

Начиная с апреля, мы переходим к решению более сложных задач.

-Для БП и двух указателей берите курс ИТМО (чтобы ссылка работала, нужно зарегаться), если вы прорешали все задачи на бп и два указателя, я уверен вы сможете решить любую задачу из ШАДа на эти темы.

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

-По графам не нужно знать супер сложные алгоритмы. Я вам рекомендую acmp, прорешать обязательно 1 часть, а второй части решить хотя-бы по 5 задач на алгоритм Флойда и Дейкстры.


Если вы все эти темы хорошо знаете или осталось еще свободное время для подготоки, я предлагаю вам порешать задачи на монотонный стек, СНМ, ДП.

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

Задача на Аналитика

Изначально у вас нет предметов. Вам поступают запросы, вида добавь предмет с названием s_i и веса w_i.
А еще бывают запросы вида: вытащи мне из набора предметов учитывая их вероятности.

Пример.
У вас есть предметы:
"abc" - 4
"qq" - 2
"bbb" - 6
Тогда вероятность того что вернете строку "abc" равно 4/12, вероятность вернуть "qq" равно 2/12, вероятность вернуть "bbb" вернуть 6/12.

После добавили предмет "post" веса 5
Ваши вероятности станут следующими:
abc - 4/17, qq - 2/17, bbb-6/17, post-5/17.
(Честно сам не понял условия, пока собеседующий не дал пример)

Решение:

Во первых заметим, что у нас нет операции удаления, это нам сильно облегчит задачу.
Пусть вам пришел запрос добавить первый предмет в набор, пусть его веса равен 3. Давайте в массиве who на отрезке [1, 3] поставим число 1.
Т.е who[1] = who[2]=who[3] = 1, а остальные пока нули.

После вам сказали добавить второй предмет в набор, пусть его вес равен 2, давайте поставим в массиве who на отрезке [4, 5] число 2.
То есть у вас получится такой массив who = [1, 1, 1, 2, 2, 0, 0, 0, 0, 0, ...0].

Думаю вы поняли что тут происходит.
Теперь запустим randint на отрезке 1, до суммы весов предметов.
Пусть выпало число pos, тогда who[pos] и будет предметом который нужно вернуть.

В комментариях расскажите что можно оптимизировать в этом решение.

Задача с Озона
(Полное условие в комментариях)

Решение.

Решим задачу жадным алгоритмом.
Создадим очередь x_ids = []
Давайте пройдемся по строке слева направо и смотрим позицию i.

* Если видим букву 'X' мы добавим его в очередь x_ids.

* Если видим букву 'Y' то посмотрим правда ли очередь x_ids непустой, если действительно непустой, то скажем что буквы на позициях x_ids.back() и i образовали пару. (просто отметьте их у себя) и удалим последний элемент из x_ids.back().

* Если видим букву 'Y' и очередь пустая то ничего не делаем.

* Если видим букву 'Z' то мы обязательно должны дать ему в пару, какую-то букву слева, которая является X или Y, но вопрос, а какой давать ???
— Конечно выгоднее всего посмотреть есть ли слева 'Y' у которого нет пары, если существует такой 'Y' то скажем, что он образует пару с нашей буквой Z, а если такого Y нету, то посмотрим правда ли очередь x_ids непустой.
Если непустой то скажем что x_ids.back() и i образовали пару и удалим x_ids.back() из очереди.
Но если эти два случая не сработали мы вынуждены взять какую то пару и забрать у него Y сказать что этот Y образует с Z пару, а его паре X сказать что остался без пары.
А то почему мы первом делом удаляем Y оставлю на подумать.

Специально для вас я подготовил 25 задач, в которых я старался охватить все важные подходы к решению задач, актуальные для собеседований за последние два года

Задача на Аналитика

Вам приходит два вида запроса.
1) Добавить число x в набор чисел.
2) Удалить число x из набора (если число x встречается несколько раз, то удалить их всех)

Ваша задача после каждого запроса найти дисперсию.
В рамках этой задачи дисперсию будет считать SUM(xi - x`)^2 / n
То есть сумма средне квадратичных отклонений от мат ожидания.

Решение:

Если честно могли бы лучше написать условия задач)

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

Когда вам приходит первый тип запроса то вы увеличиваете количество вхождения, то есть cnt[x] += 1.

Когда второй тип мы просто удаляем этот ключ, то есть del cnt[x].

Давайте лучше посмотрим на сумму (xi - x`)^2 Если мы раскроем скобку, то получим
x1^2 + x2^2 + .... + xn^2 + n * x`^2 - 2 * (x1 + x2 + ... + xn) * x`.

И так чтобы считать дисперсию нам необходимо знать размер набора чисел, суммы чисел, суммы квадратов чисел x` мы можем всегда найти: x` = (x1 + .... + xn) / n

Создадим переменные
sum_sq, sum, n.

Когда приходит первый тип запроса:
sum_sq += x^2
sum += x
n += 1
cnt[x] += 1

Когда приходит второй тип запроса:
sum_sq -= x^2 * cnt[x]
sum -= x * cnt[x]
n -= cnt[x]
del cnt[x]

И так чтобы посчитать дисперсию у нас есть вся необходимая информация.
Дисперсия = (sum_sq + n * x`^2 - 2 * sum * x`) / n
Где x` = sum / n.

И так мы научились обрабатывать запросы за O(1)

Задача ШАДа
Как по мне одна из самых сложных задач, благо сейчас такие не попадаются.

Skill Diagnostic - B. Команда аналитиков
https://contest.yandex.ru/contest/33766/problems/B/



Аркадий - менеджер команды аналитиков из k человек. У Аркадия есть бэклог из n задач, i-я задача требует
ti дней работы любого из членов команды (мы считаем всех членов команды равнозначными). Над каждой задачей от начала
до конца должен работать кто-то один - передавать задачи в процессе выполнения неудобно. Для каждой задачи известен дедлайн - di рабочих дней. Помогите Аркадию определить, успеет ли его команда выполнить все задачи в срок.

Формат ввода
В первой строке заданы два целых положительных числа - n и k (1<=n,k<=15). В каждой из следующих n строк заданы
два целых положительных числа - ti и di (1<=ti<=di<=10^9).

Формат вывода
Выведите NO, если нельзя выполнить все задачи в срок.
Иначе в первой строке выведите YES. Далее выведите k строк, причем в i-й строке будет описание того, какие задачи
выполняет i-й сотрудник: сначала выведите одно целое неотриц число - кол-во задач, которое будет выполнять i-й сотрудник,
а затем выведите номера задач, которые будет выполнять i-й сотрудник. Выводите номера в том порядке,
в котором их должен выполнять сотрудник. Задачи нумеруются в порядке перечисления во входных данных.
Если существует несколько правильных ответов, вы можете вывести любой.

Пример 1
Ввод
5 2
3 3
2 2
3 6
2 4
2 6
Вывод
YES
3 2 4 5
2 1 3

Пример 2
Ввод
2 1
4 7
4 7
Вывод
NO


Решение:
Опытный человек заметит что ограничения n, k <= 15, что чуть чуть странно. Я лично когда прочитал условия подумал про жадное решение, но в моменте реализации понял, что задача не решается жадно и не зря ограничения такие.

Вообще очень странно n, k <= 15 и я вам советую держать в голове следующие наблюдения:
При 10 <= n <= 15 скорее всего решение за 3^n * (на что то)
При 15 < n <= 20 скорее всего решение за 2^n * (на что то)
При 20 < n <= 30 скорее всего решение на разделяй и властвуй с подмножествами.

В общем смысле решение выглядит следующим образом.
Первый учение мог решить ids[1] набор задач, второй ids[2], ..., k-тый ids[n].
Где ids[i] - набор индексов задач, которые решит i тый ученик, т.e ids[i] = {j0, j1, j2, ..., jt}.
Надеюсь вы уже видите что можно решить задачи динамическим программированием по подмножествам.

И так пусть dp[i][mask] = 1 если мы рассмотрели i учеников и задачи в mask уже решены, иначе 0.
mask - это число на отрезке [0, 2^n-1], если вы переведете mask в двоичное представление то получите нули и единицы, на позициях где стоит 1 означает что вы завершили эту задачу.

И так пусть мы зафиксировали i, mask и знаем, что dp[i - 1][mask] = 1, тогда нужно перебрать, а какое подмножество задач решит i-тый ученик, то есть вы должны перебрать подмножество mask1, такой, что (mask1 & mask) = 0, но если будете перебирать mask1 у вас асимптотика будет больше чем O(4^n), давайте лучше заметим, что мы можем воспользоваться следующей техникой. То есть переберем максу s, а дальше переберем все подмножество маски s, пусть это число mask, тогда задачи которые предстоит решить i тому ученику равно (mask xor s).

Ответ YES если dp[k][(2^n)-1] = 1, иначе ответ NO.

Остались болезненные моменты с выводом ответа, а также мы не учли порядок задач в котором будет решать i тый ученик.
То есть когда мы зафиксировали i того ученика и маску задач мы должны определить в каком порядке он будет решать эти задачи. Здесь я написал снова дпшку) может вы сможете придумать что то другое.
И так моя дпшка следующая, dp_calc[mask][i] минимальное время чтобы решить все задачи из mask и при этом последняя решенная задача это i. (дпшка такая же как и в задаче коммивояжёра)

Читателю без опыта сложно будет вникнуть, но если хотите разобраться то советую разобраться с темой динамическое программирование по подмножествам.
Время работы O(3^n * k)

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

Задача ШАДа
Дают n отрезков (1 <= n <= 1e5). Каждый отрезок это два числа l, r (1 <= l <= r <= 1e5).
Для каждого натурального числа x которое состоит хотя-бы в одном отрезке, посчитать в скольких отрезках содержится число x.

Например:
5
1 10
2 9
3 8
4 7
5 5
Ответ
1 1
2 2
3 3
4 4
5 5
6 4
7 4
8 3
9 2
10 1

например число 9 встречается только в первом и во втором отрезке.


Решение:

Наверное придет в голову создать массив cnt, размера 1e5, для каждого отрезка l, r пройтись циклом for i in range(l, r + 1) и сделать cnt[i] += 1
Таким образом ответом является все такие пары (i, cnt[i]), такие что cnt[i] > 0.
Проблема в том, что работает этот алгоритм O(m * n), где m = 1e5.

Давайте попытаемся это же решение оптимизировать. Конечно вы можете написать дерево отрезков или дерево Фенвика, но вам скажут, нужно ли писать такие структуры, так как они способны на большее и в этой задаче это лишнее.
Можно придумать решение за O(n + m). Заметим во первых, что задачу можно решить оффлайн. Давайте для каждого отрезка l, r сделаем cnt[l] += 1, cnt[r + 1] -= 1.
Это можно понимать так: Давайте не будем прибавлять плюс один ко всем ячейкам в [l, r] а поставим +1 на позиции l которая будет работать на всем суффиксе, но в таком случае мы должны еще поставить -1 на позиции r + 1, чтобы тот +1 работал только на отрезке [l, r].

И так у нас есть cnt осталось на нем посчитать префикс функцию, после пройтись по префикс функции и вывести все ячейки на которых стоит положительное число.

Время работы O(n + m), где m = 1e5

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

Такая задача попадалась в Epam epic-institue.
Своего рода ШАД от Epam

Вот и разбор контеста на стажировку в Яндекс! Обязательно делимся с друзьями. Ждём 1000 шэров (поделиться) с другом и разбираем будущий сезон.

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

Задача с контеста Яндекс
Даются число n - количество массивов.
После n раз дают число k и сам массив. Где число k - длина i - того массива.
Для пары массивов i, j - красотой будем говорить максимальную длину общего префикса. Найти сумму красоты по всем парам i, j.
Например:
3
2
1 2
2
1 3
3
1 2 3
Ответ 4.
Так например для массива 1 2 и 1 3 красота 1. Для 1 2 и 1 2 3 красота 2, для 1 3 и 1 2 3 красота 1.
Ответ 1 + 2 + 1 = 4.

Решение:
Чтобы оптимально решить задачу воспользуемся алгоритмом бор.
Построим дерево. Когда будем добавлять массив в бор сделаем +1 ко всем вершинам бора, таким образом мы узнаем сколько массивов проходило через данную вершину.

Теперь подумаем, как находить ответ одного массива. Пусть мы на вершине v и пытаемся пойти в u.
Пусть v-> count говорит сколько массивов проходило через вершину v.
Когда пытаемся пройти через вершину к u, мы понимаем, что v -> count - u-> count массивов больше с нами не идут дальше по ветке.
Нам нужно знать высоту вершины в дереве, чтобы определить на какую красоту прибавлять. Легко видеть что мы должны прибавить к ответу (v->count - u->count) * h, где h - высота вершины v в дереве.
Не забывайте обработать случай, когда мы в листе.

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

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

Задача с Тинькоффа.

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
cut u v — удалить из графа ребро u - v;
ask u v — проверить, лежат ли две вершины u и v в одной компоненте связности.
Известно, что после выполнения всех операций типа cut, рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

Входные данные.
В первой строке дают три числа n, m, k.
После m пар чисел задающая ребра графа. После k запросов.

Решение:
Тинькофф любит давать задачи на СНМ.
Во первых заметим, что в конце всех запросов граф станет пустой, этот факт нам очень сильно поможет.

Давайте запросы обрабатывать с конца, то есть сначала k тый запрос, после k-1 и тд до 1 запроса.
Такой подход называется решения оффлайн, так как сначала введем все запросы, а дальше решаем задачу.

И так в конце после всех запросов наш граф пустой, давайте построим СНМ где компонента это отдельная вершина. После когда приходит запрос cut u, v мы будем добавлять вершины u, v в одно множество, а при ask u, v будем узнавать правда ли вершины в одной компоненте.

Стандартное решение с помощью СНМ, главное нужно было заметить, что задачу можно решать оффлайн.
Время работы O(k*logn).

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

Вот и разбор контеста на стажировку в Тинькофф! Обязательно делимся с друзьями. Ждём 1000 шэров (поделиться) с другом и разбираем математику.

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

Задача с Тинькофф стажировки.
Самая сложная задача с Тинькофф 2023.
Вам дается массив целых чисел а. Также дают q запросов, каждый запрос бывает двух видов
1) + l, r, x. Вы должны прибавить число х ко всем числам на отрезке l, r.
2) ? l, r, k, b. Вы должны найти max(min(a[i], k*i+b)).
n и q до 1е5.

Решение.
Давайте построим ленивое дерево отрезков на всем массиве, где в каждой вершине будем хранить максимум на всем отрезке.
И так наше дерево отрезков умеет прибавлять число х на отрезке, а также узнавать максимум на отрезке.
Давайте научимся обрабатывать второй запрос.
Вот вам дали l, r, k, b.
Путь mid_res=mid*k+b, где mid середина отрезка l, r.
Что вы можете сказать, если максимальное число из массива а на отрезке [mid, r] не меньше чем res_mid ?
Это означает, что ответ точно будет не меньше чем res_mid, значит отрезок [l, mid] вам не нужно рассматривать, так как на этом отрезке ответ будет точно меньше. Такой факт вам позволит не рассматривать одну из частей отрезка.

Теперь остается случай, когда максимальное число на отрезке [mid, r] меньше чем res_mid.
В такие моменты вам нужно запустить такое же решение на отрезке [l, mid] - которая вернет максимальный ответ, а на отрезке [mid, r] просто найти максимальное число. Далее вернуть максимум из этих двух чисел.
Замечу что находить максимум на отрезке вам поможет дерево отрезков.

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

Задача с Яндекса
Дается бинарное дерево. Найдите диаметр дерева.

Решение:
Определение: Диаметр в дереве - это максимальное расстояние между двумя вершинами.
Из определения можно понять, что диаметр это максимальный путь между двумя листьями дерева.

Пусть h[v] - максимальное расстояние от вершины v до листа поддерева вершины v. Чтобы посчитать h[v] вы должны написать dfs.
И обновлять h[v] = max(h[v.left], h[v.right]) + 1. Зная массив h как найти диаметр ?
Диаметр обязательно пройдет через какую то вершину. Давайте переберем эту вершину. Пусть эта вершина u, тогда максимальный путь между листьями поддерева вершины u равно h[u.left] + h[u.right] + (2 или 1 или 0 в зависимости сколько детей у вершины u).
Среди всех таких сумм возьмем максимум.
Время работы алгоритма O(n).
Если бы у нас было бы произвольное дерево такой алгоритм не сработал бы, так как могут быть вершины с > 2 потомками..
Кому интересно вот алгоритм нахождения диаметра для произвольного дерева ссылка

Топ-5 книг по С++ для начинающих и продолжающих от нашего нового направления по С++

Все мы понимаем, что С/С++ широко используется в современном мире в самых разных областях, где нужна высокая производительность. На нем написаны ядра ОС, интерпретаторы (привет, Python), игровые движки, библиотеки для машинного обучения, и многое другое. С++ точно не потеряет актуальность в ближайшие годы, и, как следствие, сохранится высокая востребованность разработчиков, владеющих этим языком.

Все книжки можно найти в комментариях под постом. Начать погружение в С++ я бы рекомендовал с книги Питера Готтшлинга «С++ для инженерных и научных расчетов». В ней достаточно полно рассмотрен современный С++ в объеме, необходимом и достаточном в большинстве практических ситуаций.

Также на начальном этапе многие рекомендуют книгу создателя языка С++ Бьерна Страуструпа «Язык программирования С++», которая весьма неплоха, но лично я бы все-таки выбрал Готтшлинга.

Помимо знания синтаксиса языка, нужно уметь пользоваться стандартной библиотекой шаблонов языка С++ (STL, Standard Template Library) – с одной стороны, не нужно знать ее вдоль и поперек, но, с другой стороны, она позволяет писать легко читаемый код и сэкономить время на написание собственной реализации многих алгоритмов. Поэтому предлагаю познакомиться, например, с книгой «C++17 STL. Стандартная библиотека шаблонов» Яцека Галовица.

Наконец, когда вы освоитесь с вышеперечисленным, следует обязательно прочесть каноническую книгу Скотта Мейерса «Эффективный и современный С++». Эта талантливейшая книга позволит профессионально применять освоенный ранее материал в практических задачах.

В заключение, следует упомянуть «библию С++», а именно Стандарт языка С++. Это отличная настольная книга для случаев, когда возникает, например, подозрение на undefined behaviour в коде – можно обратиться к ней и выяснить, будет ли по стандарту код корректным или могут возникнуть проблемы.

Больше материалов на нашем канале по С++! 😎😎😎

Задача с контеста Яндекс
Вам на вход даются два числа n, h. (1 <= n <= 100), (1 <= h <= 10**18)
Равновероятно выбирается перестановка p = [1, 2, 3, ..., n], и строится декартовое дерево из пар (1, p[1]), (2, p[2]), ..., (n, p[n]). Определить вероятность того, что высота дерева равна h.

Напомним определение декартового дерева:
Декартовое дерево - это бинарное дерево, в узлах которого хранятся пары (x, y), где x - это ключ, а y - это приоритет.
Оно является двоичным деревом поиска по x и кучей по y.

Например n = 3, h = 2.
Рассмотрим все возможные пары от перестановки p.
(1, 1), (2, 2), (3, 3)
(1, 1), (2, 3), (3, 2)
(1, 3), (2, 2), (3, 1)
(1, 2), (2, 1), (3, 3)
(1, 3), (2, 1), (3, 2)
(1, 2), (2, 3), (3, 2)
Высота дереве 2 достигается для
(1, 1), (2, 2), (3, 3)
(1, 3), (2, 2), (3, 1)
(1, 2), (2, 1), (3, 3)
(1, 3), (2, 1), (3, 2)
Ответ 4/6 = 0.666.


Решение.
Заметим, что для h >= n, ответ 0.
Решать будет задачу динамическим программированием по подотрезкам.
Пусть dp[n][h] - вероятность, что в дереве с перестановкой длины n высота будет h.
Базой дп очевидно dp[0][0] = dp[1][0] = 1
Как посчитать dp[n][h], если мы уже для более меньших n и h уже посчитали дп ?

Чтобы обновить дп мы должны понять в какую позицию мы поставим максимальное число, так как это число будет корнем. Давайте переберем позицию в которую поставим максимум, пусть эта позиция 1 <= pos <= n, вероятность, что максимальное число попадет на позицию pos, равно 1/n.
Что вы можете сказать теперь про p[1], p[2], ..., p[pos - 1] и p[pos + 1], p[pos + 2], ..., p[n] ?
Первый набор попадете в левую часть дерева, а вторая в правую часть дерева.
Нам необходимо, чтобы в одной из частей высота была равна h -1. Пусть в левой части высота h - 1, тогда в правой части высота может быть любой. Получаем dp[n][h] += (dp[pos - 1][h - 1] * dp[n - pos][j] ) / n где j перебирается от 0 до h - 1.
Теперь наоборот рассмотрим случай когда в правой части высота равна h - 1, а в высота левой части любая.
Полуем аналогичное обновление dp[n][h] += (dp[pos - 1][j] * dp[n - pos][h - 1]) / n, где j перебирается от 0 до h - 1.
Заметим, что мы два раза посчитали dp[pos - 1][h - 1] * dp[n - pos][h - 1], следовательно не забудем сделать
dp[n][h] -= dp[pos - 1][h - 1] * dp[n - pos][h - 1].

Как мы видим наше решение работает за O(n^2 * h^2).
Давайте оптимизируем до O(n^2 * h).
Обратите внимание " dp[n][h] += (dp[pos - 1][h - 1] * dp[n - pos][j] ) / n где j перебирается от 0 до h - 1. "
Нужно ли нам перебирать j ?
Мы же могли заранее запомнить сумму dp[n - pos][0] + dp[n - pos][1] + ... + dp[n - pos][h - 1] = sum и не перебирать j.
Следовательно время работы O(n^2 * h).
Псевдокод в комментариях.