Ответы пользователя по тегу 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-функцию ты можешь в принципе сразу зазубрить и не морочить себе голову. Они пишутся легко, а понимаются не очень легко. Хотя в любом случае, для общего развития лучше выяснить, как оно работает изнутри.
    Ответ написан