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

TopCoder SRM 485
Автор permin, 14 лет назад, По-русски
21 октября в 15:02 MSD состоялся очередной TopCoder SRM. Предлагаю здесь вести обсуждение. 
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
мне честно говоря не особо нравятся такие раунды
где 250 тупо на кодинг минут 5-10
а 500 я вообще без понятия))
про 1000 молчу)

еще ведь комп завис на отладке 250 - перезагружал)

нужно возвращаться во 2 див наверное)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Со своей колокольни втородивизника могу сказать, что в div2 была такая же ситуация =)
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    500 была достаточно оригинальная и в то же время метод ее решения меня страшно злит) Нужно было подметить, что для матриц N*M, N<=M не никогда решений при N>=5, N=4 & M>=7, N=3 & M>=7. Как подметить..не знаю, в голову должно стукнуть написать полный перебор). А дальше если N=1 - ответ 2^(количество '?'),  N=3 и N=4 решаются просто перебором, N=2 - динамикой по позиции в строке и тому, был ли черный/белый столбец.
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Достаточно просто было увидеть, что нет решений для N >= 5, а остальные случаи решать динамикой
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну всё-таки для N = 4 динамика весьма неудобна, в ней 2^20 * M состояний, между которыми весьма технично описываемые переходы. К тому же, чтобы это для N >= 5 заметить, можно как раз написать перебор, а не доказывать.
        → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я вообще нагуглил по "rectangle free coloring" слайды, в которых про (5, 5) и (3, 7) написано (страницы 15-21). Ушло на это (+ чтение слайдов) минут пять — самому думать, наверно, было бы дольше. Хотя доказать, действительно, просто (можно ещё проще, чем в слайдах, безо всяких случаев).

      С другой стороны, с первого раза (по формулировке "rectangle avoiding coloring" из условия) нагуглить не получилось, так что мне повезло, что я правильно заменил слово :) .
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Так случилось что по 250 не увидел перебор но получил за 20 минут решение O(n + log^2 (MaxW))
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Не очень понятно зачем в первой задаче дано ограничение на то, что существует хотя бы одна последовательность. Это обломало кучу challengeй. А найти к неправильному решению тест с введенным ограничением не так просто. Хотя может в этом и был весь смысл. 
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если такого бы не было сказано в условии, то что возвращать, если такой последовательности действительно не существует?
    → Ответить