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

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

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

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

Концентрировать свои силы на одном задании можно до 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)), зная определенные структуры данных.

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

Советы начинающим💡

Ищи олимпиадное окружение. Чем больше опытных олимпиадников в твоем круге общения, тем быстрее ты развиваешься.

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

Что делать, если я не умею программировать❓

Если вы не хотите учиться программированию, но хотите поступить без ЕГЭ, то есть немало перечневых олимпиад по теоретической информатике

Вот список лучших:

- Бельчонок - 2 уровень

- Гранит науки - 2 уровень

- Изумруд - 3 уровень

- Олимпиада ИТМО - 1 уровень

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

⚠️Ошибки при подготовке к олимпиадам

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

Алгоритмы это важно, но без умения придумывать идеи они бесполезны. Достаточно изучить базовые методы, а упор делать именно на решение разных задач.

Побеждает не тот, кто знает больше алгоритмов, а тот, кто решил больше задач🥇

Зачем учить алгоритмы❓

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

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

Набираю учеников‼️

Подготовка к олимпиадам по информатике в мини-группах

Формат занятий:

- В группах по 5 человек
- Раз в неделю
- Длительность - 1-1.5 часа
- Чередуем лекции и разборы задач

Уровень знаний:

- Готовлю к олимпиадам по информатике с нуля
- Единственное требование - базовое знание любого языка программирования

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

Стоимость: 1600 руб. за занятие

Отзывы (страница на Авито)

❗️ Предлагаю бесплатное пробное занятие

Задать вопрос или записаться - @nvrmanager

⚠️Количество мест ограничено, возьму не более 2 групп

Вебинар окончен, спасибо всем, кто присутствовал 👍

Записи будут отправлены в ближайшее время

Занятия скоро начнутся 🔜

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

Что произойдет на занятии ❓

- Расскажу все про олимпиады по информатике
- Объясню, на какие олимпиады нужно регистрироваться, чтобы поступить
- Начнём готовиться и познакомимся с понятием асимптотики

Подробнее - пост

Задать вопрос или записаться - @nvrmanager