Блог пользователя gofkane

Автор gofkane, 12 лет назад, По-русски

Какой по-вашему минимум алгоритмов(структур данных и пр.) стоит знать для успешного участия?

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Что вы подразумеваете под программированием?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      Написание программ.

      PS: Искренне ваш, кэп

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        Мне кажется я вполне ясно сформулировал вопрос. Переформулирую: Что нужно знать для решения наибольшего количества задач?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Все-таки, ИМХО, в первую очередь нужно выработать у себя т.н. "алгоритмическое мышление". Это понятие довольно расплывчатое, но можно сказать, что в него входят такие вещи, как умение правильно разбивать задачу на подзадачи, способность извлечь из какого-либо алгоритма его идею и применить ее в совершенно другом месте, ну и т.д..

            Ну и стоит набираться опыта (решать задачи) и учить уже конкретные стандартные алгоритмы по мере надобности.

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Для участия в чем? Для соревнований по стрельбе с лука можете вообще не учить структуры данных.

Ну а если серьезно, то до крепкого желтого или даже до красного на ТС и СF можно добраться без особых знаний.

Специфика в том, что это не АСМ, длина контеста и его индивидуальный характер не позволяют давать сложные задачи; а если они есть, то их решают не многие.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +55 Проголосовать: не нравится

    На топкодере главное динамику решать :)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      До верхнежелтого хватает и стабильной Easy, в которой ДП не часто

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      А как научиться решать динамику с ТопКодера? Может быть, кто-нибудь знает метод кроме прорешивания тысяч задач на динамику? :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -22 Проголосовать: не нравится

        Если бы я знал такой стратегический секрет, я бы не делился ни с кем)

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Тебе жалко, если одним человеком, умеющим решать динамику, станет больше? оО

»
12 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

Читай бессмертный топик.

Теоретический минимум для программиста.

Читать по порядку. Как дочитаешь, возвращайся.

А если серьёзно, отсюда к спортивному программированию имеют отношение пункты 1, 6, 7, 8, 10, 11, 12, 13, 14, 15, 20, 31, 30, что тоже немало.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Мне кажется, что нормальный человек столько знать не может. Конечно, можно рассуждать о том, что если время тратить на то, чтобы 8 часов спать, 1 час есть и 1 час отдыхать, а оставшиеся 14 часов тратить в течение 5 лет на учебу, то я верю, что можно все прочитать и понять. Но ведь знания, не закрепленные на практике, не имеют никакого смысла. А чтобы сделать даже простенькую курсовую (не копипасту из википедии, а маленькую исследовательскую работу), нужно потратить минимум неделю. Мне кажется, такой объем информации из различных областей невозможно хранить в голове одновременно.

    Существует еще математический минимум — думаю, многие видели эту "программу". Что вы о ней думаете?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Мне кажется, что нормальный человек столько знать не может.

      Вроде эпический "теоретический минимум для программиста" уже успели высмеять все кто могли — там даже не в том дело может ли человек столько знать, сколько в том что человек едва ли может за 40 лет профессиональной деятельности успеть поработать в стольки областях чтобы ему всё это пригодилось (даже если по году в каждой). Ну и до кучи там отсутствуют многие популярные нынче словечки (поищем Android или Mongo — а Java вынесена в специфику которую можно учить после этого минимума), зато некоторые зело архаичные употребляются многократно (нюансы x86 архитектуры это наше всё!).

      С математическим минимумом, как мне кажется, дело ещё хуже т.к. когда мы говорим "для программиста" — мы под этим можем хотя бы представить некоего сферического околокомпьютерного инженера с широким профилем, погружённого в разуплотнённый гелий — но что представляет из себя будущий специалист которого мы собрались учить математике (по этой например программе) вообще не понятно. Встречаются математики в природе ощутимо реже, изучать их сложнее. Особенно абстрактные, которые не математики-программисты или математики-физики и т.п. Оценивать их работу обычно сложно т.к. для этого нужен другой математик а не тестировщик или пользователь. Имхо, обязательную программу нужно рассчитать до конца 2 курса, а дальше специализация, кураторы, научные работы и руководители, вебинары и сообщества математиков по интересам, благо интернет расширяет границы. %)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        Ну давайте раззведём холивар на тему пригодится ли спортивное программирование на практике....

        Я ожидал увидеть примерно то, что написал ниже mimirrow. Но это прямо уж совсем минимум. Может кто-нибудь дополнит список?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +26 Проголосовать: не нравится

          Для успешного выступления в СП нужны не структуры данных, а идеи и умение реализовывать эти идеи. И никто никогда вам не скажет, что в решении какой-то ключевой задачи не будет аналогии с построением +-1 RMQ за O(1) с O(N) предпросчета.

          Помните: "кто лучше знает теорию" определяет места красных, но не зеленых. Уже были неоднократные наблюдения, когда фиолетовые обсуждали Укконена, а красные — наибольшую возрастающую за N*log(N) через lower_bound.

          Просто решайте задачи. Если не можете решить задачу — ищите подсказки. Если в подсказке незнакомая АТД — прочитайте о ней. Все.

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Очень часто попадаются задачи на написание бинарного поиска, НОД и НОК чисел, к примеру. Полезно знать некоторые сортировки, более эффективные — QSort, MergeSort и цифровую(там где элементов много, но все элементы меньше 10^5 или 10^6 по модулю). Знание дфс и бфс(очереди) намного облегчают жизнь. А из структур могу посоветовать дерево отрезков, дерево фенвика, корневую, декартово дерево. В принципе, данных алгоритмов и их умелого использования хватит на довольно успешные выступления.

»
12 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

What a stupid question !?

»
12 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

Пачиму вы миня все так нагло минусите?????

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    а что такое "Структура Румянцева"?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Тоже интересно. Гугл ничего не находит, это явно какое-то локальное название.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    UPD. Неактуально