Prynik
@Prynik

Есть ли карта подготовки к ВсОШ по информатике?

ВсОШ - Всероссийская олимпиада школьников (в моем случае по информатике).
Все задания в олимпиаде носят алгоритмический характер.
Пример заданий 1
Пример заданий 2

Понимаю, что здесь задания больше информатические, чем на программирование. На данный момент знаю большое количество теорий графов и умею их применять, а заданий на них попадается много. С программированием все отлично, в основном специализируюсь на JS, но для олимпиады данный язык не подходит, отлично знаю JAVA.

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

Я сейчас как Лунтик, который упал с луны, не знаю куда идти и, что делать, а желание огромное, меня бы пнуть в нужную сторону, а я дальше сам :)
  • Вопрос задан
  • 1828 просмотров
Решения вопроса 2
azerphoenix
@azerphoenix Куратор тега Java
Java Software Engineer
Нуу...
Попробуйте порешать задачи по Java & Problem Solving на https://www.hackerrank.com/
Там как раз есть похожие задачки..
Отдельно можно прочитать книгу про "Структуры данных и алгоритмы"
Поиграйтесь с приложением - https://play.google.com/store/apps/details?id=wiki...
Тут различные алгоритмы написанные на Java:
https://github.com/TheAlgorithms/Java
Ответ написан
@witaway
Я бы на твоём месте программировал олимпиады всё-таки на плюсах. Хотя бы потому, что прохождение по времени на олимпиадах гарантируется только если ты писал на них. Ещё обязательно решай кодфорсы, причём очень много. Чем больше, тем лучше. Если задачу совсем не получается решить - читай разбор или разбирайся в чужих решениях. ЭТО ВАЖНО! ПРАКТИКА - САМОЕ ГЛАВНОЕ. Не забивай. )

Если уровень у тебя ещё не очень большой, помочь может сайт ACMP. Там есть куча задачек. Но там, в общем и целом, уровень приблизительно областной.

В принципе, как некоторый roadmap ты можешь использовать сайт e-maxx.ru. По факту, если ты на самом деле хочешь взять всерос, почти всё оттуда придётся изучить. Не забывай про то, что в России на олимпиадах любят геометрию (если я не ошибаюсь), поэтому развить в себе некоторую мат. базу, вроде тех же векторов, будет хорошей идеей.

Ещё у меня есть свой Roadmap, но которому я бы на твоём месте не сильно доверял: всё-таки, я даже на республику не прошёл и моё мнение не может быть сильно авторитетным. Но, по крайней мере, свои ошибки я знаю. :)

https://www.notion.so/e4be58821dfb4e979802ae6e89df425a
По факту, ты не найдёшь здесь ничего нового, чего ты не мог прочитать на е-максе, кроме, разве что, трипка (он же декартово дерево, он же дерамида, он же курево). Штука очень полезная, очень мощная и незаслуженно непопулярная.

Ещё тебе могут пригодиться в олимпиадах всякие оптимизации прагмами (можешь сам найти) и некоторые полезные штуки из gnu pb_ds (https://codeforces.com/blog/entry/11080?locale=ru). Ещё структура rope, тоже из pb_ds, поищи. На олимпиадах время от времени пригождалось. Но это, ес что, сугубо плюсовые gcc-шные штуки.

Ещё я бы прорекламировал репозитории на гитхабе с алгосами:
Мой (мне нравится мой кодстайл, но алгосов не оч много): https://github.com/witaway/Sport-Programming
Марка Корнейчика: https://github.com/markysha/SP
Артура Петуховского: https://github.com/petuhovskiy/Templates-CP
Последние два - классные наши олимпиадники, Марк точно брал респу и вроде брал какую-то российскую (он вроде в ВШЭ учится), Артур призёр межнара, тоже классный чел. :)

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

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

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

P.s. Ой-ой, как-то неожиданно много текста получилось.

Так как комментарии у меня закончились, отвечу на твои вопросы ниже:

Правильно ли я понял, что ключевую роль играет прохождение по времени и асимптотика?

Конечно, именно так эти олимпиады и работают. Тебе надо научиться писать программы, которые будут проходить как можно больше тестов (а следовательно, получать как можно больше баллов) и при том эта программа обязательно должна вписываться в данное время. А потому и асимптотика тоже важна. И, в принципе, любые оптимизации.

C++?

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

И если всё-таки будешь изучать C++, разберись в стандартной библиотеке. Из неё тебе точно понадобятся vector, map, set, unordered_map, unordered_set, sort, queue, dequeue, priority_queue, stack. И, может быть, какие-то алгоритмы из библиотеки algorythm, но на практике, там всё ерунда и из полезного можно выделить разве что функцию next_permutation.

Ещё, вспоминая то, что ты говорил, что знаешь графы: если что, Дейкстра бывает за квадрат, а бывает за NlogN. Если ты про вторую не знаешь, обязательно изучи и больше про первую не вспоминай.

А вообще, эти все алгоритмы надо понимать, но лучше всего, помимо этого, ещё и знать их практически наизусть. Потому что на олимпиаде каждая минута на счету. А такие алгосы как дерево Фенвика, префикс-функцию и Z-функцию ты можешь в принципе сразу зазубрить и не морочить себе голову. Они пишутся легко, а понимаются не очень легко. Хотя в любом случае, для общего развития лучше выяснить, как оно работает изнутри.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bell Integrator Ульяновск
До 400 000 ₽
Bell Integrator Ижевск
До 400 000 ₽
Bell Integrator Хабаровск
До 400 000 ₽