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

Автор riadwaw, 12 лет назад, По-английски

Today, 19:10 MSK

Registration is already started. Good luck!

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

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

На чём всех ломали в 250?

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

    Меня сломали на том что я забыл домножить координаты на 2 :)

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

      Да туплю!

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

      Во 2-ом сэмпле встреча происходит в нецелых координатах, даже в условии сказано. Даже и не пытался на таком случае ломать...

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

        Да. Только решение работает на этом тесте и без учета этого. А кто ж читает пояснения к тесту который отработал и так при понятном условии?

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

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

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

            Мне почему то кажется, что так и было задумано :)

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

        Я обычно не читаю описания семплов, а ответ на нем совпал

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

        Решение, не учитывающее встречу в нецелых координатах проходит семплы.

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

        Я всегда буду читать описания семплов.

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

        У меня была другая бага, из-за которой решение падало на этом сэмпле. Заодно исправил и нецелые координаты. Повезло ^_^.

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

          Моё неверное решение, прошедшее сэмплы, пофиксил ресабмит Petr'а, заставивший задуматься, что что-то тут не так.

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

            Да-да, мне, главное, не хватило ума продолжить логическую цепочку. Смотрю, многие ресабмитят... Ну что ж... Может быть, мало итераций дали, кто их знает, мол, буду я из-за их багов свое время тратить, задача ж простая:)

            Хорошо хоть на челленджах +5/-3 и в итоге все же небольшой плюс к рейтингу.

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

    тест {1,2}, {0,0}, "EW"

    Два муравья встретятся на 0.5 сек

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

    Один человек ходил не по 1, а по 0.5, но делал не 4000 итераций, а 2000.

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

Как решить 550? (Я весь контест придумывал матрицу, чтобы ее возводить, но видел очень простые решения)

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

    Заметим 2 факта:

    1. от S нам нужно максимум |F| символов в начале и столько же в конце
    2. они быстро перестают меняться
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      На сколько быстро они перестают меняться и почему?

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

        Если f(x)=u+x+v+x+w то префикс быстро (не более 50 итераций) станет u^k например

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

      IMHO в этой задаче нужно было делать K <= 1,000,000. Чтобы решение за O(k*|F|) и O(|F|) памяти на автомате, построенном по КМП-функции, тоже проходило. А то я поначалу неправильно посчитал количество нулей в k, и в итоге все насмарку :(

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

        Для K=10^6 решение получается вообще лобовое и безидейное и никак не тянет на 550.

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

          Не такая уж это и "забоянившая" техника. Было время, когда на 500-550 давали задачки на поток. Тоже весьма лобовые. И гораздо более классические в СП.

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

            И что в этом хорошего? Идеальный медиум — где надо долго думать и мало писать, имхо. А стандартные задачи на поток превращают раунд в чемпионат по копипасте.

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

У кого-нибудь есть идеи как решать 1000?

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

    UPD: видимо ниже неправда

    Каждая клетка размножит себя за 2к итераций на крест вида

    ....o...
    ........
    ....o...
    ........
    o.o.o.o.o
    ........
    ....o...
    ........
    ....o...

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

    Закодить правда не успел. Писать это противно как-то

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

      Это кстати не неверно при k>1

      Зато это верно для k=1, так что если k четно то поле распадается на 4 независимых сетки, каждая из которых ведет себя аналогично исходной

      На этом построено мое решение

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

      Это верно для 2^k итераций. Но что с этого толку я не придумал.

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

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