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

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

НОД(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

Никогда не оценивайте олимпиады по уровню ⚠️

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

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

Скоро будет большой анонс ❗️

На осенних каникулах мы проведем открытый интенсив по подготовке к муниципальному этапу ВСОШ по информатике.

Сделаем упор на практику, а также разберем базовые алгоритмы, которые часто встречаются

Набор начнется через несколько дней, так что будьте на связи 🥇

Лучшие олимпиады для поступления 🥇

Рассказываю какие олимпиады писать, чтобы поступить

- Актуальный перечень

- Лучшие для новичков

- Если не умеешь программировать

А еще на этих каникулах состоится открытый интенсив по подготовке к олимпиадам по информатике

Зарегистрироваться может любой желающий, набор начнется через несколько дней 🔜