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

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

Привет, пользователи codeforces.

Решил подготовиться к грядущим раундам, решая задачи на тимусе. Подскажите пожалуйста, задачи какой сложности на тимусе примерно соответствуют задачам с див2 раундов?

На мой взгляд: < 50 — A, 100-120 — B, 150-200 — C. Но меня больше интересуют D и E, так как их я еще решать не умею, но хочу научиться. Пожалуйста, помогите.

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

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

Мое субъективное мнение — чтобы лучше решать СF, нужно решать СF. Здесь и соответствие между задачами установить намного проще)

Тимус весьма специфический сайт, и мне задачи оттуда очень слабо напоминают СF. Хотя я не так много там решил, и не так часто там бываю, но все же)

А на CF пишем раунд виртом, потом с разбором осваиваем D и E, которые решать не умеем, вот и вся стратегия:)

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

На тимусе весьма специфическая оценка сложности. Задачи из первых томов дольше существуют, поэтому их больше сдавали, и они часто сложнее, чем новые задачи с такой же сложностью. Кажется, система как-то учитывает "свежесть" задач,но, вероятно, не очень хорошо.

Также, есть спецэффект с популярными задачами. Например,почти все, чтобы попробовать сдать HLD сдают Caves and Tunnels, из-за чего стоимость этой задачи занижена.

Ах да, я бы сказал, что стоимость задачи на тимусе равна стоимости задачи на кф минус 500. На D-E, это не очень распространяется, но для А-В-С мне кажется весьма справедливой оценкой.

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

    Эта твоя оценка стоимости — это в терминах div1 задач, а не для div2, правильно? :)

    Спецэффект с популярными задачами наглядно — это когда 1519 проще, чем 1343.

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

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

    Всё, что я написал ниже, представляет собой исключительно мои впечатления.

    Мне вот кажется, что наоборот — задачи из первых томов имеют нереально завышенную сложность по сравнению с их настоящей сложностью, а новые имеют заниженную сложность, вплоть до того, что 600 (UPD : скорее 550) первого тома это около 300 десятого тома (задачи с завышенной сложностью, конечно, встречаются в поздних томах, но это обычно редкость, в первом томе почти у всех задач завышенная сложность).

    Понятно, что на тимусе есть куча различных и очень странных спецэффектов, связанных с методом определения сложности, например: 1334 "стоит" баллов на 400 больше, чем должна, а 1744 вообще на 1200, не меньше (по моим впечатлениям). Понятно, что также есть задачи с неоправданно заниженным рейтингом.

    Вообще, если забыть про флуктуации рейтинга задачи, то я абсолютно не согласен с тем, что 1000 на тимусе есть Div1 C на Сodeforces, так как (ИМХО) одна из самых простых задач с рейтингом 950-1050: 1965 представляет собой что-то, что у меня ассоциируется с Div1 C.

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

      там самый забавный спецэффект — задачи, у которых только английские условия. их наверное многим лень читать (я и сам такой был). сколько раз натыкался на такие а они оказывались гораздо легче, чем оценены.

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

    Рейтинг тимуса странный вообще, он основан на количестве решивших и на том, как долго задача существует. Вот несколько примеров, где этот рейтинг неадекватен: 1341, 1398 — эти задачи довольно далеко расположены, если посортить по сложности, но каждая из них за 10 минут делается.

    А еще есть неприятные в реализации задачи, например: 1438 (вообще треш), 1488, 1852. На контестах это никто не решает, а в архив можно посдавать, если за количеством гонимся (я так делал)

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

      ИМХО, 1488 очень просто пишется, я её сдал меньше, чем за 30 минут без особых проблем (то есть на контесте тоже можно сдать).

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

Но меня больше интересуют D и E, так как их я еще решать не умею, но хочу научиться.

Прямо вообще ни одну? А Вы много раз пробовали? Или Вы попробовали решить пару штук, с обеими не получилось, и Вы обобщаете на все?

Сорри за оффтопик. Просто понятие "объективная сложность задачи" ну слишком нечеткое. Допустим, есть безыдейная задача на знание какой-либо неизвестной для Вас структуры данных и есть задача, где нужно заметить неочевидную идею и написать 10-20-50 строчек совсем простого кода. Какая из них сложнее? А если Вы все-таки знаете ту структуру?

Я вот в свою бытность новичком решал на Online Judge все подряд. Некоторые задачи не получались — я их откладывал (не выбрасывая из головы), а потом вновь к ним возвращался. Возможно, Вам тоже не стоит заморачиваться насчет численной сложности?

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

    Прямо вообще ни одну? А Вы много раз пробовали? Или Вы попробовали решить пару штук, с обеими не получилось, и Вы обобщаете на все?

    На контестах ни одну, так как иногда до них тупо не дохожу. Начинать думать над задачами D, E за <30 минут до окончания раунда считаю нецелесообразным.

    Просто понятие "объективная сложность задачи" ну слишком нечеткое. Допустим, есть безыдейная задача на знание какой-либо неизвестной для Вас структуры данных и есть задача, где нужно заметить неочевидную идею и написать 10-20-50 строчек совсем простого кода. Какая из них сложнее? А если Вы все-таки знаете ту структуру?

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

    Я вот в свою бытность новичком решал на Online Judge все подряд. Некоторые задачи не получались — я их откладывал (не выбрасывая из головы), а потом вновь к ним возвращался.

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

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

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

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

      Начинать думать над задачами D, E за <30 минут до окончания раунда считаю нецелесообразным.

      Можете обосновать это утверждение?

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

        Только тем, что мне может не хватать 30 минут для решения более простых задач, нежели див2D.

        Можно еще вопрос, вы добивали сложные задачи самостоятельно, или рано или поздно читали разбор/спрашивали у человека, который решил?

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

          Можно еще вопрос, вы добивали сложные задачи самостоятельно, или рано или поздно читали разбор/спрашивали у человека, который решил?

          Иногда спрашивал, иногда получалось-таки добить самостоятельно. Тут ИМХО важно пройти самостоятельно как можно дальше, а потом попросить кого-нибудь довести Вас до правильного решения.

          Только тем, что мне может не хватать 30 минут для решения более простых задач, нежели див2D.

          Не знаю, первой решенной мной на раунде КФ задачей была как раз Div2-D. Я тогда был ну совсем новичком, но сдал эту задачу на 30 минуте — просто она мне показалась более очевидной, чем A-C. Говорю же: не заморачивайтесь так сильно насчет буквы, либо численной сложности на Тимусе.

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

        Ну вот допустим, знаю я, что существуют дфс, бпф, алгоритм Укконена, Карацубы и алгоритм построения диаграммы Вороного за нлогн, но не умею реализовывать ни один из них. Это лучше, чем когда я умею реализовывать дфс, но не знаю об остальных? В чём лучше?

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

          Я, например, не знаю алгоритм Укконена, но знаю что он существует. И когда я увижу задачу "постройте суффдерево", не буду ломаль голову как это сделать, а пойду разбирать/копипастить алгоритм.

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

            Я вот тоже не знаю алгоритм, но если суфф дерево не надо строить в онлайне, то, наверное, построю его автоматом. В смысле, разверну строку и возьму дерево суфф ссылок. Вот и суфф дерево готово...

            P.S. Если задача попадётся на контесте, вряд ли знание о существовании алгоритма как-то поможет. Разве что можно будет полчаса сидеть и биться об стол со словами "вот же я даун, я же знал, что это можно делать, ну почему я сразу не изучил, как..."

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

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

              как раз наоборот, можно сразу бросать эту задачу и решать дальше.

              А вообще, контесты бывают long форматов, где можно всё успеть изучить. И большинство случаев — это всётаки когда ты бодаешся с задачей на online judge (в данном случае тимус).

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

                Ну в принципе да, об стол можно будет побиться позже, особенно если задача в итоге будет разделять кучу мест :)

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

          Оффтоп: это каким же надо быть убогим, чтобы знать, что такое ДФС, но не уметь его реализовывать?

          Еще оффтоп: я давным-давно читал обзорно читал про алгоритм Форчуна и запомнил его идею. На ЧУ-2013 была вот эта задача. Я вспомнил про алгоритм Форчуна и понял, что в том конкретном случае он совершенно тупо реализовывался за линию. Итого — АС по задаче.

          Я имел в виду, во-первых, то, про что уже написал tyamgin, а во-вторых, то, что в любом алгоритме самое ценное — его идея, а совсем не детали реализации.

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

            Ну я образно. Можно дфс на какой-нибудь алгоритм Дейкстры за ElogV заменить.

            в любом алгоритме самое ценное — его идея, а совсем не детали реализации.

            С этим, конечно, не поспорить, здесь я абсолютно согласен.

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

      Начинать думать над задачами D, E за <30 минут до окончания раунда считаю нецелесообразным

      ну вот, вы считаете нецелесообразным, а там оказывается халява вроде 459D - Задача Пашмака и Пармиды или 451D - Считаем хорошие подстроки.

      Помню пост какого-то серо-зеленого индуса, который по ошибке зашел в контест для Div1 вместо Div2, увидел, что все решают задачу A (Div2C) за 5 минут, и тоже решил ее за 10 минут :)

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

        А да) Опять вспомнил как не обратил внимание, что там алфавит из 2 букв(((

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

Лучше Codeforces ничего нету!