Задача с ШАДа

Дается массив положительных целых чисел a длины n <= 1e5.
Набор чисел называется хорошим, если любое число из набора не больше суммы двух других чисел из набора. Найдите хороший набор из массива с максимальной суммой.
Например
5
3 2 5 4 1
Возьмем числа 3, 2, 5, 4

5
1 2 4 8 16
Возьмем числа 8, 16

Решение:
Отсортируем массив a и будем искать ответ в отсортированном массиве.
Пусть мы взяли числа на позициях i1, i2, ..., ik. Чтобы набор был хорошим нам необходимо и достаточно, чтобы выполнялось неравенство a[i1] + a[i2] >= a[ik].

Что вы можете сказать про i1, i2 в оптимальном ответе ?

Утверждение i1 + 1 = i2 - это правда так как иначе вы могли передвинуть i1 к позиции i2 - 1 сохраняя неравенство a[i1] + a[i2] >= a[ik], но уже с большей суммой.
Из этого утверждение получаем вывод:
i1 + 1 = i2
i2 + 1 = i3
i3 + 1 = i4
......
То бишь индексы - это непрерывный отрезок.
Зная эти факты вы наверное уже поняли, что задачу будем решать двумя указателями. Для этого достаточно для каждого l находить максимальный r для которого выполнено неравенство a[l] + a[l + 1] >= a[r].

Время работы: O(n * logn)

Задача с собеседование в Яндекс

Напишите декоратор '@profiler', который при вызове функции будет замерять время ее исполнения
(в секундах, можно дробное) и количество рекусивных вызовов произошедших при последнем вызове функции.
Для работы со временем в питоне есть замечательный модуль datetime.
Декоратор не должен затирать основные атрибуты функции: __name__, __doc__, __module__.
Пользоваться глобальными переменными запрещено, сохранять результаты замеров нужно в атрибутах функции.
Атрибуты назовите last_time_taken и calls.

Задача с Шада
Имеется n касс. Каждая касса работает определенное время работы.
Найдите количество секунд, когда все кассы работают одновременно.
Формат времени работы каждой кассы определяется 6 числами h, m, s, h1, m1, s1 (час, минута, секунда открытие и закрытие кассы соответсвенно)

Решение:
Давайте время начала работы кассы и время закрытие переведем в секунды, то есть сделаем h*3600 + m*60 + s, h1*3600 + m1 * 60 + s1.
Заметим, что время работы кассы теперь определяется отрезком. В случае если время работы меньше времени закрытие мы разобьем на два отрезка [beg, 24*3600], [24*3600, end].
Отсортируем все отрезки по левому значению и пройдемся циклом заведя счетчик открытых касс. Как только количество открытых касс равно n увеличиваем ответ.
Время работы О(n * logn)
Можно решить и за линию.

Задача с Шада
На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстоянием в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может стартовать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время. Если собрать все монеты не получится вывести No solution.
(1 <= n <= 1e3) - количество монет.
Каждая монета определяется двумя числами (xi, ti) - место положение и время за которое нужно взять

Решение:
В задаче вы должны выбрать стартовую позицию от которой начнете движение. Пусть это точка xi тогда ваши движение представляется последовательностью R и L (где R - движение на одну позицию вправо, а L на одну влево).

Решим задачу динамическим программированием.
Давайте отсортируем все монеты по координате в которой они стоят.
Пусть dp[l][r][0] - минимальное количество минут необходимое, чтобы набрать все монеты на позициях с l по r и при этом в конце вы окажитесь в позиции xl, аналогично dp[l][r][1], но уже окажитесь на позиции xr.

Вы можете обновить состояние dp[l - 1][r][0] через dp[l][r][0] или dp[l][r][1] в первом случае у вас должно выполняться условие x[l] - x[l - 1] + dp[l][r][0] <= t[l - 1], а во втором x[r] - x[l - 1] + dp[l][r][1] <= t[l - 1]. Аналогично обновляем и dp[l][r + 1][1].

База дп. Поставим для всех l, r (1 <= l, r <= n) dp[l][r][0] = dp[l][r][1] = INF и после dp[l][l][0] = dp[l][l][1] = 0 так как мы можем сами выбирать с какой позиции нам начинать.

Выводим No solution если dp[1][n][0] = dp[1][n][1] = INF, иначе выводим min(dp[1][n][0], dp[1][n][1])
Время работы O(n^2)

Один из популярных подходов.
Представим, что вам дали задачу где происходят какие-то битовые операции.
Например вам дали натуральное число n (1 <= n <= 1e18) и вы должны посчитать сумму (i & j) по всем i, j (1 <= i, j <= n).

Давайте посмотрим на двоичное представление числа (i & j) - в этом представление может быть всего 60 битов. Это нам позволяет свести исходную задачу к другой задаче.
Пусть cnt[bit] это количество чисел x, таких, что (1 <= x <= n) и в двоичном представление числа x есть бит на позиции bit (иначе говоря (x » bit) & 1 == 1).
Тогда ответом на задачу была бы сумма 2^bit * cnt[bit]^2. (0 <= bit < 60).

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

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

что касается cnt[bit] то ее можно посчитать с помощью digit dp

Задача с собеседования в Яндекс.
Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r (0 ≤ l, r < n). Изначально оба они указывают на первый элемент массива (l = r = 0). Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

Указание. Учетная стоимость обработки каждого запроса на перемещение и подсчет максимума должна оказаться O(1).
Например:
10
1 4 2 3 5 8 6 7 9 10
12
R R L R R R L L L R L L
Ответ
4 4 4 4 5 8 8 8 8 8 8 6

Решение:
Существует знаменитый алгоритм, который называется невозрастающая очередь.
Суть алгоритма такая - мы должны поддерживать очередь dq в которой будет находиться невозрастающие числа на отрезке [l, r].

Рассмотрим на примере выше, чтобы лучше понять как работает очередь.
В первый момент времени l = r = 0 и dq = {1}.

Передвигаем правый указатель и получаем l = 0, r = 1 должны добавить число 4 в очередь. Удалим с конца все числа которые небольше числа 4 и получаем dq = {4}.

Передвигаем правый указатель и получаем l = 0, r = 2 так как число a[r] = 2 меньше чем 4 то мы просто добавим это число в очередь и получим dq = {4, 2}.

Передвигаем левый указатель и получим l = 1, r = 2. Когда сдвигается левый указатель - это означает, что мы должны удалить все числа слева которые < a[l]. В этом случае не удаляем ничего так как 4 > a[l] = 1.

Передвигаем правый указатель и получим l = 1, r = 3, наша очередь станет равно dq = {4, 3}.

Передвигаем правый указатель и получим l = 1, r = 4, наша очередь станет равно dq = {5}.

Передвигаем правый указатель и получим l = 1, r = 5, наша очередь станет равно dq = {8}
И так далее.

Самое главное поддерживать инвариант - в очереди числа идут по убывания. Все числа в очереди - это подпоследовательность чисел на отрезке [l, r].
Ответом после каждого сдвига указателя - это левое число в очереди.


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

Задача с собеседования в Яндекс.
Недавно во время собеседования в Яндекс задали вопрос: Что такое диаметр и центр дерева.
Определения можно почитать здесь по ссылке.
В литкоде можно решить соответствующую задачу.
Суть задачи: Нужно найти множество вершин за которое мы можем подвесить дерево, чтобы высота дерева была минимальной.
Решение: Найдем диаметр дерева и все вершины на этом пути.
Пусть вершины на этом пути хранятся в векторе path.
Тогда если длина вектора нечетная ответом будет path[len/2], иначе path[len/2-1], path[len/2].

Задача с собеседования в Яндекс.
Вам дается строка s, которая состоит из маленьких латинских букв.
Пусть в строке k различных букв. Вы должны удалить некоторые буквы из строки s, таким образом, чтобы оставшаяся строка была лексикографически минимальным, и также имело k различных букв. (Каждый символ должен встречаться ровно один раз)

Например
s = bcdacbcd
Ответ abcd (то есть удалили буквы ***a*bcd*)


Решение:
Давайте для каждой буквы найдем правую позицию где она встречается. Из примера выше получим следующие данные.
right_pos = {a: 3, b:5, c:6, d:7}
Давайте пройдемся по строке слева направо поддерживая строку ответа.
Пусть рассматриваем букву s[i], а на префиксе набрали ответ t.
Очевидно нам стоит удалить букву t.back() (то есть последний символ в строке t), если right_pos[t.back()] > i и t.back() > s[i].
На самом деле мы будем удалять буквы с конца строки t, пока выполняется условие выше, так как все буквы, которые удалили мы можем добавить позже, ведь right_pos[t.back()] > i говорит нам о том, что справа найдется буква t.back() и мы сделали только лучше добавив символ меньше.
После добавим букву s[i] в конец строки t.
Ответ - строка t

Разберем на примере выше.
i = 0, t = b
i = 1, t = bc
i = 2, t = bcd
i = 3, t = a
i = 4, t = ac
i = 5, t = ab
i = 6, t = abc
i = 7, t = abcd
Такая идея называется монотонный стек.
Время работы алгоритма O(N).
Псевдокод в комментариях.

Задача с собеседования в Яндекс.
Данная задача встречалась достаточно давно, но все же уметь ее решать будет полезно.
Вам дали массив a состоящая из различных чисел. Известно, что изначально массив был отсортирован по возрастанию, а потом сдвинуть налево на несколько шагов.
Например a = [5, 8, 10, 14, 20, 25, 0, 1, 2, 4]
Ваша задача найти минимальное число в массиве за O(logn)

Решение:
Ясно, что задача очень просто решается за O(n). Достаточно было бы пройтись по массиву и узнать минимальное число.
В задаче нам нужно найти этот элемент за log. Когда видим log мы думаем про деление на два. Но с другой стороны бинарный поиск как будто бы не должен работать, так как массив не является отсортированным.

Давайте скажем что type1 - это первый кусок массива, где все числа возрастали, а type2 - остальная часть. В нашем примере
type1 = [5, 8, 10, 14, 20, 25]
type2 = [0, 1, 2, 4]
По факту наша задача найти первый элемент в type2.

Давайте все таки попробуем написать бинарный поиск. Заранее обработаем особый случай a[0] < a[n - 1] в таком случае можно смело выводить a[0].
Давайте поставим границы бинарного поиска l = 0, r = n - 1, мы пока точно знаем, что a[l] > a[r].
Посмотрим на середину отрезка mid = (l + r) // 2, если a[l] < a[mid] это означает, что mid попал в type1 в таком случае мы можем смело сдвигать левую границу бинарного поиска.
Рассмотрим другой случай, когда a[l] > a[mid] - это означает, что mid попал в type2. Давайте в такие момента сдвигать r.
Вы можете заметить, что мы поддерживали инвариант a[l] >a[r] для всех l, r таких что r - l > 1.
В конце концов мы попадем в позицию минимума.

Важный вопрос, почему при a[l] > a[mid] мы сдвигали именно r, а не l ?
-Если бы сдвигали l у нас могла возникнуть ситуация a[l] < a[r] то есть l и r попали в type2 а этот случай плохой, так как l мог уйти за правую часть минимальной элемента, таким образом на подотрезке l, r не находился бы ответ, а такое в бинарном поиске допускать нельзя. Очень важно, чтобы на подотрезке l, r всегда находился ответ.

Время работы O(logn)

Задача с Яндекса
Дается отсортированный массив a из натуральных чисел, а также дается число k.
За одну операцию вы можете выбрать два индекса (i, j) такие, что k * a[i] <= a[j] и зачеркнуть эти числа. Найдите максимальное количество чисел, которые можно зачеркнуть.

Решение:
Обратите внимание, что массив отсортирован. Также заметим, что мы можем зачеркнуть не более len(a) / 2 пар чисел.
Эти два факта будем использовать в решение.
Очевидно, если вы хотите зачеркнуть cnt пар индексов, мы должны взять cnt минимальных чисел и cnt максимальных чисел (то есть cnt первых индексов и столько же последних индексов).
Мы понимаем, что cnt <= len(a) / 2.
Давайте поставим указатель i = 0 и поставим указатель j = len(a) / 2.
Если k * a[i] <= a[j] мы сдвинем указатели i, j на один, иначе нам выгодно сдвинуть указатель j, так как a[j] станет больше, а a[i] останется минимально возможный.

Важно понять, что от того, что мы поставим j = len(a) / 2, а не меньше, ничего плохого не случится.
Время работы O(N)

Задача с контеста Яндекс
Вам на вход даются два числа 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).
Псевдокод в комментариях.

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

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

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

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

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

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

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

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

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

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

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

Задача с Тинькофф стажировки.
Самая сложная задача с Тинькофф 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] просто найти максимальное число. Далее вернуть максимум из этих двух чисел.
Замечу что находить максимум на отрезке вам поможет дерево отрезков.

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

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

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

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

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
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).

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

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

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

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

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

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

Задача ШАДа
Дают 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

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

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)

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

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

Вам приходит два вида запроса.
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)