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

Автор NVAL, история, 9 лет назад, По-русски

Ссылка на страницу с результатами и задачами

Сегодня виртуально решали этот четвертьфинал и возникло два вопроса:

1) Зачем давать задачу I, которая в точности до символа копирует условие задачи с Osipovsky Cup 2014 (декабрь, Ковров), проходившего в центральном же регионе? Причем некоторые команды естественно присутствовали на этом соревновании, а некоторые нет (например команда занявшая 3-е место и не сдавшая её).

2) Я правильно понимаю, что задача E в предоставленных ограничениях не решается? :| Т.е. при циклах нулевого веса.

Других обсуждений, к сожалению, не нашел.

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

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

2) Забавно. Я даже не задумывался об этом когда решал. Видимо здравый смысл сработал где-то на подсознательном уровне. Но вообще конечно нехорошо что такие неоднозначности в условии есть.

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

1) Я думаю, что задачу I дали ошибочно. Уже после разбора мы увидели, что задачи совпадают (но не в точности до символа). До этого мы думали, что это похожая задача... 2) Если есть нули то у нас бесконечно много решений. Мы задали этот вопрос на разборе, нам ответили, что да, тестов с нулями не было и подразумевалось что циклов нулевого веса нет.

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

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

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

      .

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

        15 тест матрица 1000 на 1000 из нулей.
        Но там не совсем понятное условие задачи. Нигде не написано, что пути должны быть простыми. И неоднозначно можно понять условие различия двух путей. В общем авторское решение считает пути 1-2-3-4 и 1-3-2-4 одинаковыми.
        Поэтому проходили некоторые решения, которые на нули не обращали внимания.

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

      Я неправильно написал про бесконечно много решений. Two routes are considered different if at least one city on the route is not the same as on the other route. То есть таких путей не бесконечно много и решение всегда есть.

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

        Ну хотя да, если по хорошему вникнуть в это условие, то оно исключает ходы в саму себя и циклические пути.
        P.S. Хотя нет, не исключает) Мы можем сходить по нулевой петле и вернуться в ту же самую вершину. Либо не ходить по ней.

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

          Я думаю, что это условие лишь ограничивает размер путей(не больше количества вершин) и говорит о том как сравнивать два пути.

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

А ещё в задаче H решение (в том числе авторское) использует даблы, при этом ответ дискретный. И нигде не гарантируется, что если поменять данные на eps, то ничего не изменится.

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

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

    Еще одна неточность в условии состояла в том, что не был описан случай с двумя цилиндрами, если все их радиусы равны R, а высоты различаются. Тут есть два варианта — один стоит на другом и один вкладывается в другой до основания. В авторском решении был первый случай, но по тексту условия и второй корректен.

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

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

круто я буду

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

Кстати, почему то поменяны в условии задачи K и J местами относительно того, что было на соревновании. Или так и задумывалось?

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

    Ну, на сервере, на котором решали и уральцы, и команда NArFU, условия релевантны тем, которые были на соревновании.

    Претензии по задаче E странные, условие вполне понятно сформулировано, никаких KSON-ов там нет.

    Про задачу I странно, действительно, задачи совпадают. Когда я просматривал условия, то отметил, что задачи похожи, но предположил, что это "сиквел" той задачи. Кстати, в Коврове-2014 было не так и много команд из Центрального региона (РГАТУ2 и собственно ковровские команды); на самом деле жаль, так как набор задач, как мне кажется, вышел интересным.

    А вот вопрос с задачей H (см. выше) неплохо бы исследовать. Там WA 14 у двух топовых команд УрФУ, ответы совпадают. Если есть контакты автора, могу переслать ему оба решения.

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

      В задаче Е очень смутно дано определение того, какие пути называются различными. Судя по твоим комментариям, ты считаешь, что отличаться должны множества вершин. Решение, которое я сдал, на тесте
      5
      1 5
      0 0 1 1 1
      1 0 0 1 1
      1 1 0 0 0
      1 0 1 0 1
      1 1 1 1 0
      выводит 1 вместо 2 (пути 1-2-3-5 и 1-2-3-4-2-3-5).

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

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

        Ну вот похоже, что авторы тоже так считают (судя по ответу на "нулевой" 15-й тест, да и на некоторые ненулевые тесты).

        Хотя на этом тесте их решение тоже выдаёт 1. Так что проблемы не в условиях, а в решении; соответственно, в обсуждение вызывается и автор этой задачи.

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

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

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

            Ну или автор поставил более сложную задачу, но решил в итоге эту. В любом случае без автора на Opentrains это исправить не получится.

            Плюс ещё ситуация с H кажется подозрительной. Ваша команда дорешивать H собирается?

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

              наверное, но не сегодня

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

              Я вроде как нашел в авторском ошибку в 60 строке. Надо бы пересудить. После ее исправления ответ начинает сходится с ответами участников.

              P.S. Перетестировали.

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

      Да, я автор задачи. Действительно, после соревнования выяснились пара проблем с условием и погрешностью вычислений. Перешлите решения, я попробую продебажить их локально. Почта [email protected]

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

Задача D — Teletype тоже оказалась баяном. В 2006 в Центральном ЧФ была аналогичная задача(G — Message).