‼️ Опубликовали перечень олимпиад по информатике на 25/26 год

Основной перечень выглядит вот так:
1 уровень 🥇

- Вузовско-академическая олимпиада по информатике
- Московская олимпиада школьников
- Олимпиада школьников по информатике и программированию (ИОИП)
- Олимпиада школьников Санкт-Петербургского государственного университета
- Открытая олимпиада школьников (ИТМО)
- Открытая олимпиада школьников по программированию
- Всероссийская олимпиада школьников «Высшая проба»

2 уровень 🥈

- Всесибирская открытая олимпиада школьников 🔽
- Международная олимпиада «Innopolis Open»
- Олимпиада школьников «Гранит науки» 🔼
- Олимпиада школьников «Ломоносов»
- Олимпиада школьников по программированию «ТехноКубок»
- Открытая олимпиада школьников по программированию «Когнитивные технологии»
- Отраслевая физико-математическая олимпиада школьников «Росатом»
- Университетская олимпиада школьников «Бельчонок»

3 уровень 🥉

Международная олимпиада школьников Уральского федерального университета «Изумруд»
- Межрегиональные предметные олимпиады федерального государственного автономного образовательного учреждения высшего образования «Казанский (Приволжский) федеральный университет»
- Олимпиада школьников «Физтех»
- Олимпиада школьников «Шаг в будущее»
- Отраслевая олимпиада школьников «Газпром» 🔽

Из приятных новостей:
- "Бельчонок" все ещё перечневый, даже сохранил второй уровень, так что обязателен для написания
- "Гранит науки" теперь второй уровень, желающие легко поступить - присмотритесь

✔️Перечень хороший, в нем много несложных олимпиад второго уровня. Если хотите подготовиться к ним - 20 сентября стартует курс

Насколько полезна олимпиадная математика на олимпиадах по информатике❓

Ответ: Очень полезна

⚙️Сложные доказательства алгоритмов проще понимать, когда уже имеешь опыт в формальных доказательствах, а идеи придумываются лучше, если решить много идейных задач.

Не зря многие олимпиадники по математике переходят именно в информатику

Если вы хотите ускорить свое развитие, то рекомендую добавить в расписание занятия олимпиадной математикой. Даже один час в неделю ощутимо повлияет на прогресс🔼

Где готовиться к олимпиадам❓

Вот наиболее полезные ресурсы:

- Яндекс Кружок / Кружок Т-Банка

Основным средством подготовки с нуля не станет, так как есть отбор, но чтобы изучить и отработать сложные темы - идеальный вариант

- Яндекс Хэндбук по алгоритмам

Набор статей по некоторым полезным темам. Также есть задачи. Чтобы изучать алгоритмы с нуля подойдет хорошо

- Codeforces

Архив с задачами, на котором проводятся дистанционные олимпиады на внутренний рейтинг. Очень полезная вещь, чтобы научиться не теряться на реальных олимпиадах

- Timus Online Judge

Архив с задачами. Очень полезен, чтобы набить руку. Просто отсортируйте задачи по сложности и просто решайте по 2-3 в день, очень полезная практика.

- Алгоритмика

Сайт с очень понятными и подробными конспектами по алгоритмам. Там хорошо написано про все темы, которые могут встретиться на олимпиаде. Если нужно повторить какую-то теорию - это лучший вариант

⚠️Главная проблема этих ресурсов - приходится заниматься самостоятельно. На первых этапах изучения будет много непонятных вещей, а обратиться за советом или подсказкой будет не к кому

Если хотите избежать этого и легко начать свой олимпиадный путь - завтра стартует курс для начинающих

Узнать подробности или записаться - @nvrmanager

Заявки принимаются до конца сегодняшнего дня🔜

Графы в информатике

#олимпиады@nvmrep

Важная для олимпиад тема, которая достойна целой серии постов

Гуляя по мостам Кёнигсберга, молодой Эйлер задумался, можно ли пройти по всем мостам, переходя по каждому ровно один раз

Эйлер понял, что это невозможно, положив начало теории графов

Что такое граф❓

Граф - это множество объектов (вершин), а также связей между объектами (рёбер).

Такая структура выражает огромное количество зависимостей, а потому представляет большой интерес для математиков.

В информатике существует бесчисленное множество различных алгоритмов для графов. Например, есть алгоритм, для произвольного графа определяющий, можно ли пройти по всем ребрам, посетив каждое ровно один раз.

ℹ️Кстати говоря, в честь задачи о мостах Кёнигсберга граф с таким свойством называется эйлеровым

Как хранить графы❓

Перед тем, как изучать алгоритмы на графы, надо научиться хранить их в памяти компьютера.

Есть 2 варианта:

1. Матрица смежности

Это матрица, состоящая из нулей и единиц. Клетка [u, v] имеет значение 1, если вершины u и v связаны ребром.

2. Списки смежности

Для каждой вершины хранить список вершин, с которыми она связана

В следующем посте по этой теме обсудим обходы графов

Пишите в комментариях, про что еще сделать пост⬇️

Как развиваться в олимпиадной информатике быстро?

#Спортпрога_с_нуля@nvmrep

Всех это волнует, ведь время ограничено, а многие начинают с нуля. Меня часто спрашивают, не поздно ли начать ботать в 11 классе. Начать ботать никогда не поздно, а уже за полгода можно развиться до уровня призера перечня. Но есть важное условие

Ты должен решать задачи. Много. На решение задач, не считая лекции и разборы, необходимо уделять по 4-5 часов в неделю. Обязательно дорешивать после разбора, а если что-то вот совсем не получается, то задавать вопросы более опытному.

🥇Уже через пару месяцев, когда изучите все базовые алгоритмы будете готовы показывать результаты на олимпиадах.

Поиск в глубину

#алгоритмы@nvmrep

Перед прочтением рекомендуется изучить этот пост

⚙️Решим следующую задачу

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

Решение. Давайте возьмем вершину и посмотрим, какие из вершин графа из неё достижимы.
Будет отмечать достижимые вершины. Пусть мы взяли вершину с номером 1. Рассмотрим все вершины, связанные с ней ребром. Они будут достижимы, отметим их. Рассмотрим любую из отмеченных и посмотрим вершины, связанные ребром с ней. Они тоже будут достижимы. Будем рекурсивно продолжать этот процесс до тех пор, пока все достижимые вершины не будут отмечены.

Код

const int maxn = 1e5;
bool used[maxn]; // тут будем отмечать посещенные вершины

void search(int v) {
    used[v] = true;
    for (int u : g[v])
        if (!used[u])
            search(v);

Если в графе осталась неотмеченная вершина - значит она недостижима, а граф несвязный.

ℹ️Такой рекурсивный обход графа называется "поиск в глубину" (сокращенно - DFS), он применяется во множестве задач.

Например:

- Поиск мостов и точек сочленения
- Поиск компонент сильной связанности
- Топологическая сортировка
- 2-SAT

Пишите в комментариях, про какие еще алгоритмы рассказать ⬇️

⚠️Ошибки при написании олимпиад

Буду рассказывать про популярные , которые могут сильно замедлить развитие.

Чем быстрее ты перестанешь так делать, тем быстрее возьмёшь диплом🥇

Одна из вреднейших привычек как при подготовке, так и при написании туров - зацикливаться на одной задаче

Концентрировать свои силы на одном задании можно до 10 минут. Если за это время ты не решил - то дальше сидеть бессмысленно.

Можно пойти подумать над другой задачей, погулять, как-то сменить деятельность и вернуться попозже, но зацикливаться нельзя, это только потратит силы.


💡Бывает так, что решение приходит тогда, когда ты его не ждёшь, так что если решить что-либо сразу не получается - расстраиваться не стоит

Про эйлеровы графы

Первая часть - ссылка

Как же Эйлер понял, что обойти все мосты Кенигсберга нельзя❓

Для этого он сформулировал следующую теорему:

Давайте назовем путь, проходящий через все ребра графа по одному разу эйлеровым. В таком случае, граф имеет эйлеров путь тогда и только тогда, когда в нем не более двух вершин с нечетной степенью

Интуиция следующая:
Чтобы обойти граф, в каждую вершину нужно сначала войти, потом выйти, то есть задействуются два ребра. Исключение могут составлять только две вершины - начальная и конечная.

Проверить граф на наличие эйлерового пути несложно, интереснее такой путь построить. Оказывается, для этого есть алгоритм, работающий за линейное время

Будем рекурсивно обходить граф, удаляя пройденные ребра. Когда рассмотрим все ребра, исходящие из вершины - добавляем её в путь.

Реализация

void euler(int v) {
    while (!g[v].empty()) {
        u = *g[v].begin(); // берем ребро
        remove_edge(v, u); // удаляем его
        euler(u);            // запускаемся от новой вершины
    }
    cout << v <<  " ";     // выписываем текущую вершину
}

Чтобы удалять ребра, можно хранить их в структуре, поддерживающей удаление (set, unordered set), либо хранить массив с информацией о состоянии каждого ребра.

Пишите вопросы в комментариях ⬇️

Динамическое программирование на задачах⚙️

Этот метод проще всего понять, рассматривая реальные задания

Предыдущий пост по теме - ссылка

❗️Задача: K-ичные числа

Рассмотрим N-значные числа в системе счисления с основанием K. Будем считать число правильным, если его K-ичная запись не содержит двух подряд идущих нулей. Например:
- 1010230 — правильное 7-значное число;
- 1000198 не является правильным числом;
- 0001235 — не 7-значное, а 4-значное число.

Даны числа N и K, вычислите количество правильных K-ичных чисел, состоящих из N цифр.

Сначала подумайте сами, если хотите проверить решение - вот ссылка на задачу

💡Решение

Применим метод динамического программирования. Мы можем добавить к правильному числу еще одну цифру, чтобы получить новое правильное число. Если число не кончается на ноль, то мы можем добавить любую цифру. Если нет, то любую, кроме нуля

За dp[i][1] примем количество правильных чисел длиной i, не заканчивающихся на ноль
За dp[i][0] примем количество правильных чисел длиной i, заканчивающихся на ноль

Формулы перехода будут следующие:
dp[i][0] = dp[i - 1][1]
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)

Ответом на задачу будет dp[n][1], так как число не должно заканчиваться на ноль

Пишите в комментариях, по каким еще темам подобрать задачи ⬇️

Алгоритм Евклида: как быстро найти наибольший общий делитель двух чисел?

Если числа большие, то перебирать делители придется долго. На помощь приходит следующее свойство 💡

НОД(a, b) = НОД(b, a mod b)

Повторяем, пока одно из чисел не станет равно 0. Второе и есть ответ.

Пример работы:

НОД(252, 105):
252 mod 105 = 42 → НОД(105, 42)
105 mod 42 = 21 → НОД(42, 21)
42 mod 21 = 0 → НОД = 21 ✔️.

Работает за O(log(min(a, b))), что гораздо быстрее чем просто перебирать делители.

❗️Открылась регистрация на Всесибирскую открытую олимпиаду школьников по информатике

Несложная олимпиада II уровня, хорошо котируется, рекомендуется к написанию

➡️Зарегистрироваться

Что делать, если не получается❓

Не все выходит с первой попытки. Многие думают, что если с самого начала не получается, то у них нет потенциала и продолжать бессмысленно. Но это не так.

Олимпиады не проверяют ваш талант. Они проверяют ваше упорство

Именно упорство отделяет тех, у кто победил, от тех, у кто проиграл.

Будьте упорными и не думайте о поражениях. Тогда успех обязательно придет🥇

Задачи с реальной олимпиады🥇

Это последняя задача с финала олимпиады "Когнитивные технологии" 24 года.

Сначала подумайте сами⚠️

Решение:

Задачу можно решить методом двух указателей. Так как взято было ровно k последовательных клавиш, можно пройтись циклом по строке и проверить все варианты подстрок длины k, поддерживая координаты точки, в которую гуманоид попадет после их нажатия. Чтобы проверить следующую подстроку, достаточно добавить следующий символ и убрать последний. Сложность алгоритма - O(n)

Всего задач на финале было 11, чтобы стать призером решить было достаточно только 5.

Все еще считаешь, что поступить по олимпиадам невозможно?

❗️ Открылась регистрация на олимпиаду школьников "Бельчонок" по информатике

Обязательна для написания школьникам без БВИ, поступающим по информатике

➡️ Подробнее про олимпиаду

➡️ Зарегистрироваться

Как я взял свой первый перечень?

Рассказываю про начало олимпиадного пути

Ноябрь 9 класса. К олимпиадам по информатике тогда даже не прикасался, кое-как программировал на питоне. Передо мной встаёт вопрос о поступлении. Пытался ботать самостоятельно, не получалось ничего

На помощь пришел мой друг, коллега и тогдашний одноклассник - Дима Знышев. Он занимался олимпиадами и рассказал мне всю базу, после чего я начал самостоятельно. Занимался по 10 часов в неделю, решал тимус, писал раунды на Codeforces.

Все шло хорошо, до первой реальной олимпиады - это был регион. Я написал гораздо ниже своих способностей, еле как набрав на призера. Было обидно, но сдаваться было нельзя.

Я продолжил ботать, и уже через месяц после провала случилась первая победа - Технокубок. Был хороший для меня вариант, и я взял призера, окупив все старания

💡Мораль истории такова:
Первое. Начинать ботать самостоятельно очень сложно, не бойтесь просить помощи у более опытных, сэкономите много нервов и времени
Второе. Не бойтесь поражений. Сегодня выпал плохой тур, завтра выпадет хороший. Если записаться на все олимпиады и усердно ботать - все получится.

С момента, когда я начал ботать, до первого диплома прошло 4 месяца.

Надеюсь, эта история кого-нибудь вдохновит на собственные олимпиадные успехи🥇

Наибольшая возрастающая подпоследовательность

⚙️Продолжаем разбирать популярные задачи на динамическое программирование

Задача:

Дан массив целых чисел. Необходимо найти длину наибольшей возрастающей подпоследовательности.

Решается за O(n²) методом динамического программирования

Решение:

Пусть dp[i] - длина НВП, оканчивающейся на элементе с индексом i. Будет заполнять массив dp слева направо.

Заполнение массива будет следующим: если dp[i] = 1, то искомая последовательность состоит только из числа a[i]. Если d[i] > 1, то перед числом a[i] в подпоследовательности стоит какое-то другое число. Переберём его: это может быть любой элемент a[j], такой что j < i, а также a[j] < a[i].

В таком случае,
dp[i] = 1 + max(dp[j]), при условии, что j < i, dp[j] < dp[i]

Ответом на задачу будет максимальное значение массива dp.

Кстати говоря, данное решение далеко не оптимальное. Задачу можно решить за O(n • log(n)), зная определенные структуры данных.

Если есть вопросы, то пишите в комментарии⬇️