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

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

Всем привет! Осталось меньше суток до начала раунда 1B. Если вы, как и я, предпочли сон замечательному раунду 1А, то этот раунд именно для вас! 1000 участников, показавших лучший результат пройдут во второй раунд и не будут иметь возможности поучаствовать в следующем подраунде.

Напоминаю, что раунд пройдёт в субботу, 3 мая в 16:00 UTC на сайте, который и так все знают.

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

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

Напоминаю, что до начала осталось всего 4 минуты.

===============================

Just a reminder. It is less than 4 minutes before the start of contest.

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

как решать С?

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

Как решались А, В, С? :D

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

Как решается C?

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

Я 1002-ой

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

    Ощущал себя также после первого раунда, когда был 1007.

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

Расскажите пожалуйста как решать А и Б) В C у меня на маленьком тесте прошло решение поддерживаем стек где мы сейчас(и куда возвращаться по обратным), проверяем в какие можем полететь (если нужно раскручивать стек, то граф должен оставаться связным), выбираем минимальную и летим туда. На большом получил runtime, либо ошибка в коде, либо в алгоритме.

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

    А. В каждой строке заменим группу подряд идущих одинаковых символов на один такой же символ. Если теперь все строки равны, ответ есть. Для каждого символа в получившемся шаблоне посмотрим, сколько таких букв будет в данной "секции" в финальной строке. Просто переберём это количество, прибавим для каждой строки, сколько нужно будет операций, чтобы получить столько букв, а потом выберем минимум из таких сумм. Понятно, что для каждой секции ищем количество независимо от других.

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

    А:
    Заметим, что всё, что мы можем делать — менять количество символов в отрезке, целиком состоящем из одних и тех же символов. Теперь разбиваем каждую строку на такие отрезки. Если в итоге их общий вид не совпадает, то мы проиграем. Иначе для каждого отрезка перебираем длину, к которой мы хотим привести его для всех строк. Суммарно будет работать , где k — число, до которого перебираем. Легко заметить, что больше, чем 100 его брать незачем. В принципе, если поизвращаться, можно свести к

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

      Даже не нужно перебирать k, известно, что оно равняется медиане множества.

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

        Было такое предположение, не стал рисковать)

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

          Аналогично. Да и если ограничения позволяют, то почему бы и не перебрать)

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

    извиняюсь, 2 часа думал что мы повторяем подстроки, а не символы(

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

Традиционная рубрика обмена решениями.

Два вопроса:

1) А как попроще/покороче решать B-large? Я простенькую динамику по битам написал, которая за O(lg(max(a, b, c)) работает.

2) А как правильно решать C-large? У меня в итоге мнгновенно на их тестах работает O(n!) с неким набором очевидных отсечений.

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

    С там нельзя сказать, что мы идем в минимальный лесикографический индекс, если после этого полета сможем посетить все оставшиеся? Если можно, то перебираем куда летим, можем туда лететь если есть откуда ( в стеке текущего состояния есть элемент, из которого есть рейс в планируемый) и если при этом мы стек разматываем, то в эти вершины мы не вернемся, т.е. их удаляем, проверяем что граф связный. Вроде N^3.

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

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

      То есть на пути в стеке ребра нет, а потом оно появится.

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

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

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

      У меня такое же решение

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

    У меня B-large так: фиксируем префикс, заканчивающийся на 1 в A, в B и в K (+еше надо учесть, когда префикс равен всей строке). Это у нас будет означать числа, в которых префикс фиксирован, потом идет 0 вместо 1 и потом рандомные биты и ты пытаемся посчитать число способов для таких чисел. Ну просто в лоб для каждого бита перебираем что там может быть и перемножаем способы, потом все складываем. Получается за .

    Код: http://pastebin.com/FDB543Na

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

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

А то от жюри получил ответ: "Please read the problem statement more carefully. Consider looking at the limits and the example cases if those might help."

Не прикольно понимать условие из тестов:(

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

    At most 1 outbound flight going to each city, although there is no limit on the return flights (multiple return flights can go to the same city).

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

    Там есть At most 1 outbound flight going to each city

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

How was the large input of Problem B supposed to be solved?

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

Расскажите условие C по-человечески.

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

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

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

You must use all flights which belong to the tickets you booked.

Последний сэмпл.

6 6 10001 10002 10003 10004 10005 10006 1 2 1 6 2 3 2 4 3 5 4 5

Explanation

In the last sample test case, the following is the sequence of what you should do to achieve the smallest number:

Start from city 1, write 10001. Outbound flight from 1 to 2, write 10002. Outbound flight from 2 to 3, write 10003. Return flight from 3 to 2. Outbound flight from 2 to 4, write 10004. Outbound flight from 4 to 5, write 10005. Return flight from 5 to 4. Return flight from 4 to 2. Return flight from 2 to 1. Outbound flight from 1 to 6, write 10006. Return flight from 6 to 1.

Полёт 3 — 5 не был использован, но был заказан. Что я неверно понимаю в условии?

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

    Он не был заказан, его можно было заказать.

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

    На входе даны не купленные билеты, а только пути, на которые можно купить билет. Решать, какие пути использовать, надо самому.

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

Условия только на инглише были? Или я плохо искал? А то my English is shit(

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

How to solve the last problem? I couldn't even solve the small input!

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

Скажите, пожалуйста, это верный вывод на A-small-attempt0.in?

http://yadi.sk/d/SOKmmTTbNyQX2

Просто отправил сейчас, то же самое решение, что и вчера, на тесты в дорешку и всё ОК. Но во время соревнования был вердикт Incorrect. Не уж то на одних тестах проходит, а на других валится..

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

    Если не ошибаюсь, то тесты всем всегда разные выдаются. Дайте свой файл с инпутом, тогда можно будет сравнить ответы.

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

      Спасибо за ответ. Проблема решена. Забыл перекомпилироваться перед отправкой во время соревнования.