Квадрат Тьюринга | Олимпиады по информатике
950 subscribers
51 photos
2 files
88 links
Квадрат Тьюринга — онлайн-школа подготовки к ЕГЭ и олимпиадам по информатике.

Наша цель - развивать мышление, в отличие от обычных онлайн-школ, которые натаскивают по шаблонам.

по всем вопросам - @nvrmanager
отзывы о нашей работе - @turing_feedback
Download Telegram
#Спортпрога_с_нуля
Как начать ботать самостоятельно?

Памятка для новичка с ссылками на все необходимые ресурсы.

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


Вот три пункта, на которые нужно обратить внимание:


1. Язык программирования. Какой именно - не принципиально, если не знаешь никакой, начни с Python (вот очень хороший курс на степике), в дальнейшем стоит пересесть на C++ (хороший курс на степике, не менее хороший курс от Яндекса).

2. Алгоритмы. Они нужны чтобы решать типовые задачи, к которым можно сводить настоящие задания. Алгоритмы существуют на любой вкус, знать их необходимо, но уходить только в них не стоит, следующий пункт гораздо важнее. Изучать их можно на курсе от Яндекса, так же есть Algorithmica, сайт со всеми алгоритмами, полезными на олимпиадах. Также не могу не добавить канал Павла Маврина с лекциями по алгоритмам на ютубе.

3. Задачи. Третье, что необходимо для успеха на олимпиадах, — это нарешивание задач. Именно количество решённых задач отличает хорошего олимпиадника от плохого. Где их решать - скажу далее.


Удачи!
11
Квадрат Тьюринга | Олимпиады по информатике pinned «#Спортпрога_с_нуля Как начать ботать самостоятельно? Памятка для новичка с ссылками на все необходимые ресурсы. Как я рассказывал ранее, олимпиады по спортивному программированию отличаются по формату от других олимпиад. Все усугубляется тем, что спортивное…»
#Спортпрога_с_нуля

Где брать задачи?

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

Рассказываю, где брать задачи:

- Создай аккаунт на Codeforces, там очень много задач, а ещё проводят обучающие раунды (локальные олимпиады с наградой в виде внутреннего рейтинга).

- Решай задачи на Timus Online Judge, чтобы набить руку. Просто отсортируй задачи по сложности и иди по порядку.

- В конце зимы и лета рекомендуется пройти отбор в кружок Яндекса или Т-банка (по своей сути они почти не отличаются). Но даже если поступить туда не получится, то лекции и задачи лежат в открытом доступе.

Удачи!
6❤‍🔥1
#алгоритмы
Бинпоиск - самый популярный алгос

Решим задачу:
Я загадал вам целое число от 1 до 1.000.000. Вы можете назвать мне любое число, а я скажу, больше ли оно загаданного, или меньше. Ваша цель угадать число.
Заметим, что если вы назвали число X, и я сказал что оно больше загаданного, то вам нет смысла называть числа меньше X. Таким образом, каждый запрос уменьшает диапазон потенциальных ответов.

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

Такой алгоритм называется бинарный поиск от слова bin (англ. - два), так как каждый раз мы делим отрезок на две части.

Время работы: Так как каждый раз мы делим отрезок пополам, сложность алгоритма - O(log(n)), где n - изначальный размер диапазона (подробнее про оценку сложности). Ответ на изначальную задачу такой алгоритм найдет за 20 операций.

Подобный метод обобщается не только на поиск элементов, но и на проверку каких-либо монотонных свойств, которые сначала выполняются, а потом не выполняются, или наоборот.

Примеры задач на бинарный поиск:
- "1, 10, 100, 1000..."
- Букмекеры
73
#Олимпиады

Технокубок - лучшая школьная олимпиада.

Олимпиаде поменяли уровень в этом году с первого на второй, но она все еще котируется на многие хорошие направления (ИС ИТМО, ВШЭ ПИ и прочие)

Для второго уровня олимпиада средняя по сложности, дает много мерча и очень часто входит в список Шабурова.

Порядок отбора:
Отбор состоит из трёх раундов (17 ноября, 8 декабря, 22 декабря).Чтобы пройти на финал необходимо взять призера хотя бы на одном раунде.

Задачи прошлых лет
91
#алгоритмы

Асимптотический анализ - это должен знать каждый олимпиадник

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

Когда мы решаем задачи нам важно, чтобы решения могли отработать за определенный срок времени при любых входных данных. Мы знаем, что Python выполняет примерно 10⁶ операций в секунду, однако считать сколько операций выполняет конкретный алгоритм просто нерационально.

Идея. Давайте оценивать не точное количество операций, а то как оно увеличивается с ростом размера входных данных.

Для этого придумана O-нотация.

В контексте анализа алгоритмов, фраза «алгоритм работает за O(f(n)) операций» означает, что начиная с какого-то n он делает не более, чем за c ⋅ f(n) операций.

Таким образом:
- бинпоиск работает за O(log(n))
- Сортировка пузырьком работает за O(n²)
- Сортировка слиянием работает за O(n • log(n))
9
#задачи
Как быстро прокачаться с полного нуля?


Важнейшей частью вашего развития является решение задач. Для взятия всероса достаточно базовых тем, если нарешать на них достаточно заданий. Нет смысла сидеть и задротить продвинутые алгоритмы, которые даже не попадутся на реальной олимпиаде, зато есть смысл каждый день решать по 2-3 задачи с тимуса (к слову, очень хорошая практика, через полгода возьмете перечень).

В дополнение к тому посту, буду периодически кидать подборки хороших по моему мнению задач.

- A
- B
- C
- D
- E

Если нужны подсказки или советы - пишите @nvrmanager

Всем удачи!
5👍33
#олимпиады

Бельчонок - олимпиада, которая проще, чем егэ

Если вы до сих пор никуда не поступили, то вы должны обратить на эту олимпиаду внимание

- Уровень: II (котируется в ИС ИТМО)

- Проходит дистанционно с прокторингом, то есть пишите дома с подключенной вебкамерой

- Не связана со спортивным программированием

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

Сайт олимпиады
Задания прошлых лет
🔥43
#алгоритмы

Какие алгоритмы изучать?

Алгоритмов очень много, все их них в той или иной степени полезны. В этом посте кратко опишу какие алгосы изучать первым делом.

1. Бинарный поиск
Пожалуй, самый распространенный в спортпроге алгоритм.

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

3. Два указателя
Несложный метод, постоянно встречается как в задачах, так и в других алгоритмах.

4. Динамическое программирование
Очень обширная тема, при помощи неё решается огромное количество задач.

Где изучать алгоритмы рассказывал в том посте, так же буду иногда кидать свои статьи на эту тему.
62
по многочисленным запросам открыл комментарии
73
постепенно людей становится все больше, через неопределенное количество времени напишу полноценный пост знакомство
6🔥1
#алгоритмы

Префиксные суммы

Решим задачу:
Дан массив 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🔥22
#Спортпрога_с_нуля

Про кружки от Яндекса и Т-банка

В начале каждого учебного года стартуют кружки по спортивному программированию от Яндекса и Т-банка. Оба имеют одинаковый формат: раз в неделю проходит лекция по теме и появляется контест. Лекции выходят в записи и лежат в открытом доступе.

Кружок делится на несколько параллелей по уровню.

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

Кружки нужны, чтобы изучать продвинутые темы и нарешивать на них задачи.

Главная проблема - большой порог входа. Это не то место, где вы сможете начать ботать с нуля, ибо отбор не самый простой.

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

Оба кружка имеют одинаковый формат, но от себя рекомендую именно кружок от Яндекса, там преподаватели получше и мерч интереснее.

Ссылки:

Яндекс кружок

Кружок Т-банка
7
Про репетиторство
#Информация

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

❗️Я практикую два формата:

🔥 Занятие в мини-группах
В группе от 2 до 5 схожих по уровню людей. Заниматься таким образом эффективнее, интереснее и дешевле, а мне не нужно тратить время, рассказывая один и тот же материал по несколько раз, так что все в плюсе.


⭐️ Занятия для начинающих
В середине сентября я начну проводить занятия для начинающих в спортивном программировании. Проводиться они будут на протяжении 2.5 месяцев, занимаемся по формату Яндекс кружка. В курсе будут все необходимое, чтобы в дальнейшем развиваться и успешно писать олимпиады.
Если какой-то из этих вариантов вас интересует, то пишите в лс: @nvrmanager
Please open Telegram to view this post
VIEW IN TELEGRAM
8👍1🔥1
Динамическое программирование
#алгоритмы

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


Решим задачу

Есть 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 соответственно). Главное - для каждого состояния знать, как в него можно перейти.

Приводить конкретные примеры задач не буду, так как на Тимусе есть целый раздел, посвященный этой теме.

В дальнейшем сделаю пост про задачу о рюкзаке.
75👍3
Олимпиада Учи.ру по информатике дает 25 баллов на отборочном этапе Технокубка, если написать её без ошибок.

Сама она перечневой не является, но, как способ упростить себе отбор, имеет место быть.
5🔥11
Какие олимпиады писать, чтобы поступить🔤
#олимпиады

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

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
11🔥3❤‍🔥1
Задача о рюкзаке
#алгоритмы

Перед прочтением данной статьи рекомендую прочитать статью про динамическое программирование

🖥Решим задачу:
Есть n предметов, предмета i имеет массу a[i]. Есть рюкзак, который может вместить предметы, с суммарным весом не более S. Необходимо найти такой набор предметов, что их суммарная масса максимальна, но не превосходит S.

Заметим, что если у нас есть набор предметов массой W, в который не входит предмет с номером j, то мы можем добавить этот предмет в набор, получив суммарную массу W + a[j]. Это наталкивает на использование динамического программирования, осталось только понять, что взять за состояние.

💡Идея: Пусть dp[j][W] равно единице, если можно набрать массу W, используя первые j предметов. Это будет наше состояние, теперь опишем переходы.
Рассмотрим последний предмет. Если мы его не берем, значит нам надо набрать ту же массу при помощи первых j - 1 предметов. Если мы берем, то нам надо набрать массу W - a[j]. Таким образом, dp[j][W] можно пересчитать, как
dp[j][W] = dp[j - 1][W] or dp[j - 1][W - a[j]]


➡️Чтобы решить задачу, достаточно пройтись по всем значениям двумя циклами. Внешним циклом перебираем число j, внутренним - число W. Ответом будем максимальное число i такое, что dp[n][i] = 1.

Асимптотика такого решения составит - O(n • S)

Тема непростая, так что если есть вопросы - обращайтесь

🔗Ссылка на контест на информатиксе
Please open Telegram to view this post
VIEW IN TELEGRAM
👍53
❗️Хочу предложить новый формат
#информация

Занимаемся в большой группе, допустим 20 человек. Лекции и домашние задания заранее заготовлены, занимаемся каждую неделю на протяжении 2.5 месяцев.

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

Подходит тем, кто вообще не имеет опыта в спортивном программировании и хочет легко войти в олимпиадную среду.

Для занятий требуется знать базовые конструкции любого языка, что с нуля изучить легко

Напишите в комментариях, что думаете по поводу такого формата
Please open Telegram to view this post
VIEW IN TELEGRAM
5🔥32