по многочисленным запросам открыл комментарии
постепенно людей становится все больше, через неопределенное количество времени напишу полноценный пост знакомство
❤6🔥1
#алгоритмы
Префиксные суммы
Решим задачу:
Если запрос был бы один, то мы бы просто посчитали сумму напрямую. Однако если запросов много, то такое решение имеет сложность O(q • n), что много. Необходимо уметь отвечать на запрос быстро.
Давайте обозначит за S[l, r] сумму элементов массива от l до r. Заметим следующее.
То есть, чтобы посчитать любую сумму достаточно для любого x знать сумму первых x элементов массива.
Сумму первых x элементов массива назовем префиксной суммой и будем обозначать за P[x]. Посчитать все префиксные суммы легко, так как
Теперь сумму от l до r можно посчитать, как
Предподсчет имеет сложность O(n), каждый запрос обрабатывается за O(1). Суммарная сложность алгоритма - O(n + q).
Задачи:
- Найдите сумму на отрезке
Префиксные суммы
Решим задачу:
Дан массив a из n чисел. Также дано q запросов. Каждый запрос состоит из двух чисел l и r. Для каждого запроса выведите сумму элементов массива с индексами от l до r включительно.
Если запрос был бы один, то мы бы просто посчитали сумму напрямую. Однако если запросов много, то такое решение имеет сложность O(q • n), что много. Необходимо уметь отвечать на запрос быстро.
Давайте обозначит за S[l, r] сумму элементов массива от l до r. Заметим следующее.
S[l, r] = S[1, r] - S[1, l - 1]
То есть, чтобы посчитать любую сумму достаточно для любого x знать сумму первых x элементов массива.
Сумму первых x элементов массива назовем префиксной суммой и будем обозначать за P[x]. Посчитать все префиксные суммы легко, так как
P[x + 1] = P[x] + a[x + 1]
Теперь сумму от l до r можно посчитать, как
S[l, r] = P[r] - P[l - 1]
Предподсчет имеет сложность O(n), каждый запрос обрабатывается за O(1). Суммарная сложность алгоритма - O(n + q).
Задачи:
- Найдите сумму на отрезке
❤7🔥2
#Спортпрога_с_нуля
Про кружки от Яндекса и Т-банка
В начале каждого учебного года стартуют кружки по спортивному программированию от Яндекса и Т-банка. Оба имеют одинаковый формат: раз в неделю проходит лекция по теме и появляется контест. Лекции выходят в записи и лежат в открытом доступе.
Кружок делится на несколько параллелей по уровню.
Кружок бесплатный, но есть отбор, который имеет формат длинного тура. Он начинается 18 августе, заканчивается 8 сентября.
Кружки нужны, чтобы изучать продвинутые темы и нарешивать на них задачи.
Главная проблема - большой порог входа. Это не то место, где вы сможете начать ботать с нуля, ибо отбор не самый простой.
Тем не менее, настоятельно рекомендуется поучаствовать в отборе, тем более, что зарегистрироваться все еще можно.
Оба кружка имеют одинаковый формат, но от себя рекомендую именно кружок от Яндекса, там преподаватели получше и мерч интереснее.
Ссылки:
Яндекс кружок
Кружок Т-банка
Про кружки от Яндекса и Т-банка
В начале каждого учебного года стартуют кружки по спортивному программированию от Яндекса и Т-банка. Оба имеют одинаковый формат: раз в неделю проходит лекция по теме и появляется контест. Лекции выходят в записи и лежат в открытом доступе.
Кружок делится на несколько параллелей по уровню.
Кружок бесплатный, но есть отбор, который имеет формат длинного тура. Он начинается 18 августе, заканчивается 8 сентября.
Кружки нужны, чтобы изучать продвинутые темы и нарешивать на них задачи.
Главная проблема - большой порог входа. Это не то место, где вы сможете начать ботать с нуля, ибо отбор не самый простой.
Тем не менее, настоятельно рекомендуется поучаствовать в отборе, тем более, что зарегистрироваться все еще можно.
Оба кружка имеют одинаковый формат, но от себя рекомендую именно кружок от Яндекса, там преподаватели получше и мерч интереснее.
Ссылки:
Яндекс кружок
Кружок Т-банка
❤7
Квадрат Тьюринга | Олимпиады по информатике pinned Deleted message
Про репетиторство
#Информация
У меня часто спрашивают про репетиторские услуги. Я преподаю, но на индивидуальные занятия сейчас не набираю.
❗️ Я практикую два формата:
🔥 Занятие в мини-группах
⭐️ Занятия для начинающих
#Информация
У меня часто спрашивают про репетиторские услуги. Я преподаю, но на индивидуальные занятия сейчас не набираю.
В группе от 2 до 5 схожих по уровню людей. Заниматься таким образом эффективнее, интереснее и дешевле, а мне не нужно тратить время, рассказывая один и тот же материал по несколько раз, так что все в плюсе.
В середине сентября я начну проводить занятия для начинающих в спортивном программировании. Проводиться они будут на протяжении 2.5 месяцев, занимаемся по формату Яндекс кружка. В курсе будут все необходимое, чтобы в дальнейшем развиваться и успешно писать олимпиады.Если какой-то из этих вариантов вас интересует, то пишите в лс: @nvrmanager
Please open Telegram to view this post
VIEW IN TELEGRAM
❤8👍1🔥1
Динамическое программирование
#алгоритмы
Изложить все тонкости динамического программирования в одном посте невозможно, но саму идею я объясню.
Решим задачу
Идея. Давайте для каждой клетки сохранять количество способов до неё добраться. Для клетки i обозначим это число за dp[i]. Тогда, будет верно следующее соотношение.
Теперь достаточно пройтись циклом по всем i от 2 до n, итеративно считая dp. Асимптотика такого решение составит O(n)
Это и есть метод динамического программирования - свести задачу к меньшей и сохранять ответы. Таким методом можно решать задачи не только на поиск количества вариантов, но и максимизацию или минимизацию определенной величины (вместо суммы использовать max или min соответственно). Главное - для каждого состояния знать, как в него можно перейти.
Приводить конкретные примеры задач не буду, так как на Тимусе есть целый раздел, посвященный этой теме.
В дальнейшем сделаю пост про задачу о рюкзаке.
#алгоритмы
Изложить все тонкости динамического программирования в одном посте невозможно, но саму идею я объясню.
Решим задачу
Есть n клеток. На первой клетке находится кузнечик. Он умеет прыгать вперед на одну или на две клетки. Посчитайте количество способов добраться до последней клетки.Рассмотрим последнюю клетку и подумаем, как кузнечик мог в неё попасть. Попасть в клетку n кузнечик может из клетки n - 1, а также n - 2. Соответственно, если мы знаем, сколько способов добраться до этих клеток, то сложив их, мы посчитаем ответ на задачу.
Идея. Давайте для каждой клетки сохранять количество способов до неё добраться. Для клетки i обозначим это число за dp[i]. Тогда, будет верно следующее соотношение.
dp[i] = dp[i - 1] + dp[i - 2]
Теперь достаточно пройтись циклом по всем i от 2 до n, итеративно считая dp. Асимптотика такого решение составит O(n)
Это и есть метод динамического программирования - свести задачу к меньшей и сохранять ответы. Таким методом можно решать задачи не только на поиск количества вариантов, но и максимизацию или минимизацию определенной величины (вместо суммы использовать max или min соответственно). Главное - для каждого состояния знать, как в него можно перейти.
Приводить конкретные примеры задач не буду, так как на Тимусе есть целый раздел, посвященный этой теме.
В дальнейшем сделаю пост про задачу о рюкзаке.
❤7
Олимпиада Учи.ру по информатике дает 25 баллов на отборочном этапе Технокубка, если написать её без ошибок.
Сама она перечневой не является, но, как способ упростить себе отбор, имеет место быть.
Сама она перечневой не является, но, как способ упростить себе отбор, имеет место быть.
Олимпиада по информатике
Олимпиада Учи.ру по информатике проходит с 26 августа по 29 сентября для дошкольников и учеников 1–11 классов. Участие в олимпиаде бесплатное.
❤5🔥1
Какие олимпиады писать, чтобы поступить🔤
#олимпиады
🔥 Прикрепляю список олимпиад по информатике, которые я настоятельно рекомендую писать даже новичкам.
❗️ Писать стоит все олимпиады, но именно эти - в первую очередь.
Постепенно буду делать более детальные посты про олимпиады из этого списка.
Пишите в комментариях, про что еще написать💡
#олимпиады
1. Технокубок
2. СПбГУ
3. Бельчонок
4. Когнитивные технологии
5. Высшая проба
Постепенно буду делать более детальные посты про олимпиады из этого списка.
Пишите в комментариях, про что еще написать
Please open Telegram to view this post
VIEW IN TELEGRAM
❤7👍3🔥2❤🔥1
Олимпиада СПбГУ - самая простая олимпиада первого уровня
#олимпиады
❗️ Если вы искали несложную олимпиаду по программированию первого уровня - то присмотритесь.
➕ Плюсы:
🗓 Расписание:
🔗 Ссылки:
- Сайт олимпиады
- Задания прошлых лет
Пишите в комментариях, про какие еще олимпиады рассказать💡
#олимпиады
- Уровень I
- Задачи идейно несложные
- Длинный отборочный тур
Отборочный тур длится долго, около 2 месяцев (в прошлом году - с 1 ноября до 13 января), поэтому написать его сможет даже начинающий.
Финал олимпиады проходит в феврале (в прошлом году - 15 февраля) и является довольно простым, но имеет широкий разброс тем.
⚠️
Постоянно встречаются
интерактивные
задачи, задачи с
двойным запуском
, а также задачи с
потестовой оценкой
.
- Сайт олимпиады
- Задания прошлых лет
Пишите в комментариях, про какие еще олимпиады рассказать
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача о рюкзаке
#алгоритмы
Перед прочтением данной статьи рекомендую прочитать статью про динамическое программирование
🖥 Решим задачу:
Заметим, что если у нас есть набор предметов массой W, в который не входит предмет с номером j, то мы можем добавить этот предмет в набор, получив суммарную массу W + a[j]. Это наталкивает на использование динамического программирования, осталось только понять, что взять за состояние.
💡 Идея: Пусть dp[j][W] равно единице, если можно набрать массу W, используя первые j предметов. Это будет наше состояние, теперь опишем переходы.
Рассмотрим последний предмет. Если мы его не берем, значит нам надо набрать ту же массу при помощи первых j - 1 предметов. Если мы берем, то нам надо набрать массу W - a[j]. Таким образом, dp[j][W] можно пересчитать, как
➡️ Чтобы решить задачу, достаточно пройтись по всем значениям двумя циклами. Внешним циклом перебираем число j, внутренним - число W. Ответом будем максимальное число i такое, что dp[n][i] = 1.
⏱ Асимптотика такого решения составит - O(n • S)
Тема непростая, так что если есть вопросы - обращайтесь
🔗 Ссылка на контест на информатиксе
#алгоритмы
Перед прочтением данной статьи рекомендую прочитать статью про динамическое программирование
Есть n предметов, предмета i имеет массу a[i]. Есть рюкзак, который может вместить предметы, с суммарным весом не более S. Необходимо найти такой набор предметов, что их суммарная масса максимальна, но не превосходит S.
Заметим, что если у нас есть набор предметов массой W, в который не входит предмет с номером j, то мы можем добавить этот предмет в набор, получив суммарную массу W + a[j]. Это наталкивает на использование динамического программирования, осталось только понять, что взять за состояние.
Рассмотрим последний предмет. Если мы его не берем, значит нам надо набрать ту же массу при помощи первых j - 1 предметов. Если мы берем, то нам надо набрать массу W - a[j]. Таким образом, dp[j][W] можно пересчитать, как
dp[j][W] = dp[j - 1][W] or dp[j - 1][W - a[j]]
Тема непростая, так что если есть вопросы - обращайтесь
Please open Telegram to view this post
VIEW IN TELEGRAM
👍5❤3
#информация
Занимаемся в большой группе, допустим 20 человек. Лекции и домашние задания заранее заготовлены, занимаемся каждую неделю на протяжении 2.5 месяцев.
Каждое занятие оплачивается отдельно и выходит дешевле, чем в маленьких группах.
Подходит тем, кто вообще не имеет опыта в спортивном программировании и хочет легко войти в олимпиадную среду.
Для занятий требуется знать базовые конструкции любого языка, что с нуля изучить легко
Напишите в комментариях, что думаете по поводу такого формата
Please open Telegram to view this post
VIEW IN TELEGRAM
❤5🔥3
Навигацияℹ️
#информация
Для удобства читателей оставляю ссылки на ключевые вещи
🖥 Посты:
🎙 Рубрики:
По всем вопросам - @nvrmanager
#информация
Для удобства читателей оставляю ссылки на ключевые вещи
- Знакомство
- Как ботать с нуля?
- Какие олимпиады писать?
- Репетиторские услуги
#информация - организационные моменты
#алгоритмы - конспекты по разным алгоритмам
#олимпиады - обзоры олимпиад
#Спортпрога_с_нуля - советы тем, кто начинает самостоятельно ботать
По всем вопросам - @nvrmanager
Please open Telegram to view this post
VIEW IN TELEGRAM
❤6🔥2🥰1
Главный совет начинающим олимпиадникам - забейте на Всош⚠️
Жутко нестабильная олимпиада, которая может забрать у вас много сил и времени, не дав ничего взамен. Ставить свое поступление на всош даже хуже, чем поступать по ЕГЭ.
Сфокусируйтесь на перечнях. Узнайте, какие олимпиады котируются на желаемое направление, и зарегистрируйтесь на каждую. Если на хотя бы одной покажете хороший результат - то вы поступили, а всерос оставьте безумцам, занимающимся со средней школы.
Жутко нестабильная олимпиада, которая может забрать у вас много сил и времени, не дав ничего взамен. Ставить свое поступление на всош даже хуже, чем поступать по ЕГЭ.
Сфокусируйтесь на перечнях. Узнайте, какие олимпиады котируются на желаемое направление, и зарегистрируйтесь на каждую. Если на хотя бы одной покажете хороший результат - то вы поступили, а всерос оставьте безумцам, занимающимся со средней школы.
Please open Telegram to view this post
VIEW IN TELEGRAM
❤13👍3
Открыта регистрация на олимпиады Изумруд и Высшая Проба❗️
Рекомендую всегда регистрироваться на максимальное количество олимпиад, чтобы повысить шансы.
Рекомендую всегда регистрироваться на максимальное количество олимпиад, чтобы повысить шансы.
Please open Telegram to view this post
VIEW IN TELEGRAM
❤6
Стоимость обучения в вузах в зависимости от баллов ЕГЭ предложили ввести в Петербурге❗️
Такая инициатива может вернуть смысл поступать по егэ, так как пропадает риск получить на 1 балл меньше порога и не пройти на бюджет, обесценив всю подготовку. Однако все зависит от самих скидок, ведь цены на образование все равно огромные.
А еще, учитывая скорость, с которой вводятся подобные законопроекты, воспользоваться такой системой тем, кто старше 9 класса лучше не расчитывать
⬇️ Пишите в комментарии, что думаете
- Чем выше результат, полученный абитуриентом при сдаче Единого государственного экзамена, тем ниже должна быть для него плата за обучение. На сегодняшний день отличник, набравший больше 90 баллов, недобравший до бюджета, платит за занятия столько же, сколько и тот, кто поступил с 50 баллами. Это абсурд и несправедливость
Такая инициатива может вернуть смысл поступать по егэ, так как пропадает риск получить на 1 балл меньше порога и не пройти на бюджет, обесценив всю подготовку. Однако все зависит от самих скидок, ведь цены на образование все равно огромные.
А еще, учитывая скорость, с которой вводятся подобные законопроекты, воспользоваться такой системой тем, кто старше 9 класса лучше не расчитывать
Please open Telegram to view this post
VIEW IN TELEGRAM
👍10🔥5
Олимпиады второго уровня - зачем они нужны?
#олимпиады
Олимпиады второго уровня дают не сильно меньше льгот, чем олимпиады первого, но они легче, поэтому начинающим рекомендуется делать упор именно на этот разряд.
ℹ️ Например, любая олимпиада второго уровня дает поступление без экзаменов на направление "Информационные системы" университета ИТМО. А это очень хорошее направление в престижном вузе, проходные на него начинаются от 290 баллов.
💡 А вот чтобы взять олимпиаду Бельчонок, имеющую второй уровень достаточно прорешать немного пробников, тем более, времени ещё очень много.
Выбирайте, что вам проще
#олимпиады
Олимпиады второго уровня дают не сильно меньше льгот, чем олимпиады первого, но они легче, поэтому начинающим рекомендуется делать упор именно на этот разряд.
Выбирайте, что вам проще
Please open Telegram to view this post
VIEW IN TELEGRAM
❤9🔥5👍2
На каком языке писать?
#Спортпрога_с_нуля
Для олимпиад актуальны два языка - Python и C++
ℹ️ Python проще в освоении, его учат в школах, так что большинство олимпиадников в первое время пишут именно на нем. Но постепенно приходится пересаживаться на C++, так как он быстрее.
⚠️ Взять перечень на питоне можно, но пересесть на плюсы сильно проще, чем писать олимпиады с таким утяжелением.
➡️ Если не знаете, с чего начать, то изучайте питон (хороший курс на степике), когда привыкните и освоите базовые алгоритмы - начинайте писать на плюсах (хороший курс от яндекса)
⬇️ Пишите в комментариях, про что еще написать
#Спортпрога_с_нуля
Для олимпиад актуальны два языка - Python и C++
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥5❤4
500 человек в канале!
Первое круглое число и очень важная для меня отметка💖
Приятно видеть, как наше сообщество растет и развивается, я надеюсь так будет продолжаться до момента, пока каждый не возьмет свой диплом
Спасибо всем за актив👍
Первое круглое число и очень важная для меня отметка
Приятно видеть, как наше сообщество растет и развивается, я надеюсь так будет продолжаться до момента, пока каждый не возьмет свой диплом
Спасибо всем за актив
Please open Telegram to view this post
VIEW IN TELEGRAM
❤16🔥4
Олимпиады - это не просто сложные задачи и способ поступить
- Это необходимость думать вне шаблона
- Это умение придумывать новые методы для каждой задачи
- Это способность оперировать чем-то большим, чем просто набор инструкций
Это возможность стать умным
- Это необходимость думать вне шаблона
- Это умение придумывать новые методы для каждой задачи
- Это способность оперировать чем-то большим, чем просто набор инструкций
Это возможность стать умным
👍6❤5
Олимпиада "Когнитивные технологии"
#олимпиады
❗ Простая перечневая олимпиада для тех, кто недавно начал заниматься олимпиадами
➕ Плюсы:
🗓 Этапы:
🔗 Ссылки:
- Сайт олимпиады
Пишите в комментариях, про какие еще олимпиады рассказать💡
#олимпиады
- Уровень II
- Три отборочных тура
- Не требует знания сложных алгоритмов
Отборочный этап проходит в 3 тура. Первый в середине ноября, второй в начале декабря и третий в середине декабря. Для участия в финале достаточно хорошо написать только один из трёх туров.
Финал олимпиады проходит в марте.
- Сайт олимпиады
Пишите в комментариях, про какие еще олимпиады рассказать
Please open Telegram to view this post
VIEW IN TELEGRAM
👍5❤3🔥3