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

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

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

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

нужно возвращаться во 2 див наверное)
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Со своей колокольни втородивизника могу сказать, что в div2 была такая же ситуация =)
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 - динамикой по позиции в строке и тому, был ли черный/белый столбец.
    • 16 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится
      Достаточно просто было увидеть, что нет решений для N >= 5, а остальные случаи решать динамикой
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Я вообще нагуглил по "rectangle free coloring" слайды, в которых про (5, 5) и (3, 7) написано (страницы 15-21). Ушло на это (+ чтение слайдов) минут пять — самому думать, наверно, было бы дольше. Хотя доказать, действительно, просто (можно ещё проще, чем в слайдах, безо всяких случаев).

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