Задача ШАДа.

Так как скоро вступительный в ШАД решил разобрать задачу 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) будет максимальные числа.
Если хотите лучше подготовиться то записывайтесь на наш интенсив.
Благодарю интенсиву в прошлом году много наших студентов успешно поступили в ШАД.
Код в комментариях.

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

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

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

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

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

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 марта.
Программа и подробности.

Задача от который посыпалось много аналитиков.
Условия задачи выше.

Решение:
Весь разбор к сожалению не влезет, я рекомендую смотреть код и читать короткий разбор.

Нам нужно number_of_trials=10000 промоделировать ситуации.

Функция barber_shop_simulation будет моделировать приходы клиентов, а также время стрижки каждого клиента. Мы это можем сделать так как знаем как распределены эти вероятности.

Функция calculate_closing_time посчитаем время закрытие. Для этого будем рассматривать каждого клиента по очереди и будет отдавать его мастеру, который раньше всего освобождается. В конце концов мы будем знать когда освободятся все мастера, вернем разницу между этим числом и 16*60 (16:00 в минутах)

Функция check_insufficient_seating будет возвращать True если хотя-бы один клиент будет стоять во время ожидания, так как всего 5 мест для ожидания.
Для решение мы первых трех клиентов отдадим мастерам, следующие 5 добавим в очередь (сказав что они сели) теперь рассмтрим следующего клиента, если он приходит раньше чем освободится один мастер, мы вернем True, так как ему придется стоять, иначе мы из очереди достаем левого человека (то есть того кто сидит на 1 месте) и отдаем мастеру. В общем просто моделируем эту ситуацию. По коду можно легко понять этот момент.
Вероятность того, что хотя бы один посетитель за день будет шестым в очереди и на него не хватит кресла в зоне ожидание - доля случаев когда функция check_insufficient_seating вернет True.

Функция calculate_waiting_time_12_00 посчитаем время ожидания человека который придет в 12:00. Для решения мы должны просто оставить всех людей который пришли до 12:00 и вызвать функцию calculate_closing_time, которая будет считать уже не до 16:00 а до 12:00.
Так как мы моделируем number_of_trials раз мы получим массив чисел длины number_of_trials, среди них мы должны вернуть 95 квантиль (np.quantile)

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

Задача ШАДа
Мощностью элемента массива назовем сумму максимального элемента, стоящего справа от него и максимального элемента стоящего от него слева.
Мощность крайних элементов будем считать равной 0.
У вас имеется первоначально пустой массив к которому по очереди справа приписываются n целых чисел. На каждом шаге посчитайте и выведите наибольшее значение среди мощностей его элементов.

В первом строке дается число n (1 <= n <= 10^6). Во второй строке дается сам массив.
Вывести n чисел - наибольшие мощности на каждом из n шагов.

Пример-1
3
1 4 5
Ответ 0 0 6
(если кто не понял объясню пример, вам сначала дают число 1, так как в списке у вас одно число то ответ 0, после вам дает число 4, так как всего у вас два числа то ответ 0, после вам дают число 5, можность для числа на второй позиции (4) будет равна 6, так как 1 + 5 = 6)

Пример-2
2 3 3 2
Ответ 0 0 5 5

Пример-3
6
6 5 4 3 2 1
Ответ 0 0 10 10 10 10

Решение:

Решим задача за O(N).
Предположим что вы уже получили i чисел, то есть у вас есть числа a[1], ..., a[i], вы знаете ответ для них равен ans[i].
Теперь вам дает i + 1 ое число, то есть a[i + 1].
В каких случаях ans[i + 1] может стать больше чем ans[i] ?
Очевидно чтобы это произошло в ans[i + 1] должен участвовать число a[i + 1] и какое-то максимальное число слева от позиции i (мы не можем взять число a[i] в ans[i + 1]) пусть это число max_pref, которую легко поддерижвать (смотрите код для лучшего понимания).
Таким образом получаем формулу:
ans[i] = max(ans[i - 1], a[i] + max_pref)

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

Задача из Яндекса

Дается массив из 0 и 1. Ваша задача выбрать такую позицию нуля, чтобы минимальное расстояние до единицы было максимальным.
Например 100110001
ответом будет позиция 6. 100110001. В задаче нельзя использовать дополнительную память, то есть можете использовать только О(1) дополнительной памяти.

Решение:
Очевидно, что если массив начинается с нуля то претендент на ответ это позиция 0.
Аналогично если массива заканчивается на 0 то претендент на ответ это позиция n - 1.
Теперь разберемся с остальными кейсами,пусть i1, i2, ,..., ik позиции где стоят единички, тогда очевидно претендентом на ответ будет нолик по середине между двумя соседними единицами, например в случае 1000001 ответом будет ноль по середине 1000001.

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

Давайте хранить переменную last_one -которая будет хранить ближайший слева позицию единички от позиции i. (i - цикл по которому идем слева направо)
Если a[i] == 1 то есть встретили единичку, то мы понимаем что до этого единичка была в позиции last_one и нам выгоднее всего выбрать позицию (i + last_one) // 2 (конечно если там ноль)
Таким образом мы смогли решить задачу без дополнительной памяти.
Время работы алгоритма O(n)

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

Задача из ШАДа.

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

Решение:
В задаче якобы просят построить граф, но по факту вас интересуют только степени вершин. Давайте обойдемся без построения графа.
И так для каждой вершины k мы должны провести ребра к вершинам k-v[k], k - v[k] + 1, ...., k - 1. Проводить ребра явно плохая идея так как получим асимптотику O(n^2). Давайте мыслить в сторону степеней вершин. У каждой вершине на отрезке [k-v[k], k - 1] мы увеличиваем степень на один, а у вершины k степень увеличивается v[k].
Хочется применить дерево фенвика или дерево отрезков ?
- В целом можно но за это у вас снимут пару баллов, так как асимптотика такого решения O(n * logn).

Давайте придумаем решение за O(n).
Заведем массив ans размера n, давайте для каждой вершины k мы обновим массив ans следующим образом:
ans[k - v[k]] += 1
ans[k] -= 1
Этим трюком мы условно говорим " Давай прибавим +1 на отрезке [k-v[k], n - 1] (то есть на суффиксе, а также -1 на отерзке [k, n-1]"

После того как проделали для каждого k (0 <= k < n) мы посчитаем префикс сумму массива ans.
Осталось вывести массив ans[0] + v[0], ans[1] + v[1], ans[2] + v[2], ..., ans[n-1] + v[n-1].
Время работы алгоритма O(n)


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

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

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

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

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