# Олимпиадное программирование

## Вопросы:

- random access к памяти в случае ДП?
- garbage collection в С++
- рекурсивные переборы
- все перестановки,
- генерация все вариантов
- генерация с отсечениями
- [Матроиды](https://codeforces.com/blog/entry/69287?locale=ru)
- https://habr.com/ru/post/170933/

## olympiads.ru/zaoch January 2023

- [Дорешивание](https://codeforces.com/gym/104162)

### D

Set<int, 0 или 1> - все отрезки которые пересекают i-й дом (индекс отрезка = день когда выпал снел или его почистили)
- помогает передить от i-го дома к i+1-му
- инициализация
- все отрезки которые влияют на 1-й дом
- переход
- удалить все текущие отрезки которые уже не влияют на i+1 дом (т.е. заканчиваются в i + 1, т.е r_i = i + 1)
- добавить все новые отрезки которые начинают влиять на i+1 (т.е. начинаются в i + 1, т.е l_i = i + 1)

Дерево отрезков - состояние дней для i-го дома - был ли снег на i-м доме в j-й день
- позволяет считать количество заснеженных дней для i-го дома

https://docs.google.com/spreadsheets/d/1u3Wl3LFhWZ9bYTzAVFTrNsdoQlVVDucXMx6hMb9KMUA/edit#gid=0

# Прорешиваем

- [Всероссийская олимпиада школьников по информатике 2022–2023 День 2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)
- Задача 6:
- двумерное ДП: dp[position][mask]
- position (от 0 до 100)
- mask (от 0 до 2^21): 3 бита для каждой цифры (всего 7*3)
- Задача 7:
-

# Прорешали

- [Всероссийская олимпиада школьников по информатике 2022–2023 День 1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf) - кроме 4 задачи