Довольно часто необходимо оптимизировать подсчет каких то константных значений. В данной задаче мы рассматривали так называемые префиксные суммы в матрице. То есть для заданной матрицы мы подсчитываем префиксные суммы и уже их используем для быстрого (О(1) по времени) подсчета суммы произвольной подматрицы.
Полный разбор, как обычно, по ссылке ниже!

#task_227 #решаем_задачки_дома

Разбор стратегии максимизации своей суммы у жадного банкомата!

#puzzle_79

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

P.S. Спасибо @Dream_Cat4er за присланную задачу!

#announcement #task_228 #решаем_задачки_дома

Довольно интересная задача с техникой, которую стоит знать. Задача связана с предыдущей #task_227 с префиксными суммами!

#task_228 #решаем_задачки_дома

Смотрим решение для последней головоломки!

#puzzle_80

🎓 Давненько у нас не было задач на динамическое программирование! Надеюсь, вы не забыли этот класс задач 😜

#announcement #task_229 #решаем_задачки_дома

Task #229: Кубики

Задачу можно решить с помощью двумерного динамического программирования. Пусть f(n,k) — количество пирамидок высоты k с основанием n.

Смотрим полный разбор (2 мин)

#task_229 #решаем_задачки_дома

Анонс #230. Быстрый маршрут

Одна из классических задач на поиск оптимального маршрута из точки А в точку B!

Анонс задачи (1 мин)

#announcement #task_230 #решаем_задачки_дома

Task #230. Быстрый маршрут

Задачу можно решить алгоритмом Дейкстры, но его необходимо модифицировать. Вместо расстояния до вершины i будем хранить ...

Смотрим полный разбор (2 мин)

#task_230 #решаем_задачки_дома

UPD: Разбор

Так как 300 и 198 делятся на 6, Петя сможет снять лишь сумму, кратную 6 долларам. А максимальное число, кратное 6 и не больше 500 равно 498.
Итак, как можно снять 498 долларов. Произведём следующие операции:
● 500 – 300 = 200,
● 200 + 198 = 398,
● 398 – 300 = 98,
● 98 + 198 = 296,
● 296 + 198 = 494.
После этого сумма, лежащая в банке, уменьшилась на 6 долларов. Проделываем подобную процедуру 16 раз, после этого Петя снимет 96 долларов. Далее он может снять 300, положить 198 (остается 102 и 96) и снова снять 300.
Итого будет ровно 498 долларов.

#puzzle_82

Теперь и мой говнокод код будут изучать потомки через 1000 лет 😜

#ArcticCodeVault #github

Анонс #231. Обрезка строки

Задача из раздела динамического программирования, дерзайте! Разбор с решением опубликуем в понедельник!

Анонс задачи (1 мин)

#announcement #task_231 #решаем_задачки_дома

Task #231. Обрезка строки

Итак воспользуемся методом динамического программирования. Пусть dl, r - наименьшее кол-во символов, которое следует удалить из подстроки s(l)...s(r)...

Смотрим полный разбор (2 мин)

#task_231 #решаем_задачки_дома

UPD: Разбор

Пункт отправления:
● Первая буква либо Б (2), либо У (21).
● Варианты для вторых букв: БА (21), БК (212), УБ (212), УФА (21221). Получили возможный ответ — УФА.
● Проверим другие варианты для третьих букв: БАБ (212), БАФА (21221), БКБА (21221), БКУ (21221), УБУ (21221), УББА (21221).
Итак, мы определили, что поезд отправляется из Уфы, аналогично определяем пункт назначения и получаем Баку.

#puzzle_83

Анонс #232. Счастливый телефонный номер

Если вы не запрогаете эту задачу за 15 минут, у меня для вас плохие новости!

Анонс задачи (1 мин)

#announcement #task_232 #решаем_задачки_дома

Task #232. Счастливый телефонный номер

Даже если вы сделали задачу перебором, не все так плохо! Но задачу можно решить и за O(1)!

Смотрим полный разбор (2 мин)

#task_232 #решаем_задачки_дома