Рассказываю, как начать ботать информатику

Что такое олимпиады по программированию?

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

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

Например:

Напишите программу, которая для данного числа выведет сумму его цифр.

Задач на такой олимпиаде немного, от 4 до 8.

Во-вторых, результат по задаче виден сразу, а свое решение можно менять сколько угодно раз. Программа проверяется на большом количестве скрытых тестов (от 50 до 200), после чего выдается вердикт в зависимости от результатов на тестах.

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

Существуют два основных формата.
1. IOI формат - каждая задача либо дает 100 баллов если все тесты пройдены, либо не дает ничего. За неправильные посылки начисляется штраф. Это необходимо чтобы разделять результаты людей с одинаковым количеством решённых задач. Штраф также накапливается со временем. Как правило используется на командных олимпиадах, а также отборочных турах.
2. ICPC формат - каждая задача имеет группы тестов, объединенные какими-то условиями. Баллы начисляются за каждую полностью пройденную группу тестов. Штрафа нет. И пользуется на большинстве индивидуальных олимпиад.

В следующем посте будут советы как начать ботать с полного нуля и вкатиться в олимпиадное сообщество.

#Спортпрога_с_нуля
Как начать ботать самостоятельно?

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

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


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


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

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

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


Удачи!

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

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

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

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

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

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

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

Удачи!

#алгоритмы
Бинпоиск - самый популярный алгос

Решим задачу:

Я загадал вам целое число от 1 до 1.000.000. Вы можете назвать мне любое число, а я скажу, больше ли оно загаданного, или меньше. Ваша цель угадать число.

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

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

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

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

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

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

#Олимпиады

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

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

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

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

Задачи прошлых лет

#алгоритмы

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

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

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

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

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

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

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

#задачи
Как быстро прокачаться с полного нуля?


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

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

- A
- B
- C
- D
- E

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

Всем удачи!

#олимпиады

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

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

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

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

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

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

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

#алгоритмы

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

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

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

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

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

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

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

по многочисленным запросам открыл комментарии

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

#алгоритмы

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

Решим задачу:

Дан массив 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).

Задачи:
- Найдите сумму на отрезке

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

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

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

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

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

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

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

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

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

Ссылки:

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

Кружок Т-банка