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

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

Сегодня в 15:00 MSK начнется третья командная интернет-олимпиада в обоих номинациях.

Зарегистрировать свою команду можно здесь.

Посмотреть свою номинацию можно здесь.

После окончания предлагаю обсудить задачи здесь.

Удачи.

P.S. Больше информации.

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

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

При написании условий про "Сумерки" ни один автор не пострадал.

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

    Не знаю как ты, а я пострадал.. Минут 40 думал тупо над идеей условия

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

Как решать H в усложненке?

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

    ДП на ациклическом графе: dp[i] равно 1, если, начиная из i-ой вершины, мы сможем гарантировать, что сигнал не дойдет до сердца, и 0 иначе.
    Как считать: идем по вершинам в обратном порядке, dp[n] = 0, для остальных i считаем с, равное количеству ребер, идущих в вершины j, такие, что dp[j] = 0. Понятно, что все эти ребра будут идти в уже рассмотренные вершины с посчитанным dp[j]. Итак, если c ≤ k, то, очевидно, dp[i] = 1 (т.к. мы сможем блокировать все ребра в "плохие" вершины с dp[j] = 0), иначе dp[i] = 0.
    Если dp[1] = 0, ответ NO, иначе на каждом шаге блокируем ребра в "плохие" вершины и, тем самым, выигрываем жюри.

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

    Решается задача H очень просто:) (мой код)

    Из условия видно, что данный нам граф ациклический, так как написано, что в нем такие ребра:

    a -> b, где a меньше b.

    Будет считать такую динамику на этом ациклическом графе:

    f[v] — всегда ли может ли сигнал дойти из v-ой вершины в n-ую. видно, что f[n] = true;

    Для остальных вершин v считается так:

    считаем кол-во d — кол-во вершин смежных вершин to, что f[to]=true.

    если d>k то f[v]=true;

    Посчитав динамику мы можем видеть, что если f[1]==true, то нужно вывести "NO";

    А если f[1]=false, то мы сможем оптимально решить задачу так:

    Перекрываем все ребра v->to, где f[to]=true, а v — вершина в которой находится сигнал.

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

Как решать D, F в усложненной?

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

Архив часов в 10 вечера, мы пишем тренировку.

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

А как G из усложненной решать?

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

    На каждом шагу пытаемся найти наибольшее кол-во задач которую сможет решить вся команда. Строим двудольный граф на членах команды и нерешенных задачах. Запускаем поиск максимального паросочетания.

    Повторяем вышеописанные операции раз.

    Код

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

      Я правильно понимаю, что если на какой-то из фаз вы сказали, что такой-то участник делает такую-то задачу, то эту задачу в итоге будет решать именно он, и свое решение вы не поменяете?

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

        К сожалению, я не очень понимаю Ваш вопрос.

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

          Допустим, на одной из фаз была выбрана пара (u,v), то тогда она уже точно попадет в ответ?

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

            Боже мой, я как сдал и увидел, что прошла, то даже об этом не думал :)

            А у Вас есть антитест?

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

    Как ни странно, решаем потоками)

    Построим граф такой, что 0 — исток, 1..m — задачи, (m + 1)...(m + n) — участники, (m + n + 1) — сток. Из истока ребра пропускной способности 1 к каждой задаче, от задач — ребра пропускной способности 1 к участникам, которые умеют её решать. Из участников ребра в исток пропускной способности размера X. Будем перебирать X от 1 до максимального количества задач, которое может решить один человек за контест. При увеличении X пускаем поток по сети, которая получилась из предыдущих X, пока пускается (то есть мы не зануляем поток, а используем старые значения)

    А, ну и ответ обновляем: общее количество задач — это поток, который течет из истока в сток, а штрафное время считается, как сумма ((1 + f[i][t]) * f[i][t] / 2) * L, (t — сток) для всех i от (m + 1) до (m + n), ну то есть всех участников

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

      Тоже решение с потоками, но немного другое. Все ребра с пропускной способностью 1. Пусть из истока ребра ведут в участников. В одного участника ведут несколько ребер, одно стоимости 1, другое стоимости 2 и т.д.. Дальше все просто: из участников в задачи, которые они могут решать стоимости 0, а из задач в сток по одному ребру стоимости 0. Ну и наконец mincost.

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

Теперь я знаю, в чем счастье: сдать самую халявную задачу контеста с седьмой попытки на предпоследней минуте.

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

Зачем вообще давать такие задачи как E, ну объясните пожалуйста? На что вообще рассчитывали.

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

    Нестандартная задача на подумать. Чем плохо?

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

      Наверное подумать над тем, что все ее сдают, и тоже ее запихать.

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

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

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

      Решали поиском количества согласных, которые с двух сторон пробелами окружены

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

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

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

      Как и ожидалось, у жюри такие же рандомные решения

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

        Ты путаешь понятия "рандомные" и "эвристические".

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

      Да. Абсолютно стандартнейший подход, который используется именно для этой цели (ну и ещё иногда для определения языка) — посчитать распределение букв в тексте. Разница между равномерным распределением и свойственным естественному языку получается очевидной, у меня решение зашло с первого раза.

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

      Простое решение. Посчитать длину наибольшего слова. Если длина > 10, то это художественный текст (генератор не генерирует слова такой длинны), иначе генератор.

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

        Простое решение найти артикль the, при чем надо искать такую строку " the ". :)

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

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

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

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

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

Как решать задачу A из усложненки?

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

    Выглядит как HLD чистой воды.

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

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

    UPD 343D

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

    А время неудачных посылок участников-призраков выставляется рандомно? Простите, если глупый вопрос, я просто только сейчас увидел, что оно не соответствует, мне стало интересно

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

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

      Если импорт происходит из формата dat (testsys-compatible, содержит информацию по всем попыткам), то используются настоящие времена.

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

В 18 тесте задачи C усложненной номинации m почему-то больше, чем 100000

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

    Большое спасибо за указание на ошибку.

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

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

      Надо что-то исправить в тренировке? Напишите точно что именно. Спасибо.

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

        Проще будет, если я обновлю сразу архив на сайте.

        Сделаю это завтра или послезавтра и напишу.

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

Скажите, почему в тренировки добавили задачу D с TL 4 секунды? Решение за O(21 * n * n + 21 * (1<<21) + q) на контесте не успевало, а здесь успевает.

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

    Все авторские решения работают 1200-1300 мс. Конечно, если такое решения как ваше не предполагалось, то надо опустить TL.

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

В H усложненного дивизиона TL должен быть 5 секунд, а тут выставлено только 2. Невозможно сдать, она же интерактивная :)

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

    Почему невозможно? Авторское решение работает совсем быстро и написано на Java.

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

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

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

        Запросов на передвижение фишки не более числа вершин, разве нет?