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

TopCoder SRM 475
Автор Egor, 14 лет назад, По-русски
6 июля в 15:00 MSD состоится очереной SRM
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Мне необыкновенно повезло :) Последний СРМ я писал из Питера в 5 утра, а этот буду писать из Чикаго в 6 утра по местному :)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Ну правильно! :) Что от хорошей то привычки отходить? :)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У меня одного арена не грузится?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кажись заработало
→ Ответить
14 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
kto ponel shto vozvrashat 550 zadache?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    подобные вопросы стоит задавать после челленджа
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
a kakaya raznica?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ну, может данная информация поможет кому-нибудь челленджить по ней
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Жутко обидно. Если бы не крайний случай в 600 - было бы первое место (наверное, я же не знаю еще результаты систем тестов)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Есть идеи как организовать вычитание в динамике в 600? Динамика вроде очевидная, но вот вычитание с модулем портит всё.... Или я вообще не верно понял ход решения задачи. :))
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Надо делать по модулю, домноженному на 2 в степени числа плохих лет
    Тогда все ок
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Эээ... что-то мне совсем понятно, что ТАК будет всё ОК? Можно попробнее пожалуйста?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если мы знаем остатов числа x по модулю n * m (q), то остаток числа x / n по модулю m будет q / n
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Посмотрел 600 у Гены. Так и не понял, почему проверять на чётность можно так просто. Из-за модуля ведь это никак этого не сделать, или тут какая-то хитрость именно в этой задаче?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Если я понимаю вопрос, то потому что он считает по двум модулям - по нужному и по четному. И на четность он проверяет ответ, посчитанный по четному модулю.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я всё равно не понимаю. Если бы были только операции сложения и вычитания, то всё просто, но тут есть деление на 2. Допустим возьмём даже чётный модуль, пусть 10.

      a = 2, b = 12

      по модулю 10 они равны, но (a / 2) - нечётное, (b / 2) - чётное.

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Если взять модуль, равный 2N, то можно корректно выполнить N делений пополам.
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А контест был рейтинговым или нет?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как же я не люблю задачи типа 300 в Диве1. Обычно такие задачи, у меня вроде бы работают как и у всех, но на СистемТесте у меня валится на какой-нибудь тупой мелочи, а у других нет. Плюс еще vexorian заставил высрать немало кирпичей :), говорит у меня мол неправильно, тока тест не мог подобрать.

Но удивительным образом задача прошла и теперь я впервые желтый на Топкодере :)

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, трехсотка откровенно неудачная... Что-то сходу даже не могу вспомнить задачу на топкодере, которая была бы хуже этой :(
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Кстати от Field там нужна только длина. почему-то никто не догадался :)
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Я тоже так думал, пока не увидел Правильное РешениеTM.

      Оно состоит в том, что если количество кроликов нечётно, то ответ всегда 1: ведь их останется 0, 1 или 2, и чётность их количества не поменяется.

      Если же оно чётно, то их иногда останется 0, а иногда — 2. Когда сколько — зависит от того, сколько кроликов начинают на нечётных клетках, а сколько — на чётных. Получается простая комбинаторная задача: найти количество способов из n элементов выбрать k, а потом разбить на две чётных или две нечётных группы.

      Теперь я думаю, что это скорее очень хорошая задача, чем очень плохая ;) .
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вот решение участника Dremov из моей комнаты, в котором это реализовано.
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Теперь я думаю, что задача еще хуже, чем я думал. Ко всем ее прежним недостаткам добавился тот неприятный факт, что она похоронила в себе такое красивое решение :)
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится
          Ну это скорее большинство участников предпочло писать и плеваться, а не думать :) .
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            А мне не показалась задача совсем уже неудачной. Вполне нормальная для 300. Сразу видно, что нужно поперебирать и промоделировать. Я вроде был вторым в комнате, кто заслал её после Натальи Бондаренко. Одна эта сданная задача дала хороший "+" мне в рейтинге, что не может не радовать. :))
            → Ответить