Задача с Тинькоффа.
Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
Известно, что после выполнения всех операций типа
Входные данные.
В первой строке дают три числа n, m, k.
После m пар чисел задающая ребра графа. После k запросов.
Решение:
Тинькофф любит давать задачи на СНМ.
Во первых заметим, что в конце всех запросов граф станет пустой, этот факт нам очень сильно поможет.
Давайте запросы обрабатывать с конца, то есть сначала k тый запрос, после k-1 и тд до 1 запроса.
Такой подход называется решения оффлайн, так как сначала введем все запросы, а дальше решаем задачу.
И так в конце после всех запросов наш граф пустой, давайте построим СНМ где компонента это отдельная вершина. После когда приходит запрос cut u, v мы будем добавлять вершины u, v в одно множество, а при ask u, v будем узнавать правда ли вершины в одной компоненте.
Стандартное решение с помощью СНМ, главное нужно было заметить, что задачу можно решать оффлайн.
Время работы O(k*logn).
Код в комментариях.
Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
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).
Код в комментариях.
🔥23👍4❤1
Задача с контеста Яндекс
Даются число 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 в дереве.
Не забывайте обработать случай, когда мы в листе.
Таким образом алгоритм получается следующий.
Нам нужна функция, которая умеет добавлять массив в бор, а также умеет считать красоту для одного массива со всеми другими.
Код в комментариях.
Даются число 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 в дереве.
Не забывайте обработать случай, когда мы в листе.
Таким образом алгоритм получается следующий.
Нам нужна функция, которая умеет добавлять массив в бор, а также умеет считать красоту для одного массива со всеми другими.
Код в комментариях.
🔥9❤4👍1👏1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Вот и разбор контеста на стажировку в Яндекс! Обязательно делимся с друзьями. Ждём 1000 шэров (поделиться) с другом и разбираем будущий сезон.
Смотрим! https://youtu.be/Y_DICMm9lxA
Смотрим! https://youtu.be/Y_DICMm9lxA
YouTube
Разбор алгоритмов на стажировку в Яндекс!!
Как затащить собесы: https://news.1rj.ru/str/postypashki_old/1198
Сам код и условия задач: https://news.1rj.ru/str/botalkaaa/17965
Канал по алгоритмам: https://news.1rj.ru/str/algoses
Сам код и условия задач: https://news.1rj.ru/str/botalkaaa/17965
Канал по алгоритмам: https://news.1rj.ru/str/algoses
🔥12🤯6
Задача ШАДа
Дают 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
Дают 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
🔥10❤3👍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)
Код в комментариях.
Как по мне одна из самых сложных задач, благо сейчас такие не попадаются.
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 и я вам советую держать в голове следующие наблюдения:
При 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), давайте лучше заметим, что мы можем воспользоваться следующей
Ответ YES если dp[k][(2^n)-1] = 1, иначе ответ NO.
Остались болезненные моменты с выводом ответа, а также мы не учли порядок задач в котором будет решать i тый ученик.
То есть когда мы зафиксировали i того ученика и маску задач мы должны определить в каком порядке он будет решать эти задачи. Здесь я написал снова дпшку) может вы сможете придумать что то другое.
И так моя дпшка следующая, dp_calc[mask][i] минимальное время чтобы решить все задачи из mask и при этом последняя решенная задача это i. (дпшка такая же как и в задаче коммивояжёра)
Читателю без опыта сложно будет вникнуть, но если хотите разобраться то советую разобраться с темой динамическое программирование по подмножествам.
Время работы O(3^n * k)
Код в комментариях.
🔥15👍5❤2🤗1
Задача на Аналитика
Вам приходит два вида запроса.
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)
Вам приходит два вида запроса.
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)
🔥16❤1👍1
Алгоритмы.pdf
68.4 KB
Специально для вас я подготовил 25 задач, в которых я старался охватить все важные подходы к решению задач, актуальные для собеседований за последние два года
🔥72👍11🍓3❤1
Задача с Озона
(Полное условие в комментариях)
Решение.
Решим задачу жадным алгоритмом.
Создадим очередь 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 оставлю на подумать.
(Полное условие в комментариях)
Решение.
Решим задачу жадным алгоритмом.
Создадим очередь 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 оставлю на подумать.
🔥11❤2👍2
Задача на Аналитика
Изначально у вас нет предметов. Вам поступают запросы, вида добавь предмет с названием 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] и будет предметом который нужно вернуть.
Изначально у вас нет предметов. Вам поступают запросы, вида добавь предмет с названием 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] и будет предметом который нужно вернуть.
🔥13❤2😁2
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
How to забоать алгосы к ШАД за оставшееся время
Товарищи, вступительные ШАД совсем скоро, самое время начать готовиться!
Для начало сравним задачи вступительных 2023 и 2018 года.
Вот несколько задач которые встречались в 2023 году.
https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/19
2018 год
https://news.1rj.ru/str/algoses/69
https://news.1rj.ru/str/algoses/9
Задачи сильно отличаются......
2018 год был аномальным по алгоритмам и сейчас такого уже не делают, так что расслабляемся и не тревожимся.
Лучше всего сфокусироваться на свежих задачах, это касается не только алгосов, но и всего другого. Тот же матанализ, если вы видели задания 2022 года и 2023, то согласитесь во многом общие темы.
И так какие же темы по алгоритмам попадались в прошлом году и какие скорее всего попадутся в этом ?
—Бинарный поиск, два указателя, префиксные суммы, жадные алгоритмы, бинарные деревья, графы.
Первые два этапа обычно состоят из задач на бинарный поиск/два указателя, графы. (в прошлом году было так)
Последний этап - это собес, и скорее всего вам дадут задачу на два указателя/жадные алгоритмы.
Объясню логику почему на последним этапе именно такие задачи.
-Во первых это Яндекс и зачастую на собесах дают задачи со сложностью O(N).
-Во вторых собес длится 30 минут, давать задачи на сложные алгоритмы или сложную идею нет смысла, скорее всего будет задача где можно легко уйти не туда, не учесть подводные камни и наделать багов. Как раз таки темы на два указателя/жадные алгоритмы такие.
На вступительных экзаменах могут встречаться два типа задач: идеиные и простые на реализацию.
Темы из которых обычно составляют идейные задачи - бинарныи поиск, два указателя, префиксные суммы, жадные алгоритмы.
А на просто закодить - бинарные деревья, графы
—Теперь про подготовку:
Чтобы избежать ситуации, когда не удастся решить простую задачу на графах из-за недостаточного знания этой темы, я предлагаю вам ознакомиться с алгоритмами, перечисленными выше. Для этого можно решать простые задачи на соответствующие темы на платформе leetcode. Желательно до-конца марта это одолеть.
Начиная с апреля, мы переходим к решению более сложных задач.
-Для БП и двух указателей берите курс ИТМО (чтобы ссылка работала, нужно зарегаться), если вы прорешали все задачи на бп и два указателя, я уверен вы сможете решить любую задачу из ШАДа на эти темы.
-Префиксные суммы, жадные алгоритмы и бинарные деревья лучше всего решать на Leetcode, ваша цель дойти до уровня медиум.
-По графам не нужно знать супер сложные алгоритмы. Я вам рекомендую acmp, прорешать обязательно 1 часть, а второй части решить хотя-бы по 5 задач на алгоритм Флойда и Дейкстры.
Если вы все эти темы хорошо знаете или осталось еще свободное время для подготоки, я предлагаю вам порешать задачи на монотонный стек, СНМ, ДП.
Такой подход подготовки показал отличные результаты при подготовки к ШАДу и к собеседованиям. А если хотите гарантировано подготовиться к школам по типу ШАДа или тащить алгособесы, то советую наш новый курс по алгоритмам.
Товарищи, вступительные ШАД совсем скоро, самое время начать готовиться!
Для начало сравним задачи вступительных 2023 и 2018 года.
Вот несколько задач которые встречались в 2023 году.
https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/19
2018 год
https://news.1rj.ru/str/algoses/69
https://news.1rj.ru/str/algoses/9
Задачи сильно отличаются......
2018 год был аномальным по алгоритмам и сейчас такого уже не делают, так что расслабляемся и не тревожимся.
Лучше всего сфокусироваться на свежих задачах, это касается не только алгосов, но и всего другого. Тот же матанализ, если вы видели задания 2022 года и 2023, то согласитесь во многом общие темы.
И так какие же темы по алгоритмам попадались в прошлом году и какие скорее всего попадутся в этом ?
—Бинарный поиск, два указателя, префиксные суммы, жадные алгоритмы, бинарные деревья, графы.
Первые два этапа обычно состоят из задач на бинарный поиск/два указателя, графы. (в прошлом году было так)
Последний этап - это собес, и скорее всего вам дадут задачу на два указателя/жадные алгоритмы.
Объясню логику почему на последним этапе именно такие задачи.
-Во первых это Яндекс и зачастую на собесах дают задачи со сложностью O(N).
-Во вторых собес длится 30 минут, давать задачи на сложные алгоритмы или сложную идею нет смысла, скорее всего будет задача где можно легко уйти не туда, не учесть подводные камни и наделать багов. Как раз таки темы на два указателя/жадные алгоритмы такие.
На вступительных экзаменах могут встречаться два типа задач: идеиные и простые на реализацию.
Темы из которых обычно составляют идейные задачи - бинарныи поиск, два указателя, префиксные суммы, жадные алгоритмы.
А на просто закодить - бинарные деревья, графы
—Теперь про подготовку:
Чтобы избежать ситуации, когда не удастся решить простую задачу на графах из-за недостаточного знания этой темы, я предлагаю вам ознакомиться с алгоритмами, перечисленными выше. Для этого можно решать простые задачи на соответствующие темы на платформе leetcode. Желательно до-конца марта это одолеть.
Начиная с апреля, мы переходим к решению более сложных задач.
-Для БП и двух указателей берите курс ИТМО (чтобы ссылка работала, нужно зарегаться), если вы прорешали все задачи на бп и два указателя, я уверен вы сможете решить любую задачу из ШАДа на эти темы.
-Префиксные суммы, жадные алгоритмы и бинарные деревья лучше всего решать на Leetcode, ваша цель дойти до уровня медиум.
-По графам не нужно знать супер сложные алгоритмы. Я вам рекомендую acmp, прорешать обязательно 1 часть, а второй части решить хотя-бы по 5 задач на алгоритм Флойда и Дейкстры.
Если вы все эти темы хорошо знаете или осталось еще свободное время для подготоки, я предлагаю вам порешать задачи на монотонный стек, СНМ, ДП.
Такой подход подготовки показал отличные результаты при подготовки к ШАДу и к собеседованиям. А если хотите гарантировано подготовиться к школам по типу ШАДа или тащить алгособесы, то советую наш новый курс по алгоритмам.
👍9❤4🔥1👌1
Задача ШАДа.
Требуется высадить аллею из 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) будет максимальные числа.
Если хотите лучше подготовиться то записывайтесь на наш интенсив.
Благодарю интенсиву в прошлом году много наших студентов успешно поступили в ШАД.
Так как скоро вступительный в ШАД решил разобрать задачу 2023 года. Эту задачу вы не найдете в открытом доступе.
Требуется высадить аллею из n деревьев. Лунки под деревьями пронумерованы последовательно. Расстояние между деревьями определяется как разность номеров лунок, где они растут. На Марсе могут выжить только k сортов деревьев. Красота одного дерева i-го сорта c_i.
Требуется озеленить Марс с максимальной суммарной красотой. Однако, деревья одного сорта конфликтуют, поэтому их следует садить как минимум на расстоянии k.
В первой строке находится два целых числа
k (1 <= k <= 5) и n (1 <= n <= 10^5)
В следующей строке следуют k целых чисел c_i (1 <= c_i <= 10^5)
Решение:
Визуально можно представить так: |........|........|........|........|........|....
Заметим что в одном блоке не могут быть двух деревьев одного сорта. Хммм
Ну чтобы у нас не было пустых ячеек мы должны каждую ячейку блока заполнить, следовательно в каждом блоке перестановка ci - тых.
Тогда почему бы не использовать в каждом блоке следующий порядок : с1, c2, ..., ck ?
Потому что последний блок может быть длины < k, а туда нам выгодно расставить максимальные ci-тые.
Тут вы уже должны понять в каком порядке нам сажать....
Давайте отсортруем наш массив по убыванию c, и будем расставлять в каждом блоке c1, c2, .., ck, так мы получим, что в последнем блоке (который может быть длины < k) будет максимальные числа.
Если хотите лучше подготовиться то записывайтесь на наш интенсив.
Благодарю интенсиву в прошлом году много наших студентов успешно поступили в ШАД.
🔥15❤3👍3
План подготовки.pdf
65.1 KB
Твой план подготовки к собесу и ШАД.
При изучение алгоритмов, новички зачастую сталкиваются с множеством вопросов: в каком порядке следует изучать материал, сколько задач нужно решать, и где их лучше всего искать. Чтобы сделать это путешествие по миру алгоритмов более приятным и продуктивным, я разработал для вас тщательно составленный план подготовки, включающий полезные ссылки и материалы.
Также приглашаю вас на интенсив по алгоритмам на котором мы познакомимся со всеми важными темами и прорешаем более 200 задач.
При изучение алгоритмов, новички зачастую сталкиваются с множеством вопросов: в каком порядке следует изучать материал, сколько задач нужно решать, и где их лучше всего искать. Чтобы сделать это путешествие по миру алгоритмов более приятным и продуктивным, я разработал для вас тщательно составленный план подготовки, включающий полезные ссылки и материалы.
Также приглашаю вас на интенсив по алгоритмам на котором мы познакомимся со всеми важными темами и прорешаем более 200 задач.
🔥27❤2👍2
Эпичная программа от института, о котором вы еще не слышали!
Устали от стресса, боитесь не потянуть конкуренцию в ШАД, Тинькофф, и другие школы, но очень хотите повысить квалификацию, научиться новому или сменить направление?
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 марта.
Программа и подробности.
Устали от стресса, боитесь не потянуть конкуренцию в ШАД, Тинькофф, и другие школы, но очень хотите повысить квалификацию, научиться новому или сменить направление?
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 марта.
Программа и подробности.
❤10👍4🔥4😁3🤣2❤🔥1🤔1
Задача от который посыпалось много аналитиков.
Условия задачи выше.
Решение:
Весь разбор к сожалению не влезет, я рекомендую смотреть код и читать короткий разбор.
Нам нужно 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)
Код в комментариях.
Условия задачи выше.
Решение:
Нам нужно 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)
Код в комментариях.
❤🔥3❤2👍2
Задача ШАДа
Мощностью элемента массива назовем сумму максимального элемента, стоящего справа от него и максимального элемента стоящего от него слева.
Мощность крайних элементов будем считать равной 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.
У вас имеется первоначально пустой массив к которому по очереди справа приписываются 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)
Код в комментариях.
❤8👍2❤🔥1⚡1🥰1🤨1
Задача из Яндекса
Дается массив из 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)
Код в комментариях:
Дается массив из 0 и 1. Ваша задача выбрать такую позицию нуля, чтобы минимальное расстояние до единицы было максимальным.
Например 100110001
ответом будет позиция 6. 100110001. В задаче нельзя использовать дополнительную память, то есть можете использовать только О(1) дополнительной памяти.
Решение:
Аналогично если массива заканчивается на 0 то претендент на ответ это позиция n - 1.
Теперь разберемся с остальными кейсами,пусть i1, i2, ,..., ik позиции где стоят единички, тогда очевидно претендентом на ответ будет нолик по середине между двумя соседними единицами, например в случае 1000001 ответом будет ноль по середине 1000001.
С идеей разобрались, теперь мы должны подумать как найти ответ без дополнительной памяти.
Конечно если бы знали ближайший слева и ближайший справа единичку для каждой позиции i то смогли бы очень просто решить задачу, но чтобы знать ближайший слева или ближайший справа единичку нам нужно создать дополнительный массив.....
Давайте хранить переменную last_one -которая будет хранить ближайший слева позицию единички от позиции i. (i - цикл по которому идем слева направо)
Если a[i] == 1 то есть встретили единичку, то мы понимаем что до этого единичка была в позиции last_one и нам выгоднее всего выбрать позицию (i + last_one) // 2 (конечно если там ноль)
Таким образом мы смогли решить задачу без дополнительной памяти.
Время работы алгоритма O(n)
Код в комментариях:
❤16👍6👏1
Задача из ШАДа.
Так как скоро вступительные в ШАД я решил разобрать вам задачу из 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)
Код в комментариях.
Так как скоро вступительные в ШАД я решил разобрать вам задачу из 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)
Код в комментариях.
❤6🔥3
Вот и задания на стажировку в Тинькофф! Одну из самых масштабных стажировок сезона, задание на этот раз поприятней: формулировки хотя бы понятны. Поэтому дерзайте, товарищи, открыта куча позиций, не упускаем возможность отлично провести лето: прокачаться в своей карьере и образовании😎😎
Задания в БОТАЛКЕ. Там же можно обсуждать.
Задания в БОТАЛКЕ. Там же можно обсуждать.
🔥5
Тесты стажирвоки в Тинькофф также вложены в БОТАЛКЕ.
Там же обсуждаем задания с товарищами и любимым админом 🥰
Кстати тесты совсем простые, достаточно чата gpt.
Там же обсуждаем задания с товарищами и любимым админом 🥰
Кстати тесты совсем простые, достаточно чата gpt.
🔥5❤2🗿1