Тренировки по алгоритмам от Яндекса. Лекция 5: «Префиксные суммы и два указателя»
Вставка
- Опубліковано 13 чер 2021
- Расписание тренировок доступно по ссылке: yandex.ru/yaintern/algorithm-...
Чат в Телеграме для общения и вопросов о тренировках: t.me/joinchat/Ve7wRegrZtI0NjIy
![Старейшая нерешённая задача [Veritasium]](/img/n.gif)
Как же хорошо заходит такой формат... спасибо большое за подробные объяснения и легкость языка! Это лучшие качества для человека, который обучает других.
0:19 Префиксные суммы
2:42 Построение массива префиксных сумм
8:02 Ответ на запрос суммы на отрезке (Range Sum Query)
10:26 Реализация RSQ через префиксные суммы
13:26 Задача №1
13:49 Решение за O(NM)
14:42 Решение за О(N + M)
17:04 Задача №2
17:38 Решение за O(N^3)
19:30 Решение за O(N^2)
21:02 Решение за O(N)
26:24 Два указателя
26:35 Задача №3
28:18 Решение за O(N^2)
29:54 Решение за O(N)
36:56 Задача №4
38:00 Решение
46:06 Задача №5
48:19 Неидеальная реализация
51:20 Более близкая к идеалу реализация
53:00 Ответы на вопросы
Спасибо огромное за информативную и полезную лекцию !!!
Очень здорово, мне нравится понятность и доступность :)
Хорошая лекция. Хорошо донесли материал
Большое вам спасибо!
Сразу не совсем понял, почему количество пар равно n * (n - 1) // 2.
Количество способов, которыми можно выбрать k элементов из n элементов (n choose k), определяется по формуле n! / (k! * (n - k)!)
Для k = 2 (выбор пары): (n * (n -1) * (n - 2)!) / (2! * (n - 2)!) = (n * (n - 1)) / 2
узнал про последовательную обработку условий при операции and после частого парса json (проверял есть ли такой ключ и по нему нужное условие), а не из-за хорошего обучения)
Мне кажется, что в задаче 4 на 45:06 можно опустить условие 'first == last'. Так как в этом случае всегда выполнится второе условие: если оба указывают на число A, то A плюс большее число всегда больше А
Пошел в комменты чтобы найти твой коммент
Контрпример: lst= [1, 100], k=4. на второй итерации for у тебя first будет указывать на 100. lst[first+1] выдаст ошибку IndexError - выход за границы массива
Ой, крутой мужик, я у него на курсерии питону училась
А правильно ли задача 2 сформулирована? Такое ощущение, что вы ищете ответ на вопрос "сколько подотрезков, полностью заполненных нулями, есть в последовательности", а не на вопрос "сколько подотрезков с нулевой суммой есть в последовательности"
26:28 начало части про 2 указателя
Почему используете так часто list, вроде как dict работает гораздо быстрее?
Формула подсчёта допустимых отрезков неверна. Если у нас в последовательности встречается 0, то префиксная сумма будет повторяться, а следовательно, будет увеличиваться значение в словаре, но когда мы попытаемся посчитать количество возможных отрезков, то получим неверный ответ, так как отрезки, состоящие ТОЛЬКО из числа и 0 мы брать не можем.
2 вопроса (начало видео):
1. Сказано, что чтобы посчитать сумму с (n; m) для одномерного массива, будет сложность O(N^2), с помощью префиксных сумм - O(N). Разве сложность при подсчёте простым перебором не будет ли O(N) (т.к. достаточно всего одного цикла для одномерного массива), а при подсчёте префиксными суммами - O(const) ?
2. Чтобы создать массив из префиксных сумм, нам нужно пробежаться по данному массиву в любом случае, т.е. затратить время на это. Тогда в чем мы выиграем, если по сравнению с простым перебором массива?
Вопрос в топ! Тоже данный вопрос возник
насчет второго - понятное дело, что префиксные суммы не надо пихать везде, где можно сделать перебор. однако для ситуаций где надо провести одну операцию несколько раз(например, посчитать те же самые нули на нескольких отрезках, а не на одном, как приведено в видео), посчитав префиксную сумму один раз, мы выиграем во времени по сравнению с другим решением
Как я понял, благодаря префиксным суммам можно отвечать на вопросы типа «сколько существует сумм кратных чему то в определенной последовательности чисел». В таком случае использовать два вложенных цикла (начало и конец) т.е переборный алгоритм будет не очень эффективно. Когда у тебя 1000 чисел то конечно, все работает. А вот если у тебя чисел порядка 5 миллионов то переборный алгоритм будет работать вечность
Почему нельзя так решить последнюю?
def s(s1, s2):
"""Даны две отсортированные последовательности, необходимо свести их в одну отсортированную"""
ans = []
sym = 0
for i in s1:
while sym < len(s2) and s2[sym]
потому что если наибольшие элементы содержатся в s2, то они не будут добавлены в ans. Попробуйте прогнать программу например для s1 = (1, 3, 5); s2 = (2, 4, 6, 7, 8)
по поводу пефикса сумма хорошо бы пояснение написать почему количество интервалов N*(N-1)/2, лучше написать и доказательство через матрицу смежности неориентированного графа, там эта формула выводится интуитивно
Мне показалось, что намного проще сказать что это число сочетаний из N по 2, где N это количество ячеек с одинаковой префиксной суммой (выбираем по 2 ячейки из N всеми возможными способами)
1:01:32 не понял все равно почему сложность O(N)? там же два цикла for а затем while?
потому что внутренний цикл выполняется не каждый цикл N раз, а только за все циклы N раз и сложность получается O(N+N) = O(N)
В JavaScript внутри if(some && boolean || logic) выполняются все выражения, и поэтому условие считается целиком.
Потому что тут есть операция "или"
ничего не понял, но очень интересно
Вот решение 2 задачи с нулевой суммой на JS за один проход и без использования комбинаторной функции:
const sumCount = { 0: 1 };
let sum = 0;
let zeroCount = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (!sumCount[sum]) {
sumCount[sum] = 0;
}
zeroCount += sumCount[sum];
sumCount[sum] += 1;
}
console.log(zeroCount);
Считаешь количество нулей,а не количество возможных последовательностей с нулевой ссуммо. Другую задачу решает его алгоритм
За счет чего часть лампы, в которую вкручена лампочка, держится на основной части лампы? Не вижу никакого провода, на котором бы эта часть висела. Она держится за счет магнита какого-то?
Да, в Яндекс маркете чекни
Вставлю свои пять копеек реализации псевдодвух указателей в слияние списка
def merge(arr, arr2):
index1 = index2 = 0
res = []
while index1 < len(arr) and index2 < len(arr2):
if arr[index1] = arr2[index2]:
res.append(arr2[index2])
index2 += 1
return res + arr[index1:] + arr2[index2:]
Ваша программа отработает неверно на примере [1, 2, 5], [4]
@@mberdyshev Поправил))
почему когда мы используем for и затем while то сложность О(n)? Два же цикла должна быть О(n^2)
очень просто, тут на самом деле нет двух циклов, главный цикл это while, а for просто позволяет получить следующий first, таким образом тут нет вложенности, для каждого first не выполняется while по всем N, если точно, то for и while дают O(N+N), таким образом O(N). Посмотрите последовательность для k = 3 [0,4,8,12,16,20,24] и [0,4,4,4,4,4,4,4]
Солнце мое, мы же границу перебора двигаем, в итоге мы только N чисел и переберём
На мой субъективный взгляд, первые 4 лекции все было понятно и просто, как и положено обучающему материалу. А вот понятность, прозрачность и подробность 5ой лекции около нуля. И судя по комментариям, я тут такой не один:)
Что-то я не понял, если префиксная сумма это "текущий + предыдущий", то почему у нулевого элемента со значением 5 префиксная сумма ноль, а не пять?
сам уже понял, это из-за подхода не включения крайнего правого символа в массив)
В задаче 1. Первая реализация выполняется за время O(N*M). Почему не за O(N + M)? Мы же не проходимся по всем элементам снова.
Худший случай, когда все M запросов запрашивают интервал (0; N-1). В таком случае в каждом запросе будет итерироваться весь список длиной N. Отсюда, и сложность O(M*N)
@@mberdyshev а чем является m в данном случае?
Не совсем понимаю, почему 1 решение в 1 задачи, это не O(N), если по сути наш отрезок от l до r только в худшем случае будет равен длине последовательности, то есть по сути сложность должна быть O(N). Можете объяснить, пожалуйста
@@gotrax2661 - это количество запросов, дано по условию задачи.
Всё правильно, в данной реализации в худшем случае мы тратим O(N) операций на один запрос. Так как всего M запросов, то и получаем общую сложность O(N * M).
@@gotrax2661 Насколько я понял, О-большое и описывает всегда худший случай.
В задаче 4. Тест 1 2 3 4 5 должен выдавать 15. Используя вашу реализацию получается 14
Если для теста [1, 2, 3, 4, 5] ответ был бы 15, то тогда нужно задействовать всех игроков. Но сумма слабейших меньше сильнейшего (1+2 < 5), что не соответствует условию задачи.
Для ответа 14, который получается при игроках [2, 3, 4, 5] условие задачи соблюдается (2 + 3 ≥ 5)
@@mberdyshev [1, 1, 3, 3, 4, 6, 11] для такого набора из видео выдаёт 17, а должно 16 ( 3 + 3 + 4 + 6)
а отмена, о берет игроков 6 и 11, сравнивая их между собой, тогда понятно
Эта лекция мне плохо далась
Аналогично, но чую что надо пересмотреть и всё же вникнуть
Я пересматривала задачи по нескольку раз, чтобы идею и реализацию связать
Не боись, ты не одинок, только олимпиадники, наверное, смогут без повтора смотреть, потому что половину уже знают
А для чего это?
Ведь проще написать так:
a = [1,5,2,5,2,5,23,6]
#Найдем сумму от 3 элемента до 6:
s = 0
for i in range(3,6):
s += a[i]
print(s)
Чем писать так:
prefsum = [0] * (len(a) + 1)
for i in range(1, len(a) + 1):
prefsum[i] = prefsum[i - 1] + a[i - 1]
print(prefsum[6] - prefsum[3])
в лекции говорили о том, что если необходимо делать такой подсчёт не один раз, а постоянно, то каждый раз считать суммы (как первом варианте) будет медленнее, чем хранить их и вычислять разность одним действием (как во втором варианте)
@@user-og2oc5kw8p Спасибо) Почему-то мне не очень нравятся уроке от Яндекса. Я нашел другое видео, в котором объяснение более понятное, информации больше и показали интересные задачи, в которых используется префиксная сумма.
@@user-og2oc5kw8p Хотя курс по питону от данного преподавателя на курсере мне понравился.
@@user-do4su2wy3z там раскрыта только эта тема или есть ещё какие-то видео по алгоритмам?)
@@user-og2oc5kw8p вы про видео, которое я смотрел? Там еще рассказали про двумерные преф. суммы, трехмерные и всякие другие штуки.