Ваши ощущения⬇️

MITM - Meet In The Middle

Предисловие:
По мотивам задачи C 1-го дня региона...
В основном метод призван помочь, когда вы знаете решение задачи, но оно не проходит по TL, а вот то же решение при ограничениях в 2 раза меньше уже проходит. Обычно в таких задачах асимптотика 2^n и поэтому деление на 2 помогает - получаем 2^{n/2}.
По теории метод простой: делим задачу на две одинаковых (или почти) один раз (не путать с "разделяй и властвуй") и потом объединяем результаты двух половин.
Звучит просто и обычно как поделить на две задачи понятно, но трудности могут возникнуть в объединении. Также, в таких задачах может возникнуть проблема в придумывании решения без деления пополам, так как часто это какое-нибудь ДП по подмножествам.
Поэтому надо нарешать задач на него, чтобы хорошенько прочувствовать

Пререквизиты:
🔙 Перебор всех подмножеств битмасками
🔙 Динамическое программирование по подмножествам

Теория:
📼 Открытая лекция Тинькофф Поколения - разбор набора задач по теме на доске без кода
📼 Видео от красного на кф Errichto - разбор набора задач с кодом, но на английском

Первые задачи:
💻 CSES 1
💻 CSES 2

KIT контест по теме с периодически пополняемыми задачами:
🔄 Контест - сейчас там пока 7 задач, но будут еще. Для решения нужно вступить в группу на кф - ссылка

Вопросы на понимание темы:
В этот раз без них, так как надо задачи решать😉

Делитесь с друзьями, задачи будут интересны любому уровню!

💬 Следующие темы смело предлагайте в комментариях. Также, делитесь интересными задачами и материалами по этой теме, тут их точно еще полно)

Автор: https://www.tgoop.com/KogutIvanTutoring

Теги: #алгоритмы #методы #meet_in_the_middle #динамическое_программирование

Как AI решает олимпиадное программирование?

В декабре 2022 года Google DeepMind представили свою систему решения задач по программированию - AlphaCode. И если тогда это выглядело не очень, то новая версия AlphaCode 2, которая вышла в декабре 2023 года, уже дает повод понервничать (смотри результаты в конце поста)

👨‍💻 Посмотреть, как система пишет код и на какие места в условии она обращает внимание во время написания, можно по ссылке

А я начну рассказывать с первой версии

Что было в AlphaCode:
🔄 Pretrain модели. 715 GB кода из гитхаба. Делили файл на 2 части: 1 - в энкодер, 2 - в декодер, чтобы он выучился ее восстанавливать
🔄 Finetune модели. 2.6 GB датасет из условий задач, правильных и неправильных решений и тестов из условия
🔄 Sampling. Генерируется много решений для одной задачи
🔄 Filtering. Фильтруются программы, которые не прошли по тестам из условия или не скомпилировались
🔄 Clustering. По условию генерируются новые тесты другой моделью. Решения прошедшие фильтрацию группируются в кластеры по правилу: одинаковые ответы на сгенеренные тесты -> решения попадают в один кластер
🔄 В конце из каждого кластера из топ-10 по размеру берется одно решение и все 10 решений отправляются в систему

Результат AlphaCode:
📊 Решила 25% задач из 12 контестов codeforces div.2 или div.1+2
📊 Лучше чем 46% людей с codeforces на этих контестах

AlphaCode 2. Отличия и нововведения:
🔄 Претрейн модели Gemini PRO модель от гугла в качестве основной
🔄 Finetune. Чуть расширили датасет
🔄 Одна модель Finetune несколько моделей с разными гиперпараметрами
🔄 Брать произвольное решение из кластера Finetune еще одной Gemini PRO модели для оценки правильности решения. Берут из каждого кластера топ-1 решение по оценке этой модели

Результат AlphaCode 2:
📊 Решила 43% задач из 12 контестов codeforces div.2 или div.1+2
📊 Лучше чем 85% людей с codeforces на этих контестах
📊 По уровню между синим и фиолетовым рейтингом на кф

Автор: https://www.tgoop.com/KogutIvanTutoring

Теги: #алгоритмы #AI #Нейросети

Матрицы и их умножение

Предисловие:
Вам не нужно знать все о матрицах, чтобы пользоваться ими на олимпиадах) Курс линейной алгебры тут не нужен

Достаточно этого:
* Матрица - это двумерный (одно из измерений может быть равно единице) набор чисел
* Как работает умножение матриц: суть, алгориитм и время его работы

И дальше нужно научиться видеть (через решение задач естественно), где можно задачу свести к умножению матриц или возведению матрицы в степень. В последнем случае можно получить ускорение за счет бинарного возведения в степень, с матрицами этот трюк тоже работает.
Это может пригодиться, например, в пересчете ДП. А самым базовым примером является задача нахождения n-го числа Фибоначчи быстрее чем O(n)😱 Как это возможно, узнаете ниже)

Пререквизиты:
🔙 Сумма, вычитание, произведение, деление по модулю
🔙 Бинарное возведение в степень
🔙 Базовое ДП

Теория:
📚 Алгоритмика 1 - определение матриц и их умножения + код умножения
📚 Алгоритмика 2 - как использовать умножение матриц в задачах, n-ое число Фибоначчи и другие задачи
📼 Видео от красного на кф Errichto (На английском) - очень подробное объяснение как решать несколько задач на тему

KIT контест по теме с периодически пополняемыми задачами:
🔄 Контест - в этот раз просто взял контест от Errichto, очень он хорош для отработки: простые и сложные задачки. Для решения нужно вступить в группу на кф - ссылка

Вопросы на понимание темы:
❓ За какое время работает умножение матрицы размером NxK на матрицу размером KxM?
❗️ O(N * M * K)

❓ Что делать, если в реккуренту затесалась константа? Например, a2 = a1 + a0 + 5. Как тогда посчитать n-ое значение с помощью умножения матриц?
❗️Как минимум 2 способа. 1) Немного отойти от общего случая (как в алгоритмике 2 описано) и составить немного другую матрицу - пишите в комментах какую. 2) Избавиться от этой константы. Можно из a3 вычесть a2, тогда константа (5) сократится и получится новая реккурента. Ее уже общим случаем можно спокойно решить

Автор: https://www.tgoop.com/KogutIvanTutoring

Теги: #алгоритмы #матрицы