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

TopCoder Open Round #4
Автор Egor, 15 лет назад, По-русски

Добрый день.

Сегодня в 20:00 по Москве состоится четвертый отборочный раунд TopCoder Open. В пятый раунд пройдет 60 участников. Всем удачи!
  • Проголосовать: нравится
  • +54
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Блин, я не прочитал в 300, что все иксы и игреки различны :( Написал более сложное решение, сделал неудачный челлендж, не успел закончить 500.
→ Ответить
  • 15 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +5 Проголосовать: не нравится

    Про 300 - +1, аналогично, написал решение, которое должно и при равных работать (на чем потерял время). А 500ка - хз, на 5 сек. не успел послать решение, правда оно наверное ТЛ бы словило всё равно.

    500ка неверная как и ожидалось, правда оказывается я и 500ку условие криво прочел сегодня... (потерял ограничение до 5 карт и получилась очень жосткая задача).
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Хм, в 500-ке гениальная бага - константа "на автомате" стала 57 вместо 75 :( Зато MikeMirzayanov смог это почелленджить и попасть в топ-60 - gratz!
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Надо будет проверить свою 500, которую дописал 3 минуты спустя. Если пройдет - очень обидно
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
У кого-нибудь есть мысли по поводу 1000?
Я написал жадное решение, но оно на последнем сэмпле выдает ответ оптимальнее чем у жюри. Багу пока не нашел)
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится
    Кмк, это минимальный разрез. Для каждого радара построим две цепочки - одна из "выходных" вершин, вторая из "входных", по одной вершине для каждой мощности. Разрез цепочки "выходных" или "входных" вершин между мощностями i и i+1 соответствует уменьшению мощности до i. Есть дуга из "выходной" вершины от одного радара до "входной" вершины другого когда соответствующие окружности пересекаются. Ну и надо разрезом отделить левую сторону от правой.

    Плюс еще можно пооптимизировать, убрав много ненужных вершин и ребер.

    Я написал за минуту до конца, но не прошел сэмплы. После контеста нашел два бага, сэмплы теперь проходят, практис рума пока нет :)
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +8 Проголосовать: не нравится
      Практис рум появился, систест прошло. Код можно там тоже посмотреть теперь.
      → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Моя жадность на тесте 5 получает мощности [3, 3, 2, 2, 2, 2, 3, 3, 3], что дает ответ 7.
      Я нарисовал тест на бумажке, вроде как разрез есть. Может я в чем-то неправильно понял условие?
      → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
у меня после этого раунда volatility подскочил до 564 =)
→ Ответить