Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

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

CodeSprint 5 -- как решать Hacker Country?
Автор AlexSkidanov, 10 лет назад, По-русски

Тут давече прошел пятый CodeSprint. Интересно, как решается вот эта задача: https://www.hackerrank.com/contests/codesprint5/challenges/hacker-country

Стандартное для похожих задач решение с бинпоиском и флойдом ожидаемо ловило таймлимит на половине тестов. Я вижу что кто-то его втолкал ища отрицательный циклы дийкстрой (О.о) вместо флойда, но интересно правильное решение.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

Решение чуть лучше: все как у Вас, только ищем отрицательный цикл алгоритмом Форда-Беллмана с очередью.

Удивлен, что ИТМОшники еще не набежали и не рассказали про то, как эта задача решается за чистый куб. У них, ведь, это задание по алгоритмам и структурам данных (номер 78).

UPD. Погуглите по запросу "Minimum mean cycle", уже на первой странице куча статей и презентаций по теме.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Увидев этот комментарий, подумал, что это скорее всего упражнение из Кормена. Так и оказалось: можно найти в задачах после главы о кратчайших путях из одной вершины.

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Да, это забавная штука. Только недавно слушал её на спецкурсе у Максима Бабенко. Если вкратце, то утверждается, что если насчитать Фордом-Беллманом массив D[k][v] — кратчайший путь длины ровно k до v из произвольной стартовой вершины 1, из которой достижимы все вершины графа, то минимальный средний вес цикла равен .

    → Ответить