Тренер по программированию

Решим простую задачу на графы, которая на первый взгляд такой не кажется. Сначала читаем развесистое условие и пытаемся понять, что требуется в задаче: Если переложить на язык алгоритмов, то надо покрыть граф путями. И есть специальные алгоритмы, которые справляются с этой задачей. Но они расчитаны на ориентированные графы. А в этой задаче по каждой дороге можно передвигаться в обоих направлениях. Если упростить задачу и сказать, что есть только один ковбой и спросить, можно ли заблокировать все дороги? Тогда мы получим вариант классической загадки про нарисовать фигуру, не отрывая руки...

Сегодня решим сложную задачу на динамическое программирование про поиск уникальных подпоследовательностей. Читаем условие: Сложность задачи складывается из нескольких пунктов: Напомню, что подстрока - это непрерывная последовательность символов с i-го до j-го. Или, на языке Python - это слайс s[i:j]. А подпоследовательность - это любая последовательность, которая может быть получена из исходной вычёркиванием произвольного числа символов. Количество подстрок O(N^2), а количество подпоследовательностей O(2^N), поэтому перебрать все не получится...

Давно не было решений на С++. Сегодня разберём непростую задачу на динамическое программирование по подмножествам, которую на Python затолкать в ограничения очень сложно. Читаем условие: Почти всегда, когда в задаче есть перебор перестановок, можно решение за O(N!) заменить решением за O(N * 2^N), используя динамическое программирование по подмножествам. Это всё ещё экспоненциальное решение, но константа сильно меньше. В нашем случае, если решать задачу в лоб, то надо каждую перестановку ещё проверять на удовлетворение условий К-перестановки...

Разберём решение ещё одной задачи на динамическое программирование, в которой нет ничего сложного, и можно рассмотреть все шаги решения таких задач. Сначала читаем условие: Алгоритм решения будет точно таким же, как и в задачах Задача 11. Зайчик и Задача 29. Компьютерная игра. Но здесь есть дополнительные ограничения, поэтому рекомендую разобраться с теми задачами и потом вернуться сюда. Как обычно, сначала надо определиться, что будет состоянием динамики. Выберем в качестве состояния длину префикса введённого числа...

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

Разберём ещё одну задачу с регионального этапа Всероссийской олимпиады школьников и поймём, что в ней нет ничего сложного. Читаем условие: Идейно, здесь базовая работа с массивами: Сразу покажу решение, а дальше разберём его особенности: Нам не нужно знать размеры массивов, поэтому в 1 и 3 строках не объявляем никаких переменных, а просто считываем данные вникуда. Также, по массиву p надо пройти всего один раз, поэтому не будем его хранить в отдельной переменной, а сразу запустим по нему (точнее по итератору) цикл в 4ой строке...

Разберём простую задачу на динамическое программирование, автором которой являюсь я сам - сочинил эту задачу для одного из контестов, а потом она попала в архив задач. Читаем условие: Задача является сильным упрощением общего случая с разделением прямоугольника размера NxM, который надо решать с помощью динамического программирования по профилю. В этой же задаче можно поступить проще, рассмотрев все варианты. Для начала считаем размер шоколадки: Сразу можем обработать случай с нечётным N, так как...

Разберём простую прекрасную задачу, в которой есть математика и строгое доказательство. Читаем условие: Для начала надо убедиться, что возможно разложить любое число, большее 7, на сумму пятёрок и троек. Докажем это с помощью математической индукции. База индукции: N = 8 = 5 + 3. Выполняется. Шаг индукции: пусть для всех чисел от 8 от N выполнено, докажем, что и для N+1 имеется разложение. Если в разложении N имеется хотя бы одна пятёрка, то можно заменить её на две тройки, таким образом получим разложение для N+1...

Рассмотрим простую задачу на динамическое программирование, в которой построение ответа почти в два раза больше, чем само решение. Читаем условие: Задача не является продолжением или вариацией задачи 16. Лесенка, но решать будем тоже с помощью динамики. Считаем входные данные и сразу преобразуем их к числовым типам: Состоянием в динамическом программировании будет номер ступеньки, на которой стоит Вова. Чтобы узнать переходы, надо ответить на вопрос "Как Вова мог здесь оказаться?". Ответ очень простой - или с предыдущей ступеньки или через одну от неё...

Несложная классическая задача на структуры данных, которая усложнена форматом входных данных. Читаем условие: Итак, первая сложность в этой задаче - как считать данные? Действительно, нет классического N - количества строк. А это значит, что надо считывать все строки до конца. Построчное считывание в Python можно организовать через следующую конструкцию: Такой цикл считает весь входной файл и сам разделит его на строки. Единственная особенность - в строках l будут находиться и символы переноса строки, поэтому при их обходе надо делать l...

Несложная задача про написание обхода в ширину, на которой можно потренировать и применить несколько трюков. Читаем условие: В этой задаче нужно построить кратчайший путь, поэтому это явно поиск в ширину или BFS. Этот алгоритм подробно разбирали при решении Задачи 127. Путь. Если вы с ним не знакомы, то рекомендую сначала прочитать тот разбор. По условию задачи, поле очень маленькое (помним, что алгоритм BFS работает за линейное время от количества вершин и рёбер в графе, то есть O(V + E)). Поэтому,...

Задача, которая на Python решается практически в одну строчку. Но благодаря ей, познакомимся с ещё одной полезной функцией стандартной библиотеки. Читаем условие: Для начала надо определить, сколько может быть перестановок, чтобы понять, можем ли мы использовать Python или потребуется что-нибудь быстрее. Так как символы не повторяются, количество различных перестановок равно факториалу от N. То есть в самом худшем случае будет 8! = 40,320 перестановок. Вывод очередной перестановки (как и построение следующей из предыдущей) занимает O(N) времени...