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

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

Добрый день.

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

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

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

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

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

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

    У меня как-то был 632. Когда у меня была операция "домкрат" - поднял рейтинг на 900+ за 5 матчей.

    Да ты крут, поздравляю.

    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится
    У меня в самом начале участий на топкодере было 944 - вроде как рекорд)
    → Ответить