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

TopCoder SRM 493
Автор Egor, 15 лет назад, По-русски
13 января в 5:00 по Москве состоится очередной TopCoder SRM
Так же в какое-то близкое время состоится тестовый раунд Facebook HackerCup - может быть, epic fail не продолжится
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Хотел поинтересоваться (на ТС пока ниразу не удалось поучаствовать онлайн), всегда ли время СРМа такое раннее? Бывает ли часов в 18-21.00 по Москве?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
Ты действительно надеешься что fail на facebook закончится?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
По-моему первый раунд будет 15-го в 18:00 по Москве..
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится
GL & HF
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, пожалуйста, как решать вторую задачу с див2, она же первая с див1?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
фейл-контест) у меня +1 рейтинга в 1 диве за ничего)
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
как я хотел себя убить...
я забыл в 300 проверять, что тот блок, который мы переворачиваем - не вылезает на [1..N]

>_<

кстати, а 450 я запихал только в дорешивание... не знаю, как люди сдать могли - там нужно хачить и хачить, чтобы уложить в ТЛ и МЛ.

но в итоге оно у меня работает 18мс. на их сервере :-D
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    не нужно ничего хачить, простой перебор даже с  set<vector<int> > для мемоизации состояний проходит без проблем
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Я написал решение на шарпе с отдельным классом под состояние, и хранение их в Dictionary. И у меня локально на макс тест работало секунд 5. Переписать на хранение состояния в числовой маске успел только через несколько минут после конца.
      → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Изначально K было до 9. Потом решили уменьшить до 7, а то там очень жестко оптимайзить надо чтобы прошло.
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    В 450 достаточно несложная динамика. Вначале перебор по ответу. А потом уже без особых проблем можно за 50 x 7^7 памяти решить, при помощи сохранения для каждого цвета расстояния до последней его встречи (если оно больше чем проверяемый ответ, то полагаем равным ответу). Пересчет - достатчно тривиален: если можем оказаться в позиции i с расстояними j (храним их в числе не превосходящем d^K), то перебираем цвета которые мы можем добавить и пересчитываем маску расстояний.

    На макс тесте работает около 0.7 сек.

    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Я не говорил, что она сложная =)
      вопрос в том, что там на грани ограничения. пришлось запихивать.

      хотя отмечу, что если бы ограничения были бы меньше... задача была бы уже не такой интересной =)
      → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А что там за эпик фейл был расскажите? хотел поучаствовать, но совсем забыл про дату окончания. Там из-за этого epic fail-а не планируется еще один квал?)
→ Ответить