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

SRM 514
Автор sdryapko, 13 лет назад, По-русски
Здравствуйте, сегодня в 5:00 по московскому времени начнется очередной SRM, предлагаю после окончания соревнования вести его обсуждение здесь.
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
У меня одного не заходит в Арену?
У меня выбивает "Error while processing your move request, logging you off ..."
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Новенький автор? )

Как-то насторожило авторское You are... :)

Красивая 250. Интересно, для тех, кто ее быстро сдал - свеча, или просто "быстро думают"? 247+ впечатляют:)

В этой самой 250, куча кодеров забыли, что в С++ 3%2!=(-3)%2 :)

Сам когда написал, долго думал, не пропустил ли где-нибудь случая этих "отрицательных модулей".

P.S. Ну и объясните кто-то 500. Во время тура придумал кое-какое решение, но что-то больно сложное в плане идеи оказалось, молчу уже о реализации. Там можно как-то сравнительно просто? :)

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

    Тоже интересно, что там в 600. Сам свел задачу к прямоугольнику NxM, дальше вроде можно написать аккуратную динамику с маской сумм по столбцам и текущей суммой в строке.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      По моему именно так и надо. Правда сам придумал это только за 5 минут до конца.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        именно так и нужно было делать. меня удивляет, почему так мало народу это придумало... 
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Написал динамику по прямоугольнику NxM, все даже было хорошо, но внезапно понял, что разные раскраски этого прямоугольника влекут разное количество заполнений глобального. В связи с этим надо было допиливать какой-нибудь костыль, но я не успел. Вот если бы цифры были от 0 до 9...
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Количество аналогичных точек на всей сетке найти несложно по индексам. Дальше просто *4^x или *5^x.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я тоже об этом подумал, но это ведь нужно еще разобрать что-то типа 2(n + m) вариантов заполнения первой строки и столбца прямоугольника NxM и для каждого посмотреть все поле. Жалко, что не успел
          → Ответить
          • 13 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Если идти в маленьком прямоугольнике слева направо и сверху вниз, каждое состояние будет описываться только текущими суммами столбцов (2^m) и суммой в текущей строке (2). Суммы в нижних строках не меняются, в верхних - единицы.
            → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Там можно было в самом начале взять модули x и y, а затем работать просто с положительными.

    Уточнение:
    модули в смысле abs()
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я так потерял задачу :о(
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Перед контестом вырубилась арена. не заметил, когда контест начался%)
Понравилась 250
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

не стал 49-м, потому что вместо if ( (x+y)%2==1  0 ) написал if (x+y%2==1 0) O_o

(UPDATED)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Красные, активней пишите ТопКодер, не пропускайте матчи.

А то из-за вашего отсутствия рейтинга мало дают:(

→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

900 подлая -- я долго не мог понять что реально N до 600, а не до 10^9 :о( Вперед к желтому :о)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А это сильно помогает?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      уву

      там каждая новая строка содержит в себе предыдущую в качестве префикса
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не, это я понимаю, то есть я понимаю что n нафиг не нужно(кроме проверки, что оно не в первых K), а вот что делать дальше как-то без идей
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что-то плохо народ порешал сегодня. с 1 задачей так высоко.

Надеюсь это начало моего возвращения:D
→ Ответить
13 лет назад, # |
← Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

Классно я поучаствовал... Написал одну задачу, а на придумывании решения второй уснул О_о Итог, +78 к рейтингу (правда я был синим), стал жёлтым. Хороший метод участия :)

А как решается 600? (выше обсуждали, но по существу там никто не написал)

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    1. Пусть A — наша таблица. Заметим, что чётность A[i1][j1] и A[i2][j2] должна совпадать, когда i1 = i2 (mod m) и j1 = j2 (mod n). Чтобы это доказать, будем двигать полоски m x 1 и 1 x n на одну позицию и смотреть, в чём разница.

    2. После этого задача из 50x50, в которой нужно расставить цифры 1–9, сводится к 10x10, в которой у каждой клетки есть три характеристики: можно ли ставить в неё чётную цифру, можно ли ставить нечётную цифру, а также C[i][j] — сколько клеток с точками в исходной таблице соответствуют этой клетке.

    3. Теперь запустим динамику по профилю, заполняющую нашу таблицу нулями и единицами. Если идти сверху вниз, то профиль — чётности в каждом столбце. Если изломанный профиль, то ещё чётность в текущей строке. Значение функции от клетки и профиля — количество способов так сделать. Когда ставим чётную цифру, домножаем на 4 в степени C[i][j], когда нечётную — домножаем на 5 в степени C[i][j].
    → Ответить